꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1720 백준 11727번 2*n 타일링 2(http://jaimemin.tistory.com/401)을 심화한 문제였습니다.tiling 함수 구현 자체는 똑같지만 뒤집힌 경우 좌우 대칭인 경우를 찾아내는 방법을 모색하는 것이 너무 어려웠습니다.그래서 중복되는 모양을 찾는 대신 중복되지 않는 방법을 찾았습니다.아래는 http://m.blog.daum.net/rhaoslikesan/369?tp_nil_a=2 포스팅을 참고한 내용입니다.tiling 함수를 통해 타일을 구하면 중복된 모양 + 중복된 모양 + 중복되지 않은 모양 이렇게 세 가지 경우의 수를 구할 수 있습니다.현재 문제에서 요구하는 답은 (중복된 모양 + 중복되지 않은 모..

문제 링크입니다: https://www.acmicpc.net/problem/1695 앞에서 뒤로 보나, 뒤에서 앞으로 보나 똑같은 숫자를 팰린드롬이라고 합니다.따라서, 알고리즘은 아래와 같습니다.1. arr[begin]==arr[end]라면 begin 인덱스는 하나 증가, end 인덱스는 하나 감소를 시킵니다.2. arr[begin]!=arr[end]라면 조건 충족을 위해 숫자가 하나 추가되어야 하므로 begin 인덱스만 하나 증가시키거나 end 인덱스만 하나 감소시킵니다. 이 중, 더 작은 결과를 반환합니다. #include #include #include //memset using namespace std; const int MAX = 5000; int N; int arr[MAX]; int cache..

문제 링크입니다: https://www.acmicpc.net/problem/2580 흥미로운 백트래킹 문제였습니다.처음에 풀 때는 3*3 칸 내에서도 1~9가 하나씩 존재해야한다는 규칙을 잊어먹어서 틀렸습니다.3*3 칸 내 인덱스는 change2SquareIdx 함수를 통해 반환받았고 각 열, 행, 그리고 3*3 칸 내에 숫자 존재 여부를 파악하기 위해 bool 형 배열 row, col, square를 선언했습니다.스도쿠는 총 9 * 9 = 81칸이기 때문에 DFS 함수를 최초로 호출할 때 매개변수로 0을 전달하고 cnt가 81이 되면 스도쿠 판을 출력하는 식으로 코드를 작성했습니다. 주의할 점은, 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다는 것입니다!(exit(0) 필수)*exi..

문제 링크입니다: https://algospot.com/judge/problem/read/FAMILYTREE 구간 트리(Segment Tree) 문제이기 때문에 Algospot MORDOR(http://jaimemin.tistory.com/662) 문제처럼 RMQ(Range Minimum Query) 구조체를 이용해서 푸는 문제였습니다.두 노드의 촌수 계산을 위해서는 공통 조상 LCA(Least Common Ancestor)를 찾는 것이 핵심입니다.예를 들어 u와 v의 촌 수를 계산하기 위해서는 (u의 깊이와 + v의 깊이 - 2 * LCA(u, v)의 깊이)를 구하면 됩니다! 새그먼트 트리는 일렬로 늘어선 배열을 처리하는 자료구조이기 때문에 해당 알고리즘을 사용하기 위해서는 트리를 펴서 일렬로 만들어야..

문제 링크입니다: https://algospot.com/judge/problem/read/MORDOR 문제를 보면 간단히 시간 복잡도가 O(N)인 탐색 기법으로 최대 높이와 최소 높이의 차를 구하는 문제처럼 보이지만 요구하는 알고리즘의 시간복잡도가 O(logN)이기 때문에 구간 트리(Segment Tree)에 대한 개념을 모르면 풀 수 없는 문제였습니다.RMQ(Range Minimum Query) 클래스의 query 함수는 node가 표현하는 범위 array[nodeLeft..nodeRight]가 주어질 때 이 범위와 array[left..right]의 교집합의 최소치를 구해주기 때문에 최소 높이를 쉽게 구할 수 있습니다.이제 최대 높이를 구하는 것이 문제인데, minusHeight 벡터에 높이의 부호를..

문제 링크입니다: https://www.acmicpc.net/problem/10845 오랜만에 자료구조 큐를 복습할 수 있던 문제였습니다.사실, 덱(deque)을 쓰면 훨씬 쉬운 문제였지만 문제의 의도대로 큐를 사용해서 풀었습니다.덱을 사용하면 back도 쉽게 할 수 있지만 큐는 FIFO(First In First Out) 구조이기 때문에 살짝 까다로울 수 있습니다.저 같은 경우에는 back을 출력하기 위해 (현재 큐의 사이즈 - 1)만큼 pop을 한 다음에 push를 하는 방식으로 큐를 환형큐라고 생각하면서 오른쪽으로 쉬프트했습니다. #include #include #include using namespace std; int N; int main(void) { cin >> N; queue q; for ..

문제 링크입니다: https://www.acmicpc.net/problem/12100 핸드폰 게임인 2048을 모티브로 만든 문제이지만 게임과는 달리 한번 shift에서 이미 합체된 블록은 더 이상 합체되지 않는 점이 특징이였습니다.백준 14500번 테트로미노(http://jaimemin.tistory.com/623)처럼 브루트 포스(Brute Force)와 DFS(Depth First Search) 알고리즘을 함께 적용시켜 푸는 문제였습니다.Board를 적절히 복사해주고 원상복구해주는 것이 핵심이였습니다. #include #include using namespace std; const int MAX = 20; int N; int board[MAX][MAX]; int maxBlock; void shift..

문제 링크입니다: https://www.acmicpc.net/problem/1107 N=500,000까지이지만 5 6 7 8 9가 망가졌을 경우도 고려해야하기 때문에 MAX를 1,000,000+1까지 설정해야했던 문제였습니다.일차적으로 이 부분에서 틀렸던 문제이고 이차적으로는 length 함수에서 0에 대해 예외처리를 하지 않았기 때문에 틀렸던 문제였습니다.알고리즘 자체는 간단한 브루트포스였습니다.1. 기존 채널 100에서 +/- 버튼을 클릭하는 경우2. 채널을 입력하고 +/- 버튼을 클릭하는 경우 위 두 가지 경우 중 최소를 반환하는 값이 정답이였습니다. #include #include #include #include using namespace std; const int INF = 987654321;..

문제 링크입니다: https://www.acmicpc.net/problem/2251 처음에는 A 물통과 B 물통은 비어있고 C 물통은 가득 찬 상태에서 시작합니다.한 물통이 비거나, 다른 물통이 가득 찰 때까지 물을 부을 수 있으므로 아래와 같이 두 가지 경우의 수를 고려해줘야 합니다.1. 비우는 물통과 채우는 물통의 합이 채우는 물통의 한계보다 클 경우, 비우는 물통은 완전히 비지 않습니다.2. 비우는 물통과 채우는 물통의 합이 채우는 물통의 한계보다 같거나 작을 경우 비우는 물통은 완전히 빕니다. 위 두 조건을 고려했다면, BFS(Breadth First Search) 알고리즘을 적용하여 A 물통이 비었을 때 C 물통이 가질 수 있는 물의 높이를 정렬하여 순차적으로 출력해주면 AC 처리를 받을 수 있..

문제 링크입니다: https://www.acmicpc.net/problem/5427 백준 3055번 탈출(http://jaimemin.tistory.com/649)과 동일한 문제였습니다.단지 비버의 집이 범위 밖 좌표가 되었고 두더지 출발지점이 '@', 물에서 불로 바뀌었을 뿐입니다.그런데도 불구하고 헷갈려서 세 번째 시도에서나 AC 받은건 비밀입니다. #include #include #include #include #include //memset using namespace std; const int MAX = 1000; typedef struct { int y, x; }Dir; Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; int W, H; stri..