기록

문제 보기 이 문제는 Stack 문제이다. 처음에는 완전 탐색 방식으로 구현하였는데, 역시나 시간 초과가 발생하였다. 예제로 주어진 6, 9, 5, 7, 4를 오른쪽부터 읽는 것이 아니라 왼쪽부터 읽는 방법이 없을까 생각해보았다. 그 결과 빈 스택(리스트)을 선언한 후 왼쪽부터 값을 삽입하면서 의미 없는 탑들은 제거하는 방식이 어떨까?라는 결론을 내었다. 6, 9, 5, 7, 4를 예로 들면 수행 과정은 다음과 같다. stack = [ ] -> 최댓값을 저장할 스택 answer = [ ] -> 수신 탑 인덱스 저장 1. 처음 스택은 비어있기 때문에 최댓값이 0인 상황이다. 따라서 6을 수신할 수 있는 탑이 존재하지 않기 때문에 answer에 0을 삽입하고, stack에는 인덱스와 6의 값을 삽입한다. s..

문제 보기 이 문제는 BFS 문제이다. 입력받은 두 수에서 첫 번째 값을 기준으로 BFS 탐색을 진행하면 된다. 알고리즘 순서는 다음과 같다. 1. 첫번째 값을 큐에 넣는다. 2. 큐에 들어있는 값을 가져와서 한 자리씩 값을 수정해보고 소수 조건에 부합한다면 큐에 추가한다. 3. 2번의 과정을 두 번째 수를 찾을 때까지 진행한다. 알고리즘은 위와 같이 구성하였고 값을 한자리씩 수정하기 위해서는 Int -> String으로 변환해주는 별도의 과정이 필요했다. 이외에는 기존의 BFS동작 방식과 큰 차이가 없었다. 코드 import math, copy from collections import deque def prime_check(n): # n값이 소수인지 확인 for i in range(2, int(mat..

문제 보기 이 문제는 시뮬레이션 문제이다. 문제를 읽고 어떤 알고리즘을 사용해야 할지 바로 떠오르지 않았다. 10분 넘게 고민하여도 도저히 생각이 안 났다. 완전 탐색을 하면 경우의 수가 너무 많아서 시간 초과가 날 것 같았지만 다른 방법이 떠오르지 않았다. 운이 좋은건지는 모르겠지만 정답은 완전 탐색이었다. [ 케이스 분류] 문제에서 요구하는 정답이 1, 2, 3 혹은 -1(추가 x, 추가 4개 이상)이기 때문에 5가지로 분류하였다. 1. 가로선 추가 x 2. 가로선 1개 추가 3. 가로선 2개 추가 4. 가로선 3개 추가 5. 그 외 [ 가로선 추가 관리 ] 가로선을 추가하기 위해서 가로선을 추가할 수 있는 구간을 따로 저장하였다. 저장한 구간에서 파이썬 내장 함수 combination을 사용하여 1..

문제 보기 이 문제는 DFS 문제이다. DFS를 구현하는 것은 어렵지 않았으나, 시간 초과를 해결하는 부분이 쉽지 않았다. 알고리즘 1번부터 N번까지 순서대로 탐색을 시작한다. 해당 번호에서 DFS 탐색을 시작한다. (지나간 부분은 같은 팀으로 가정) 위에서 탐색한 방향의 역순으로 탐색하면서 사이클을 확인한다. (-1을 대입) 역순으로 탐색하면서 -1로 채워지지 않은 부분은 팀을 이루지 못한 것이라고 생각하면 된다. 처음에는 역순으로 탐색하지 않고, 팀을 관리하는 별도의 배열을 만들어서 append, in 연산자를 활용하였다. 그 결과 80%에서 시간 초과가 발생하였다. 시간을 절약하면서 최소한의 탐색을 할 수 있는 방법이 무엇이 있을까 생각해보니 역순으로 탐색하는 방법이었다. 코드 import sys ..

문제 보기 이 문제는 시뮬레이션 문제이다. 문제에서 주어진 순서와 조건에 맞게 그대로 구현하면 된다. 순서는 미세먼지 확산, 공기청정기 작동 순서이며 조건은 미세먼지가 확산될 때 주의할 것이 있었다. 문제 접근 미세먼지 확산을 구현한 후 공기정청기를 구현하고자 하였다. 미세먼지 확산은 동시에 일어나기 때문에 두 개의 배열을 활용하고자 하였다. - 확산이 일어나는 즉시 값을 업데이트하면 오류가 나기 때문이다. 배열을 탐색하면서 배열 값이 5 이상인지 파악한다. - 5 이상이면 상, 하, 좌, 우에 공기청정기가 있는지 탐색하고 확산을 진행한다. 확산이 모두 끝난 후, 원래 배열 값에 확산 과정에서 따로 저장했던 배열 값들을 반영한다. 공기청정기는 상, 하 따로 관리한다. - 상은 시계 방향, 하는 반시계 방..

