성덕이의 개발공간

1. 문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 한다. 다음과 같은 경우, 구조대 전화번호는 영석이의 전화번호의 접두사이다. 구조대 : 119 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false, 그렇지 않은 true 2. 제한사항 phone_book의 길이는 1 이상 1,000,000 이하 각 전화번호의 길이는 1 이상 20 이하. 같은 전화번호가 중복해서 들어있지 않다. 3. 입출력 예 phone_book return ["119", "97674223", "1195524421"] false ["123","456","789"] true ["12","1..

1. 문제 설명 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant 선수들의 이름이 담긴 배열 completion 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성 2. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하 completion의 길이는 participant의 길이보다 1 작다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있다. 참가자 중에는 동명이인이 있을 수 있다. 3. 입출력 예 participant (참여 선수 명단) completion (완주 선수 명단) return (미 완주 명단) ["leo", "kiki", "eden"] ["ed..

1. 문제 설명 폰켓몬은 종류에 따라 번호를 붙여서 구분한다. 즉, 같은 종류의 폰켓몬은 같은 번호를 가지고 있다. 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 3번 폰켓몬은 2마리 1번, 2번 폰켓몬은 각각 1마리씩 있다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같다. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택 두 번째(1번), 세 번째(2번) 폰켓몬을 선택 두 번째(1번), 네 번째(3번) 폰켓몬을 선택 세 번째(2번), 네 번째(3번) 폰켓몬을 선택 따라서 위 예시의 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 된다. 최대한 ..

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 전형적인 최단 거리 문제이므로 최단 거리 알고리즘을 이용해 해결한다. N의 크기가 최대 100이므로 플로이드 워셜 알고리즘을 이용해도 효율적으로 해결할 수 있다. 플로이드 워셜 알고리즘을 수행한 뒤에 (1번 노드에서 X까지의 최단 거리 + X에서 K까지의 최단 거리)를 계산하여 출력한다. 4. 답안 예시 INF = int(1e9) #무한을 의미 #노드, 간선의 개수를 입력받기 n, m = map(int, input().split()) #2차원 리스트(그래프 표현)을 만들고 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a in ..

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 한 도시에서 다른 도시까지의 최단 거리 문제이다. N과 M의 범위가 충분히 크기 때문에 우선순위 큐를 활용한 다익스트라 알고리즘을 활용 4. 답안 예시 import heapq INF = int(1e9) #무한을 의미 def dijkstra(start): q = [] #시작 노드로 가기 위한 최단 거리는 0으로 설정하여, 큐에 삽입 heapq.heappush(q, (0,start)) distance[start] = 0 while q: #큐가 비어있지 않다면 #가장 최단 거리가 짧은 노드에 대한 정보 꺼내기 dist, now = heapq.heappop(q) #현재 노드가 이미 처리된 적이 있는 노드라면 무시 if distance[now] < dist..

1. 개요 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로디으 워셜(Floyd-Warshall)알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하진 않다. 2차원 테이블에 최단 거리 정보를 저장한다. for문을 3번 사용하므로 많은 노드에서는 비효율 적이다. 다이나믹 프로그래밍 유형에 속한다. 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. a - b의 최단 거리보다 a - k - b가 더 짧은지 검사 점화식 2. 동작 과정 살펴보기 [초기 상태] 그래프를 준비하고 최단 거리 테이블을 초기화한다. 행은 출발노드, 열은 도착노드 1번노드에서 2번..

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 표준 라이브러리 형태로 지원 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나 최소 힙(Min Heap), 최대 힙(Max Heap) 존재 Min Heap = 값이 낮은 값부터 추출 Max Heap = 값이 높은 값부터 추출 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용 리스트는 삽입에 굉장히 빠른 시간이 소요되지만 삭제에는 전체 데이터를 돌아야한다. 힙의 이진트리 형태를 이용한다. 사용예제 1. 최소 힙 import heapq #오름차순 힙 정렬(Heap Sort) def heapsort(iterable): h = [] result = [] #모든 원소를 차례대로 힙에 삽입 for value in iterable: hea..

최단 경로 알고리즘이란 가장 짧은 경로를 찾는 알고리즘 1. 한 지점에서 다른 한 지점까지의 최단 경로 2. 한 지점에서 다른 모든 지점까지의 최단 경로 3. 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 1. 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 음의 간선이 없을 때 작용 그리디 알고리즘으로 분류 매 상황에서 가장 비용이 적은 노드를 선택하는 과정을 반복 1.1 다익스트라 최단 경로 알고리즘 출발 노드를 설정 최단 거리 테이블을 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리..

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 기본 아이디어는 가장 긴 증가하는 부분 수열(LIS) 예를들어 array = {4,2,5,8,4,11,15} 가장 긴 증가하는 부분 수열은 {4,5,8,11,15} [Step 0] 우선 값이 1이 될 수 있도록 모두 1로 초기화한다. [Step 1] 2부터 시작한다. 앞에 4라는 인덱스가 1개존재한다. 점화식에 의해 4는 2보다 크므로 그대로 유지한다. [Step 2] i = 2일 경우를 살펴보자 인덱스2의 값인 5를 확인한다. 4와 비교했을때 5가 크므로 4의 값에 1을 더해 2가된다. 인덱스1의 값인 2를 비교했을때 1

1. 문제 설명 2. 문제 조건 n은 3, m은 4 1 3 3 2 2 1 4 1 0 6 4 7 형태로 되어있다. 3. 문제 해결 아이디어 금광의 모든 위치에 대하여 다음의 세 가지만 고려 1. 왼쪽 위에서 오는 경우 2. 왼쪽 아래에서 오는 경우 3. 왼쪽에서 오는 경우 세 가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 갱신해주어 문제를 해결한다. 이때 테이블에 접근할 때마다 리스트의 범위를 벗어나지 않는지 체크해야 한다. 4. 답안 #테스트 케이스 입력 for tc in range(int(input())): #금광 정보 입력 n, m = map(int, input().split()) array = list(map(int, input().split())) #DP 테이블 초기화 dp = [..