본문 바로가기

알고리즘225

BOJ 1074 - Z https://www.acmicpc.net/problem/1074 재귀로 완전탐색하는 기본문제를 찾다가 접한 문제다. 주어진 입력을 4분할해서 좌상단 우상단 좌하단 우하단 순으로 방문하고 기저를 잘 처리해주면 되겠다 해서 처음으로 짠 코드. cnt[][] 2차원 배열로 방문 순서를 저장할까 했지만, 그냥 cnt=0부터 한개씩 올려주면서 처리하는 것으로 했다. #include int n, r, c; int cnt, rst; void go(int cy, int cx, int n) { if (n == 0) { if (cy == r && cx == c) rst = cnt; cnt++; return; } go(cy, cx, n - 1); go(cy, cx + (1 2019. 7. 4.
07 - 쿼드 트리 QUADTREE_SOL #include #include using namespace std; string reverse(string::iterator& it) { char head = *it; ++it; if (head == 'b' || head == 'w') return string(1, head); //head string형태 return string upperLeft = reverse(it); string upperRight = reverse(it); string lowerLeft = reverse(it); string lowerRight = reverse(it); return string("x") + lowerLeft + lowerRight + upperLeft + upperRight; } int main() { int.. 2019. 6. 30.
07 - 쿼드 트리 QUADTREE 1. 흑백 그림의 string 형태 표현에 대한 규칙설명, string 형태 표현 입력으로 주어졌을 때 그림을 상하반전했을 때의 결과에 대한 string 형태 표현을 출력으로 하는 문제. 2,3. 문제에서 트리를 그림으로 굳이 보여준 것에 의문을 갖고 생각해보니 주어진 입력을 트리로 구성만 한다면 x의 자식은 항상 4개고 w,b의 자식은 항상 없으니 루트트리부터 3,4,1,2번째 자식 순회하면 ㅆ가능하다고 생각함. 4. 처음엔 재귀로 트리를 구성하려 했지만 내 수준이 너무 떨어져서인지 구현할 수 없었음. string의 최대 길이가 1000이므로 for문으로 돌려도 가능하겠다 싶어서 구현해봄. 1) 첫 인덱스부터 for문을 돌린다면 자식노드로 사용된 노드는 다음에 부모 노드로 사용될 수 있지만, 부모 노드.. 2019. 6. 30.
06 - 시계 맞추기 CLOCKSYNC 1. 시계 16개를 모두 12시가 되도록 스위치를 누르는 문제. 2,3. 스위치와 시계의 연결은 const vector linked[10] = { //[switch][clock]형태 {0,1,2}, {3,7,9,11}, {4,10,14,15}, {0,4,5,6,7}, {6,7,8,10,12}, {0,2,14,15}, {3,14,15}, {4,5,7,14,15}, {1,2,3,4,5}, {3,4,5,9,13} }; 이렇게 함. 스위치를 4번 이상 누르는 경우가 없다. 스위치를 누르는 순서는 상관이 없다 (이걸 생각을 못해서 처음에 재귀를 못짬.) -> 스위치 누르는 순서를 0번-9번으로 강제함. 기저: 누를 스위치가 10번(존재하지않음)일 때 시계들이 정렬돼 있다면 0, 아니면 큰 수 반환 5. #incl.. 2019. 6. 27.

티스토리툴바