두두의 알고리즘 (145) 썸네일형 리스트형 [BFS] 백준 14502번 '연구소' (Python) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 가벽 3개를 세울 수 있는 모든 조합을 구한다. 2. 조합 순서대로 가벽을 세우고 바이러스가 퍼진 후의 안전영역을 구한다. 3. 안전영역을 비교하여 제일 큰 안전영역을 구한다. #220328 n,m = map(int,input().split()) graph = [] zero = [] for i in range(n): graph.append(list(map(int,input().split()))) for .. [구현] 백준 15686번 '치킨 배달' (Python) https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 일반 집과 치킨집 좌표 구하기 2. 모든 치킨집 중에서 m개의 치킨집을 뽑는 조합 구하기 3. 조합 하나씩 꺼내서 집마다 가장 가까운 치킨집 거리 구하고 다 더하기 4. 다 더한 치킨집 거리에서 최소 값 구하기 n,m = map(int,input().split()) city = [] chicken = [] home = [] for i in range(n): city.ap.. [구현] 백준 3190번 '뱀' (Python) https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 1. 사과 있는 곳은 1로 표시 2. 방향 지정 함수 만들기 3. q를 사용하여 뱀의 위치 저장. 사과가 없을 때 가장 왼쪽 좌표 제거하면 도미 4. 벽이나 뱀의 몸통과 부딪혔다면 종료 n = int(input()) k = int(input()) data = [[0]*(n+1) for _ in range(n+1)] info = [] for _ in range(k): a,b = map(int,input().. [구현] 난이도2, 이취코 118p '게임 개발' (Python) 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1x1 크기의 정사각형으로 이뤄진 NxM 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 (A,B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로.. [동적계획법] 난이도1.5, Goldman Sachs 인터뷰 '편집 거리' (Python) 두 개의 문자열 A와 B가 주어졌을 때 문자열 A를 편집하여 문자열 B를 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다. 1. 삽입 (Insert) : 특정한 위치에 하나의 문자를 삽입합니다. 2. 삭제 (Remove) : 특정한 위치에 있는 하나의 문자를 삭제합니다. 3. 교체 (Replace) : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다. 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다. 두 문자열 A와 B가 한 줄에.. [동적계획법] 백준 18353번 '병사 배치하기' (Python) https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 가장 긴 증가하는 부분 수열 알고리즘 이용하여 풀 수 있음 n = int(input()) array = list(map(int,input().split()) array.reverse() dp = [1] * n for i in range(1,n): for j in range(0,i): if array[j] < array[i]: dp[i] = max(dp[i], dp[j]+1) pri.. [동적계획법] 난이도1.5, 이취코 223p '바닥 공사' (Python) 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1x2의 덮개, 2x1의 덮개, 2x2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2x3 크기의 바닥을 채우는 경우의 수는 5가지이다. 첫째 줄에 N이 주어진다. (1 [동적계획법] 난이도1.5, 이취코 217p '1로 만들기' (Python) 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다. 1. X가 5로 나누어 떨어지면, 5로 나눈다. 2. X가 3으로 나누어 떨어지면, 3으로 나눈다. 3. X가 2로 나누어 떠러지면, 2로 나눈다. 4. X에서 1을 뺀다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다. 1. 26-1 = 25 2. 25/5 = 5 3. 5/5 = 1 첫째 줄에 정수 X가 주어진다. (1 이전 1 2 3 4 5 6 7 ··· 19 다음