기록

문제 보기 이 문제는 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..

문제 보기 이 문제는 브루트 포스 문제이다. 2차원 배열에 존재하는 CCTV의 가능한 모든 방향을 다 고려한 후 사각지대의 최소 크기를 출력하면 된다. 1번 -> 상, 하, 좌, 우 2번 -> (상, 하), (좌, 우) 3번 -> (상, 우), (우, 하), (하, 좌), (좌, 상) 4번 -> (좌, 상, 우), (상, 우, 하), (우, 하, 좌), (하, 좌, 상) 5번 -> (상, 하, 좌, 우) 5가지 CCTV가 움직일 수 있는 방향은 위와 같으며 코드 상에서 반복적으로 나오는 부분이 많아서 코드의 길이가 길다. 코드 import sys import copy def dfs(idx): global min_area, arr if idx == len(position): temp = 0 for i in..

문제 보기 이 문제는 bfs 문제이다. 물의 이동과 고슴도치의 이동 순서만 잘 고려해 준다면 어렵지 않게 풀 수 있다고 생각한다. 알고리즘의 순서는 아래와 같다. 1. 물의 이동을 수행한다. 2. 고슴도치가 이동할 수 있는 구간을 파악한 후 이동시킨다. 3. 1 ~ 2 의 과정을 도착지에 도달하거나, 더 이상 이동할 곳이 없을 때까지 진행한다. 코드 import sys from collections import deque def bfs(): position = deque() # 이동 경로 water = deque() # 물의 위치 for i in range(R): for j in range(C): if arr[i][j] == "*": water.append([i, j]) elif arr[i][j] == ..

문제 보기 이 문제는 브루트 포스 문제이다. case를 두 가지로 나누고 브루트 포스를 진행하면 된다. case 1 - abs(N - 100)의 값을 구한다. (채널 100번에서 +,- 버튼만 채널을 이동하는 것이다) case 2 - 0번부터 1,000,000까지 브루트 포스를 진행한다. (이동하려고 하는 채널의 최댓값이 500,000 이기 때문에 500,000 보다 크면서 모든 숫자의 경우의 수를 거치는 1,000,000까지를 범위로 잡았다. 코드 if __name__ == "__main__": enable = {str(i) for i in range(10)} # 0, 1, 2 ... 9 (가능한 수) # input N = int(input()) # 이동하려고 하는 채널 M = int(input()) ..

문제 보기 이 문제는 다익스트라 문제이다. 최근 코딩 테스트에서 자주 출제되는 유형이기 때문에 알아둘 필요가 있다고 생각한다. 알고리즘 순서는 다음과 같다. 1. 입력(노드, 간선, 시작 지점, 도착 지점)을 받는다. 2. 1차원 배열에 거리의 값을 무한대로 초기화해서 저장한다. (시작 위치는 0으로 초기화한다.) 3. 우선 순위 큐를 사용해서 최단거리에 있는 노드를 선택하고 그 노드와 인접된 노드까지의 거리를 계산한다. - 이미 계산한 거리보다 더 작은 거리 값이 나온다면 값을 업데이트하고 인접한 노드를 우선순위 큐에 추가한다. 4. 우선순위 큐가 빌 때까지 3번 과정을 반복한다. 다익스트라를 구현하면서 왜 우선순위 큐를 사용하는지 궁금하였다. bfs 대신에 다익스트라를 구현했다는 자체만으로도 엄청난 ..

문제 보기 이 문제는 시뮬레이션 문제이다. 삼성 기출문제는 대부분 bfs로 풀거나 지도에서 움직이는 형태가 많은 것 같다. 이 문제 또한 지도에서 움직이는 형태이다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. - 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. - 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. - 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 문제에서 요구하는 사항을 하나씩 완성시키면 쉽게 구현할 수 있다. 알고리즘 수행 과정은 아래와 같다. 1. 2차원 배열(N x N)을 만든다. (0으로 초기화) 2. 사과의 위치에 1을 저장한다. 3. (0, 0)에서 뱀은..

문제 보기 이 문제는 큐(queue) 문제이며, 문제 이름을 통해서도 유추가 가능하다. 큐는 먼저 집어넣은 데이터가 먼저 나오는 FIFO 구조로 저장하는 형식을 말한다. 문제를 구현하는 알고리즘은 크게 어렵지 않았다. 문제에서 요구하는 6가지 명령을 구현하면 된다. push와 pop은 이미 구현된 append, popleft를 활용하였으며, size와 empty는 원소의 개수를 세는 변수(count)를 따로 둬서 구현하였다. front와 back은 큐가 비어있는지 확인하고 출력하면 된다. 명령 구현 push append pop popleft size count 활용 empty count 활용 front 단순 출력 back 단순 출력 코드 from collections import deque import ..

문제 보기 이 문제는 완전 탐색 문제이다. 치킨 집의 위치 중에서 M개를 고른 모든 경우의 수를 탐색하면 된다. 알고리즘 순서는 다음과 같다. 1. 치킨 집의 위치를 저장한다. 2. 치킨 집의 위치 중 M개를 고른다. (조합) 3. 치킨 거리를 계산하고 최솟값을 계속해서 업데이트한다. - (x1, y1)과 (x2, y2) 거리 -> abs(x2 - x1) + abs(y2 - y1) 코드 import itertools, sys, copy if __name__ == "__main__": N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] # 치킨집 탐색 chicken = [] for i in ran..

문제 보기 주사위 굴리기는 시뮬레이션 문제이다. 문제 구현 순서는 아래와 같다. 1. N x M 지도에서 주사위를 이동시키면서 주사위 값의 변화를 파악 2. 지도에 있는 값과 주사위의 값을 상황에 맞게 복사 - 지도에 있는 값이 0일 때 주사위의 값을 지도로 복사한다. - 지도에 있는 값이 0이 아닐 때 지도에 있는 값을 주사위로 복사하고 지도에 있는 값을 0으로 수정한다. 3. 주사위 윗 면에 쓰인 수 출력 [ 값의 변화 파악 ] 4가지 방향으로 주사위가 이동할 때 주사위의 값을 유지하면서 모양을 바꾸는 것이 핵심이었다. 아래는 주사위 이동에 대해서 정리한 표이다. 동 서 북 남 1 - >3 1 -> 4 1 -> 2 1 -> 5 2 -> 2 2 -> 2 2 -> 6 2 -> 1 3 -> 6 3 -> 1..