Algorithms

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 이 문제를 처음 푼게 3년전이었고 그 때는 한 3일간 고군분투했지만 끝내 통과하지 못했다. 질문 게시판에 존재하는 모든 테스트케이스를 통과했음에도 '틀렸습니다'가 나오는 이유는 아직도 모르겠다. 3년이 지난 지금 다시 풀어보았고 역시나 쉽지 않은 문제였다. 때문에 다른 사람이 푼 코드를 참고하여 풀었다. 참고한 코드: https://bio-info.tistory.com..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 1) 처음에는 위상정렬의 일부 개념(진입차수가 0인 노드부터 탐색)을 사용한 dfs 문제인 줄 알았으나 2) 위상정렬과 완전히 동일한 알고리즘을 구현하는 문제라고 깨달았다. 1)의 이유 -> 건설 과정에서 택하는 루트는 단 하나이다. 여러개의 루트로 가서 하나의 노드에서 만난다면 그 노드에서 택하는 이전 루트는 누적된 건설시간이 더 큰 하나의 루트이다. 즉 dfs 로 구현해야 한다고 판단하였..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이 문제는 웰노운에 속한다고 한다.. 트리의 지름이란 문제에서 가중치의 합이 가장 큰 경로가 존재하며, 그 경로의 가중치를 말한다. 이번 리뷰는 문제풀이보다는 증명 위주이다. 자세한 증명 방법은 아래 블로그 주소를 참고바란다. https://blog.myungwoo.kr/112 트리의 지름 구하기 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net DP문제이다. 처음 접근할 때는 그리디, 완전탐색, DP 중 하나일 것으로 가정한다. 우선 그리디로 해보자. 3 1 2 3 4 5 6 4 9 0 예제에 나온 숫자대로 탐색할 때 가장 큰 혹은 작은 숫자만 더해서 내려간다고 할 때 가장 큰 숫자로는 3 -> 6 -> 9 = 18 (정답) 이지만 가장 작은 숫자로는 1 -> 4 -> 4 = 9 (오답) 으로 실제 정답인 1 -> 5 -> 0 = 6 보다 크기 때문에..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net dfs를 통한 완전탐색이다. 완전탐색인지를 알아차리는 것이 중요하기 때문에 시간복잡도 계산하는 연습을 꾸준히 해두어야 한다. 세로길이 m, 가로길이 n인 배열에서 벽 3개를 세우는 경우의 수는 총 m x n 개에서 3개를 택하는 조합과 같다. 그렇게 벽이 세워진 상황에서 배열의 모든 공간을 하나씩 탐색하는 경우의 수는 {mn * (mn - 1) * (mn - 2) / (3 * 2 * 1)} * mn 이 된다...

https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 겉보기에는 단순한 문제이다. 세 점이 이루는 두 선분의 방향이 시계인지 반시계인지를 알아내는 것은 딱 생각했을 때 다음과 같다. 점 A, B, C를 A(x1, y1), B(x2, y2), C(x3, y3) 라고 정의할 때, 점AB가 이루는 직선상에 점C가 있는 경우 0을 출력하면 된다. 그리고 직선상에 있지 않은 경우에는 둘로 나..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 방문하지 않은 정점을 탐색하는 그래프 이론을 알고 있다면 접근자체는 쉬운 문제다. 파티에 속한 사람들을 연결리스트로 나타낸 이중배열과 각 사람이 속한 파티를 연결리스트로 나타낸 이중배열을 만들었다. 굳이 각 사람에 대한 이중배열을 또 만든 이유는 어떤 사람이 어떤 파티에 있는지를 찾는 데에 필요한 시간을 줄이기 위해서이다. 진실을 알고 있는 사람부터 dfs로 탐색하여 그 사람이 속한 파티를 전체 파티에서 제..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제는 DP 유형임을 깨닫고 코드를 적어 제출하기 까지 시간은 얼마 안 걸렸지만 반례를 넘기지 못해서 1시간을 초과해버렸다. 뱀과 사다리 게임은 보드게임 중 하나라고 소개돼있다. 1번 칸부터 100번 칸까지 주사위를 굴려서 1~6칸씩 이동하는데 사다리를 만나면 사다리를 타고 여러 칸을 건너뛰지만 뱀을 만나면 뱀을 타고 여러 칸을 다시 돌아온다. 주..