후회가 없도록

문제 출처: https://www.acmicpc.net/problem/1012 1. 결과 1) BFS 이용: 메모리 32124KB, 시간 104ms 2) 스택으로 구현한 DFS 이용: 메모리 29452KB, 시간 88ms 2. 풀이 이 문제는 비교적 평범한 DFS 문제라고 생각한다. 전체 좌표를 탐색하다가 만약 1(배추가 심어진 곳)을 발견하면 이와 상, 하, 좌, 우로 연결된 모든 배추 좌표를 방문하고, 이 전체를 배추흰지렁이 한 마리로 해결할 수 있다. 즉, 방문한 적이 없는 1을 발견하면 필요한 배추흰지렁이의 수를 1만큼 추가하고, 값을 1을 가지면서 해당 위치와 상, 하, 좌, 우로 연쇄적으로 연결된 모든 좌표들을 방문한 상태로 바꾸면 된다. 하지만 이를 재귀로 구현한 DFS를 이용하면 재귀 오류..

문제 출처: https://www.acmicpc.net/problem/1655 1. 결과 메모리 35032KB, 시간 272ms 2. 풀이 이 문제는 N개의 숫자가 각각 입력될 때마다, 입력된 숫자들 중에서 중간값을 출력해야 한다. 평균값이나 누적 합이 아니기 때문에 각각의 값이 살아서 존재해야 하고, 값이 새로 입력될 때마다 정렬이 수행되어야 중간값을 구할 수 있다. 하지만 값이 추가될 때마다 정렬(sort)이 발생하고, 이런 과정이 N번 반복된다면 시간 복잡도는 커질 수밖에 없다. 이를 더 효율적인 방법으로 풀기 위해서는 최대 힙과 최소 힙을 함께 응용하는 방법이 있다. 우선, 최대 힙과 최소 힙이 의미하는 바를 이해해야 하는데, 최대 힙은 [0] 번째 원소부터 내림차순으로 저장 혹은 출력되는 자료구..

문제 출처: https://www.acmicpc.net/problem/11279 1. 결과 메모리 35124KB, 시간 152ms 2. 풀이 이 문제는 우선순위 큐를 이용해서 풀 수 있는 문제다. 먼저, 우선순위 큐란 우선순위가 높은 원소가 먼저 출력되는 추상적 자료형을 이야기하는데, 쉽게 보면 자료형에 자료를 저장할 때, 스스로 각 자료에 우선순위를 부여하며 저장하는 것이다. 그리고 자료를 다시 하나씩 출력할 때, 그 우선순위가 높은 것을 먼저 순서대로 출력하는 것인데, 자세한 내용은 아래 링크의 글을 통해 확인할 수 있다. https://chanhuiseok.github.io/posts/ds-4/ 자료구조 - 우선순위 큐(Priority Queue)와 힙(heap) 컴퓨터/IT/알고리즘 정리 블로그 ..

문제 출처: https://www.acmicpc.net/problem/2667 1. 결과 1) BFS 이용: 메모리 32108KB, 시간 96ms 2) DFS 이용: 메모리 29304KB, 시간 76ms 2. 풀이 이 문제는 전형적인 그래프 탐색 문제이다. 그래프 탐색은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 두 가지가 있는데, 비교적 간단한 문제는 두 방법 모두 가능하다. 여기서 잠깐 둘의 차이를 짚고 가면, BFS는 최적, 최단과 같은 요소를 구할 때 유용하고, DFS는 특정 경로나 요소에 대해 끝까지 경우를 끝까지 탐색해볼 때 유용하다. 그런 부분에서 이 문제는 DFS가 더 적합하다고 볼 수 있다. 특정 영역에 대해 끝까지 탐색한 넓이를 구하는 것이기 때문이다. 위의 결과에서도 알 수 ..

문제 출처: https://www.acmicpc.net/problem/5430 1. 결과 메모리 46428KB, 시간 336ms 2. 풀이 이 문제는 우선 입력과 출력 예시를 통해 확인할 수 있겠지만, 예시처럼 입력을 받아서 원하는 형태의 숫자로 변환하는 것, 출력을 원하는 형식대로 출력하는 것이 생각보다 고민이 됐다. 그래서 아래 코드처럼 입력과 출력이 조금은 더 길다. 본격적인 문제의 아이디어는 결국 뒤집든 안 뒤집든 한쪽 끝에서 숫자를 제거한다는 점에서 떠올렸다. 만약 스택의 형태로 풀었다면, D일 때는 [1:]로 슬라이싱을, R일 때는 reverse 정렬을 하게 되는데, 이는 슬라이싱을 할 때마다 남은 길이만큼 연산(한 칸씩 앞으로 당기는 것)이 발생하고, R이 있을 때마다 정렬이 발생한다는 뜻이..