문제 보기 이 문제는 DP 문제이다. LCS(Longest Common Subsequence, 최장 공통부분 수열)는 DP 문제로 유명하기 때문에 문제 이름을 보자마자 DP임을 유추할 수 있었다. 문제 접근 2차원 dp를 활용하고자 하였다. 행은 첫 번째 문자열, 열은 두 번째 문자열에 대한 정보를 나타낸다. dp [row][col] - 첫 번째 문자열 row 길이, 두 번째 문자열 col 길이에 해당하는 문자열로 만들 수 있는 공통부분 수열 알고리즘 첫 번째 문자열과 두 번째 문자열 길이를 이용해서 2차원 for문을 돈다. - 바깥쪽 for문은 첫 번째 문자열 인덱스(i)를 나타낸다. - 안쪽 for문은 두 번째 문자열 인덱스(j)를 나타낸다. 첫 번째 문자열의 i번째와 두 번째 문자열의 j번째의 문자..

문제 보기 이 문제는 BFS 문제이다. (+ 시간 초과) 백준 문제를 풀면서 시간제한이 6초인 문제는 처음 봤다. 하지만 6초라는 시간도 짧았다. 이 문제는 BFS를 구현하는 것보다 시간을 단축시키는 아이디어가 더 중요하였다. 문제 접근 입력받는 A 값을 큐에 삽입한다. A를 이용해서 D, S, L, R 과정을 수행해보고 가능한 경우는 결괏값을 큐에 삽입한다. 목푯값을 만날 때까지 위 과정을 진행한다. D와 S과정은 시간 초과와 별 상관없어 보였지만 L, R은 어떻게 수행하냐에 따라서 시간과 밀접한 연관이 있을 것이라고 생각했다. 제일 먼저 문자열 연산으로 접근하였지만 시간 초과가 발생하였다. 결국 수식을 활용해서 구하는 해답을 찾아내었으며 통과하였다. 알고리즘 입력받은 A 값을 큐에 삽입한다. 큐의 제..

문제 보기 이 문제는 BFS 문제이다. 문제 접근 현재 층을 큐에 삽입한 후 상, 하로 움직이면서 목표층에 도달할 수 있는지 파악한다. 도달하는 경우 움직인 최솟값을 출력한다. 도달하지 못하는 경우 use the stairs를 출력한다. 알고리즘 현재 층을 큐에 삽입한다. 큐의 제일 앞부분을 pop 한 후 상, 하로 움직일 수 있는지 파악한다. 위의 과정을 목표층을 찾거나, 큐가 빌 때까지 진행한다. 코드 from collections import deque def bfs(F, S, G, U, D): q = deque([[S, 0]]) visited = {S} while q: floor, cnt = q.popleft() if floor == G: # 목표 층에 도착 return cnt if floor +..

문제 보기 이 문제는 BFS 문제이다. 처음에 문제를 읽으면서 보물의 위치도 따로 구해야 하는지 고민하였다. 보물의 위치를 구하기 위해서 플로이드 알고리즘을 사용하려고 하였으며 보물의 위치를 구하면 거리는 BFS로 간단히 구할 수 있다고 생각했다. 하지만 문제를 다시 읽어보니 보물의 위치는 따로 구할 필요가 없었다. 보물의 위치는 두 곳 사이의 거리가 최대인 곳이다. 따라서 2차원 배열에서 육지인 곳을 시작점으로 모두 탐색해보면서 가장 거리가 먼 값을 구하면 된다. 알고리즘 모든 L값을 시작점으로 하여 다른 L과의 거리를 구한다. (BFS) 위에서 구한 거리와 현재까지 구한 거리를 비교하며 값을 업데이트한다 코드 import sys from collections import deque # 상 하 좌 우 ..

문제 보기 이 문제는 bfs 문제이다. (+시간 초과 해결) 문제 접근 인구 차이를 통해서 국경선을 열고 닫으며, 몇 번의 인구 변화가 일어나는지 파악하는 문제이다. 국경선을 열 때마다 인구 변화를 일으키는 것이 아니라 전체 국경선 형태를 파악한 후 한 번에 값을 업데이트한다. (시간 초과 관련) 국경선을 열 수 없을 때까지 진행한다. 알고리즘 현재 위치에서 지나갈 수 있는 집합을 파악한다. (원소 위치, 원소 개수, 원소 합) - bfs 1번의 과정을 전 구간에 실시한다. 값을 업데이트하고 다시 1번으로 돌아간다. 만약 업데이트할 값이 없다면 종료한다. 코드 import sys from _collections import deque # 상, 하, 좌, 우 dy = [-1, 1, 0, 0] dx = [0..