https://www.acmicpc.net/problem/17144 미세먼지가 확산되고 공기청정기가 작동하는 방법을 어렵지 않게 이해할 수 있었다. 해결 순서는 다음과 같다. 1. 미세먼지를 확산시킨다. 2. 공기청정기를 작동한다. 3. 위 과정을 t번 반복한다. 중요한 것은 초기에 미세먼지가 입력되는 위치와 값을 어떤 자료구조에 저장하고 있어야 한다. 만약 현재 위치에 미세먼지가 없었고, 옆방향에서 확산된 미세먼지로 인해 현재 위치에 미세먼지가 생길 수 있는데 이러한 경우는 현재 위치에서 미세먼지 양을 조절하지 않는다. 따라서 입력된 미세먼지의 좌표값과 미세먼지의 양을 큐에 따로 저장한 뒤 큐에서 하나씩 빼가면서 확산시켰다. 확산되는 방향은 상하좌우 4방향이므로 각 위치에서 4번씩만 확인하면 된다. 여..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 문제를 읽었을 때 전반적으로 어렵거나 이해가지 않는 내용은 딱히 없었다. 전체 치킨집에서 M개만큼 선택할 수 있는 모든 경우의 수를 ..

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2, www.acmicpc.net 처음 문제를 이해할 때 드래곤 커브가 다음 세대로 가는 경우 끝 점을 기준으로 시계 방향으로 90도 회전시킨다는 말을 반대로 이해해..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다. 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴 www.acmicpc.net 문제에서 제시한 조건을 정리하면 아래와 같다. - 현재 톱니바퀴가 회전하지 않는다 -> 옆에 있는 톱니바퀴도 회전하지 않는다. (이 ..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net Greedy 알고리즘은 가장 큰 것, 작은 것 등 원하는 방향을 기준으로 규칙을 지키면서 접근하면 된다. 정렬 알고리즘을 함께 사용하는 경우가 많다. 돈을 인출하는데 필요한 시간의 합이 최소값이 되도록 해야 하므로 돈을 인출하는데 가장 많은 시간이 걸리는 사람은 마지막에 인출해야 한다. 마찬가지로 돈을 인출하는데 가장 적은 시간이 걸리는 사람이 가장 먼저 돈을 인출하는 것이 좋다. 따라서 우선 오름차순으로 정렬한 뒤 접근하는 ..

퀵정렬은 분할정복(Divide-Conquer)기법을 이용하여 데이터를 정렬하는 정렬 알고리즘이다.분할정복이란 해결해야 할 부분을 분할하여 문제를 해결하는 방법이다. 퀵정렬은 기준이 되는 pivot을 설정하여 pivot을 기준으로 작은 값은 왼쪽으로 큰 값은 오른쪽으로 이동하여 원소를 정렬한다.pivot의 왼쪽에는 pivot보다 작은 값이 와야하고 pivot의 오른쪽에는 pivot보다 큰 값이 와야 한다. 그래서 Left와 Right를 통해 반대쪽으로 날려보낼 값을 찾을 것이다.또한 Left와 Right가 만나는 지점은 Pivot과 swap이 되는 자리이고 교체된 자리가 기존 pivot값의 올바른 위치가 된다. pivot을 설정하는 방법은 유일하지 않지만 여기선 가운데 위치를 pivot으로 잡았다. 초기상..

이진탐색트리는 이름에서 알 수 있듯이 자식노드를 최대 2개까지만 가지는 이진트리의 특성을 가지고 있으며 다음과 같은 조건을 만족한다. 1. 어떤 노드 V를 기준으로 왼쪽 서브트리의 모든 키값은 V보다 작아야 한다.2. 어떤 노드 V를 기준으로 오른쪽 서브트리의 모든 키값은 V보다 커야 한다.3. 각 노드의 키값은 유일해야 한다. 아래 트리는 이진탐색트리의 모든 조건을 만족한다. 이진탐색트리를 중위순회로 방문하면 오름차순으로 정렬된 값을 얻을 수 있다.1, 2, 4, 6, 8, 9 탐색이진탐색트리는 그 이름에 '탐색'이 있듯 탐색이 효율적이다. 위의 이진탐색트리에서 8을 탐색해보자우선 루트노드 6을 8과 비교했을 때 8은 6의 오른쪽 서브트리에 존재할 것이기 때문에 왼쪽 서브트리는 탐색할 필요가 없다.다음..

힙 정렬은 max-heap 또는 min-heap 자료구조를 이용하여 데이터를 효율적으로 정렬하는 정렬 알고리즘이다. 힙 정렬을 하기 전에 힙의 개념에 대해 간단히 살펴보자 힙(Heap)1. 힙은 완전이진트리 구조를 갖는다.2. 힙은 max-heap, min-heap 둘 중 하나의 특성을 가져야 한다. 완전이진트리를 배열로 구현 시 인덱스를 통해 부모 자식 노드에 바로 접근할 수 있다는 장점이 있다. 여기서 인덱스 0은 사용하지 않는다고 가정한다.자신의 인덱스 i를 기준으로 왼쪽 자식노드의 인덱스는 i * 2, 오른쪽 자식노드의 인덱스는 (i*2)+1을 통해 바로 접근할 수 있다. 또한 자신의 부모노드는 i/2로 바로 접근할 수 있다. 위의 트리는 완전이진트리의 조건을 만족하지만 max-heap이나 min..