본문 바로가기

알고리즘

BOJ 백준 1753 최단경로 https://www.acmicpc.net/problem/1753 이 문제의 입력은 총 정점의 수와 간선의 수, 시작할 정점과 각 간선들에 대한 정보가 주어진다. 간선의 방향이 존재하며, 시작 정점으로부터 다른 모든 정점들에 대해 최단 경로를 출력해주어야 한다. 다익스트라 문제는 종종 풀었으나, 우선순위 큐를 이용하여 푼 적은 거의 없었다. 이 문제도 보자마자 다익스트라를 사용했고, 결과는 시간 초과였다. 메모리 제한 : 256MB시간 제한 : 1초 우선 정점의 수가 최대 20000개이므로 일반 배열, 즉 20000 * 20000의 int형 배열로는 메모리 초과가 난다. 그래서 vector을 이용하여, 간선의 정보가 주어지면 push해주는 방법을 이용했다. 난 단순히 메모리초과만 생각하고 벡터로 한 뒤 ..
BOJ 백준 2644 촌수계산 https://www.acmicpc.net/problem/2644 말 그대로 촌수 계산을 해 주는 문제이다. 입력값으로는 1. 사람의 수2. 촌수를 계산하려는 두 사람3. 부모-자식 관계의 수 4. 부모-자식 관계 이렇게 들어온다. 문제에서 원하는 것은 2번에 입력된 두 사람의 촌수를 출력해주는 것이다. 촌수를 계산하려는 두 사람의 공통되면서 최소인 부모노드를 찾고 찾아낸 부모노드로부터 촌수를 계산해주면 되는, 어렵지 않은 문제이다. vector을 이용해서 두 사람의 부모노드들을 찾아 저장해주고, 비교해주면서 최소 부모 노드를 찾아내는 형태로 풀었으나, 사실 추가 배열 없이 parent[]라는 배열 하나로 문제 풀이가 가능하다. #include #include #define SIZE 101 using n..
BOJ 백준 7569 토마토 https://www.acmicpc.net/problem/7569 이 문제는 한 토마토가 익은 상태라면, 다음 날에는 그 토마토의 앞, 뒤, 왼쪽, 오른쪽, 위, 아래의 토마토가 익게 되는데, 이 때 상자에 있는 모든 토마토가 익는 데에 최소 몇 일이 걸리는 지 계산해주어 출력해주는 문제이다. 모든 토마토를 익게 할 수 없을 시에는 -1을 출력해주고, 처음부터 모든 토마토가 익어있는 경우엔 0을 출력해주면 된다. 하나 하나가 자신의 전후좌우를 전염시켜나가는 문제들과 유사한데, 조금 다른 점은 한 층의 배열이 아닌 여러 층으로 이루어져 상, 하까지 전염시켜주어야 하는 것이다. 3차원 배열을 자주 사용해보진 않았지만, 예를들어 2 x 3 배열이 2개 있다는 것은 2 x 2 x 3으로 생각하면 되므로 int ..
BOJ 백준 1068 트리 https://www.acmicpc.net/problem/1068 트리가 주어지고 삭제할 노드를 정해주었을 때, ( 삭제한 노드의 자식노드들도 삭제되는 것으로 간주 ) 그 트리의 리프 노드의 개수를 구하는 문제이다. C++을 공부하고 있어서 인지 class를 이용하여 풀고 싶었다. Node class의 멤버 변수, 함수들 ****************************************** Node* parent : 부모 노드 ( 부모 노드는 단 한 개 ) Node* child[SIZE] : 자식 노드들 ( 여러 개일 수 있기 때문에 배열로 선언 ) int n_size : 자식 노드의 인덱스 및 개수 bool deleted : 자신이 삭제된 노드인지 아닌지를 표시할 bool 변수 in..
BOJ 백준 9461 파도반 수열 https://www.acmicpc.net/problem/9461 1 1 1 2 2 3 4 5 7 9 12 ... 12의 다음은 문제 그림에 있는 밑면, 12 + 4인 16이 나온다. 16의 다음은 밑면에 거꾸로 된 삼각형이 붙어있다고 생각하면, 왼쪽 면인 16 + 5로 21이 나오게된다. 1 1 1 2 2 3 4 5 7 9 12 16 21... 가장 가까이 있는 항으로 규칙을 맞춰보려면, 21 = 16 + 5 // 16 = 12 + 4, 즉 dp[n] = dp[n - 1] + dp[n - 5]가 된다. dp[n] = dp[n-1] + dp[n-5]로 하기 위해서는, 1 1 1 2 2 를 내가 직접 넣어주고, 6번째항부터 점화식이 성립된다. 즉, 기본값으로 5개가 있어야하는 것이다. ..
BOJ 백준 12100 2048 (Easy) https://www.acmicpc.net/problem/12100 이 문제는 게임의 조건만 제대로 이해하면 푸는 데는 크게 어려울 것이 없는 문제이다. 1. 현재 움직이려는 칸이 0인 경우는 빈칸이므로 고려하지 않는다. 2. 현재 움직이려는 칸이 이동하려는 칸이 0인 경우 ex ) 2 0 4 0 2 4 0 0 0 -> 0 0 00 0 0 0 0 0 3. 현재 움직이려는 칸의 이동할 칸이 0 이 아닌 경우 3-1. 현재 움직이려는 칸과 이동할 칸의 값이 같은 경우 - 현재 움직인 칸을 0으로 만들어주고 이동할 칸의 값을 *2를 해준다. - 단, 움직이려는 칸이나 이동하려는 칸이 이미 합쳐진 경우가 있다면, 그 칸은 더 이상 이동하지 못하므로 break ex) 2 ..
BOJ 백준 13460 구슬 탈출2 콜라한캔 https://www.acmicpc.net/problem/13460 1. 빨간 구슬과 파란 구슬 중 어떤 구슬을 먼저 굴릴 지 판별한다. 2. 상, 하, 좌, 우 방향으로 판을 기울여 구슬을 굴린다. 2 - 1. 이전에 굴린 방향이나, 굴린 방향의 반대 방향 ( UP - DOWN / LEFT - RIGHT )의 경우 고려하지 않는다. 2 - 2. 판을 기울였는데, 빨간 구슬과 파란 구슬 둘 다 움직였을 경우 고려하지 않는다. 3. 굴린 결과를 다시 재귀로 보내준다. 4. 파란 구슬이 들어가지 않고, 횟수가 10번이 넘어가지 않는 상황에서 빨간 구슬이 들어갔을 때 판을 기울인 횟수를 저장한다. 1번 조건. 상, 하, 좌, 우 4가지 경우로 나누어 생각해보면 된다. 판을 기울여서 구슬들..