문제 해결 포인트 DFS와 BFS의 기본 개념을 알고 있어야 합니다. DFS 1. 깊이 우선 탐색입니다. 2. 어느 한 방향(branch)으로 깊게 탐색하다가 해를 찾지 못하면 부모 노드로 돌아와서 다음 노드를 탐색합니다. 3. 따라서 재귀함수와 스택으로 구현해야 합니다. 4. 현재 방향의 노드들만을 저장하기 때문에 메모리 관리 측면에서는 효율적입니다. 5. 그러나 목표 노드가 너무 깊이 있으면 해를 구하는데 시간이 오래 걸립니다. 6. 한 방향에서 해를 찾으면 바로 빠져나오기 때문에, 다른 방향으로 구하는 해를 검증할 수가 없습니다. 따라서 최적의 해가 아닐 수도 있습니다. BFS 1. 너비 우선 탐색입니다. 2. 노드와 인접한 노드들부터 차례대로 탐색합니다. 3. 따라서 반복문과 큐로 구현해야 합니다..

문제 해결 포인트 모두에게 익숙할 마인크래프트입니다. 높이는 0~256까지 가능합니다. 가로와 세로의 최대 길이는 500입니다. 이 정도의 사이즈라면 높이를 0, 1, 2... 256까지 차근차근 높여보면서, 각 높이의 최소 시간을 계산해보면 될 것입니다. 단, 최소 시간이 겹친다면 높이가 높은 쪽을 골라야 합니다. 즉, 모든 경우에 대해 빠짐없이 검사해보는 브루트포스 방법을 사용해야합니다. 코드 작성 from sys import stdin N, M, B = map(int, stdin.readline().split()) heights = [] for _ in range(N): heights += list(map(int, stdin.readline().split())) heights.sort(reverse..

문제 해결 포인트 높이가 몇일 때 나무의 잘린 부분의 합이 M이 되는지 계산해야되는 문제입니다. 높이를 1씩 올리면서 언제쯤 최적화가 되는지 확인할 수도 있지만, 주어진 숫자가 너무 크기 때문에 시간초과가 나게 됩니다. 높이를 1씩 올린다는 아이디어는 탐색과 관련이 있습니다. 또한 나무들의 최소 높이와 최대 높이가 정해져 있기 때문에 높이를 무한정 높이는게 아니라 정해진 범위 내에서 탐색한다는 사실을 알 수 있습니다. 바로 여기에서 이분탐색의 아이디어를 떠올려야 합니다. 이분탐색 시간복잡도: O(logn) 범위를 절반씩 줄이면서 탐색합니다. 또한 리스트 내의 자료들이 정렬되어있어야 탐색이 가능합니다. 오름차순으로 자료가 정렬되어 있다고 가정할 때, 1. 찾아야되는 자료가 mid와 같은 지 확인합니다. m..

1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 해결 포인트 문제를 풀기 위해 스택 자료구조를 사용하지만 생각해볼 점이 많습니다. Pop이 발생한 뒤의 스택 상태는? Pop 이후 Push를 할 때 어떤 수가 입력되어야 할까? 어떤 경우에 수열 생성이 불가능할까? 스택은 Last-in, First out(LIFO) 자료구조입니다. 가장 최근에 입력된 값이 제일 먼저 출력되며 가장 먼저 입력된 값은 가장 나중에 출력됩니다. 예..

문제 해결 포인트 가장 먼저 떠오르는 아이디어는 리스트에 N개의 수를 모두 넣은 뒤 split()와 sum()을 이용하는 방법일 것입니다. 그러나 sum()은 iterator를 이용하여 리스트의 원소를 하나하나 순회하면서 덧셈을 하기 때문에, M개의 입력의 각각에 대하여 sum()을 하게 된다면 시간복잡도는 O(MN)이 되어 시간초과가 발생합니다. 따라서 덧셈부분을 최적화해야하는데 여기에는 간단한 수학 지식이 사용됩니다. 바로 부분합을 빼면 일반항이 나온다는 사실인데 고등학교때 다들 한번쯤은 들어보셨을겁니다. 코드 작성 N개의 수를 입력 받으면서 S0, S1, S2 ...를 차례대로 리스트에 넣어줍니다. 이후 M개의 케이스를 입력받으며 부분합끼리 빼서 일반항들의 합을 구합니다. 주의해야 할 점은 부분합 ..

문제 해결 포인트 회의를 하는 시간이 겹치지 않도록 최대한 많이 회의실을 사용해야 합니다. 이 조건으로 생각해볼 수 있는 아이디어는 다음과 같습니다. 회의에 걸리는 시간이 작은 순으로 정렬? 회의가 시작하는 시간이 빠른 순으로 정렬? 회의가 끝나는 시간이 빠른 순으로 정렬? 조금만 생각해보면, 회의가 끝나는 시간이 시작하는 시간보다 훨씬 중요하며 다음 회의가 시작하는 시간은 현재 회의가 끝나는 시간보다 늦거나 같아야 합니다. 새로운 회의시간이 길든 짧든 어차피 기존의 회의가 끝나는 시간보다는 새 회의의 시작시간이 늦어야 회의실을 빌리는게 가능하기 때문에, 회의시간의 길이는 생각보다 중요하지 않습니다. 단, 시작과 동시에 회의가 끝날수도 있으며 이 회의는 특별하게 다뤄야 합니다. 이 회의는 여러번 해도 겹..