문제 출처: https://www.acmicpc.net/problem/17298 1. 결과 메모리 153484KB, 시간 1212ms 2. 풀이 처음에는 이 문제를 이중 for문을 통해 각 자리의 숫자(i번째)마다 이후의 숫자(i+1번째부터 n번째까지)를 탐색하며 큰 수가 있다면 이를 저장하며 break, 없다면 끝까지 탐색 후 -1을 추가하게 되는 방법으로 작성했다. 이 경우는 답은 도출이 되었지만 시간 복잡도가 크게(O(N^2)) 발생되었다. 다른 풀이로는 먼저 첫 숫자에 대해 나머지 숫자를 탐색하며 첫 숫자보다 큰 숫자가 있다면 해당 숫자를 스택에 저장하고, 두 번째 숫자부터 모두 해당 숫자보다 작다면 스택의 마지막 숫자를 그대로 또 추가하는 방식을 적용해봤다. 만약 스택의 마지막 숫자보다 현재 숫..

문제 출처: https://www.acmicpc.net/problem/6549 1. 결과 메모리 44580KB, 시간 3468ms 2. 풀이 우선 풀었을 때, 첫 플래티넘 문제라는 것이 신기하고 좋았다. 분할 정복법의 큰 틀에서 벗어나지 않은 형식인 것 같은데, 의외로 난이도가 있었다는 이야기 같다. 말한 대로 이 문제는 재귀를 통한 분할 정복법을 이용한다. 주어진 높이 리스트를 반을 가른 후, 그 반의 왼쪽에 있는 높이들 중에서 가장 큰 넓이, 반의 오른쪽에 있는 높이들 중 가장 큰 넓이, 그리고 가운데 선을 포함하여 가장 큰 넓이를 각각 구한다. 그리고 이 셋 중 가장 큰 넓이를 반환하면 된다. 왼쪽과 오른쪽의 높이들에는 다시 이 함수를 재귀로 적용시키면 된다. 이 문제의 등급을 플래티넘으로 올리는데..

문제 출처: https://www.acmicpc.net/problem/18258 1. 결과 메모리 92936KB, 시간 1764ms 2. 풀이 이전에 풀었던 큐 문제에서 이번엔 시간제한이 추가되었다. 문제 설명에서는 시간 복잡도가 O(1)이어야 한다고 제시했다. 연결 리스트를 통한 큐는 비교적으로 삽입, 삭제 등의 연산에서 유리하다고 생각했기 때문에 이전에 연결 리스트로 구현한 큐 코드를 그대로 제출했다. 하지만 이 코드가 시간 초과가 발생했다. 최대한 메모리와 연산을 줄여서 구현한 연결 리스트와 큐인데도 시간 초과가 발생했다. 이전에 패키지 collections에서 deque라는 자료구조가 큐를 구현한 것이고, queue 라이브러리의 Queue보다도 연산이 빠르다는 것을 들었기 때문에 이번엔 deque..

문제 출처: https://www.acmicpc.net/problem/10845 1. 결과 메모리 29200KB, 시간 80ms 2. 풀이 문제에서 제시한 연산 6개를 수행할 수 있는 기본적인 자료구조 큐를 구현해보는 문제였다. 큐는 FIFO(First In First Out), 선입선출의 특징을 갖는 자료구조로써, 말 그대로 먼저 들어온 자료가 먼저 출력되는 형태이다. 현실에서는 선착순, 은행 대기줄 등의 상황을 예시로 들 수 있다. 파이썬에서 제공하는 자료 타입인 리스트(list, 자료구조인 리스트와는 다른 것)로도 구현할 수 있는데, 기본적으로 파이썬의 리스트 타입은 자료구조 중 '배열'이고, 그중에서도 기본적으로는 스택을 구현한 형태를 갖는다. append를 하면 가장 뒤에 쌓이고, pop을 하면..

문제 출처: https://www.acmicpc.net/problem/1260 1. 결과 메모리 33100KB, 시간 144ms 2. 풀이 DFS와 BFS 모두 가능한 각 경로를 탐색하는 방법이지만, DFS는 루트 노드에서 시작하여 일단 하나의 분기를 끝까지 탐색해본 후, 다시 직전에서 다른 것을 탐색하는 방식이고, BFS는 루트 노드에 연결된 모든 자식 노드를 탐색, 이후 그 자식 노드의 자식 노드들을 탐색하는 방식으로 루트로부터 떨어진 높이마다 해당 높이에서 가능한 경우를 모두 탐색한다. 이런 특징 때문에 DFS는 특정 경로를 찾아내는 문제, 순열이나 조합 등을 찾을 때 주로 사용하고, BFS는 최단 거리를 찾을 때 주로 사용한다고 한다. 일단 이 문제는 간단한 DFS, BFS 구현이 요점이기 때문에..