개발일지

[인프런] 뮤직비디오(이분탐색 알고리즘) - 파이썬

문제 지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지 되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. 지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기 로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고..

알고리즘 2022. 6. 3. 20:18

다익스트라(dijkstra) 알고리즘

🚀 다익스트라 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘으로 분류된다. 최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신하는 특징이 있다. 과정 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 위 과정 3과 4번을 반복한다. 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾기 때문에 마지막 노..

알고리즘 2021. 12. 23. 02:13

[백준] 2447번 [재귀함수] 별 찍기 - 10

📌 [백준 2447번 별 찍기 - 10] 문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. 입력 첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3^k이며, 이때 1 ≤ k < 8이다. 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 예제 입력 1 27 예제 출력 1 **..

알고리즘/백준 2021. 12. 15. 02:06

[백준] 2343번 [이분탐색] 기타 레슨

📌 [백준 2343번 기타레슨] 개념 🌈 이진탐색(binary search) BigO : O(log N) 정렬된 자료를 반으로 나누어 탐색하는 방법 오름차순 정렬된 자료에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다. 재귀 def binary_search(array,target,start,end): if start > end: return None mid = (start+end) // 2 if array[..

알고리즘/백준 2021. 12. 13. 22:16

[백준] 1002번 [기본수학2] 터렛

📌 [백준 1002번 터렛] 이 문제는 (x1, y1), (x2, y2)가 주어졌을 때 첫 번째 점에서의 거리 r1과 두 번째 점에서의 거리 r2가 주어졌을 때, 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성해야 합니다. import math n = int(input()) for i in range(n): x1,y1,r1,x2,y2,r2 = map(int,input().split(" ")) # (x1,y1)과 (x2,y2) 사이의 거리 r = math.sqrt((x1-x2)**2+(y1-y2)**2) # 두 원이 만나지 않는 경우 if (0 r1+r2: print(0) # 두 원이 한 점에서 만나는 경우(외접,내접) elif (r == abs(r1-r2) and r!=0) or r == r1+r2:..

알고리즘/백준 2021. 12. 8. 01:24

[백준] 3055번 [bfs] 탈출

📌 [백준 3055번 탈출] BFS 너비 우선 탐색(Breadth First Search) 가까운 노드부터 탐색하는 알고리즘이며 동작 원리는 큐이다. 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리이다. 장점으로는 노드의 수가 적고 깊이가 얕은 경우 빠르게 동작할 수 있다. 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠르다. 너비를 우선 탐색하기에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장한다. 최단 경로가 존재한다면 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다. 단점은 재귀 호출의 DFS와는 달리 큐에 다음에 탐색할 정점들을 저장하므로 저장공간이 많이 필요하다. 노드의 수가 늘어나면 탐색해야 하는..

알고리즘/백준 2021. 12. 6. 00:42