Python

[python] 백준 - 1916. 최소비용 구하기

🤔문제 해결 G5 | 다익스트라, 그래프 하나의 정점에서 다른 모든 정점들의 최단 경로를 구하는 알고리즘 간선, 최소 등등 말이 나오면 다익스트라? 나의 경우 다익스트라를 풀 때 항상 우선순위 큐를 이용한다. (파이썬의 힙큐를 사용) A 에서 갈 수 있는 모든 정점들의 최소비용을 리스트에 담아두고 B 지점을 답으로 출력한다. 먼저 (가중치, 시작점)을 힙큐에 넣고 시작한다. 시작점에서 각 정점까지의 비용은 가장 큰 값(파이썬에서 float('inf')를 넣어두고 시작한다.) 힙큐에서 값을 하나씩 꺼낸다. 꺼낸 정점에서 이웃한 정점들 중에서 아직 방문하지 않았고, 이웃한 정점까지의 비용보다 현재비용 + 꺼낸 정점에서 이웃한 정점까지의 간선비용이 작으면 각 정점까지의 비용을 현재비용 + 꺼낸 정점에서 이웃한..

선택 정렬(selection sort)

📔 선택 정렬(selection sort) 이란 오름차순의 경우 가장 작은 원소를 맨 앞으로 보낸다. 2개의 반복문을 중첩해서 구현하기 때문에 시간복잡도는 O(n^2) 한 세트가 끝날 때마다 가장 작은 수가 맨 앞에 온다. 📔 선택 정렬(selection sort) 예제 위의 예제는 오름차순일 경우의 예제이다. 5개의 원소중 가장 작은 숫자를 맨 앞의 숫자와 바꾼다. 1세트가 끝나면 가장 작은 수가 맨 앞으로 온다. 다음 세트부터는 맨 앞의 숫자를 빼고 비교를 해준다. (이미 가장 작은 수이기 때문) 📔 선택 정렬(selection sort) 구현 numbers = [5, 3, 8, 1, 2] print(f'정렬 전: {numbers}') print() for i in range(len(numbers))..

[python] 백준 - 2225. 합분해

🤔문제 해결 G5 | dp, 조합론 DP는 역시 손으로 해야 제맛이다. 예시의 20, 2는 너무 크기 때문에 6, 4로 바꿔서 구해봤다. 열은 N 행은 K이다. 즉 2열 3행은 2를 숫자 3개로 만드는 방법의 가짓수다. 딱 보면 규칙이 보일 것이다. i, j 는 i-1,j 와 i,j-1의 합이라는 것을... 원래의 규칙은 경우의 수를 모두 직접 구해보면 3열4행을 구할 때는 3행의 0~4열까지의 숫자를 더한 값이다. 그 이유는 0을 숫자 2개로: (0,0) 1을 숫자 2개로: (0,1), (1,0) 2를 숫자 2개로: (0,2), (1,1), (2,0) 각각의 경우의 수 뒤에 2, 1, 0 을 붙여주면 숫자 2를 3개로 구성하는 경우의 수는 6이 나온다. 💨 💻소스 코드 N, K = map(int, in..

[python] 백준 - 9251. LCS

🤔문제 해결 G5 | 다이나믹프로그래밍, 문자열 LCS란 최장 공통 부분 문자열(Longest Common Subsequence)이다. 순서는 맞지만 연속하지 않아도 되는 같은 문자열을 찾는 것이다. 예를 들어 ABCAB와 BDCB가 있다. ABCAB 와 BDCB 의 LCS는 BCB이다. LCS가 뭔지 안다고 해도 처음 접하면 구하는건 당연히 어렵다. 완전탐색을 하려고 했지만 역시나 시간초과가 발생했다. 문제 해결법이 DP이고 다른 고수들의 풀이방법을 참고해서 해결했다. 먼저 위와 같이 DP를 구성한다. 먼저 1번 째 행을 채워보면 AC와 C가 만나서 LCS는 1이다. 두번 째 행을 보자. A와 CA가 만나서 LCS는 1이다. ACA와 CA가 만나서 LCS는 2이다. 세번 째 행을 보자. A와 CAP =..

[python] 백준 - 11497. 통나무

🤔문제 해결 S1 | 정렬, 그리디 알고리즘 왼쪽과 오른쪽 끝을 최솟값으로 점점 채우는 방식으로 문제를 해결했음 리스트에서 최솟값을 꺼내는 방법은 힙큐를 사용 예시 [1, 2, 3, 4, 5, 6, 7] 위의 그림을 보면 가장 앞의 1과 가장 뒤의 2의 차이도 최소로 할 수 있음 다음 리스트 앞뒤로 값의 차이의 최댓값을 답으로 저장 💨 💻소스 코드 import heapq def solution(N, logs): heapq.heapify(logs) my_logs = [0] * N left = 0 right = -1 for _ in range(N // 2): my_logs[left] = heapq.heappop(logs) my_logs[right] = heapq.heappop(logs) left += 1 r..

버블 정렬(bubble sort)

📔 버블 정렬(bubble sort) 이란 서로 인접한 두 원소의 대소를 비교하여 정렬하는 알고리즘 2개의 반복문을 중첩해서 구현하기 때문에 시간복잡도는 O(n^2) 오름차순의 경우 1세트(바깥쪽 반복문)이 끝나면 가장 큰 수가 맨 뒤에 오게 된다. 내림차순의 경우 반대 📔 버블 정렬(bubble sort) 예제 위의 예제는 오름차순일 경우의 예제이다. 앞뒤의 숫자를 비교해서 앞의 숫자가 크면 뒤의 숫자랑 바꾼다. 1세트가 끝나면 가장 큰 수가 맨 뒤로 온다. 다음 세트부터는 맨 뒤의 숫자를 빼고 비교를 해준다. (이미 가장 큰 수이기 때문) 📔 버블 정렬(bubble sort) 구현 numbers = [5, 3, 8, 1, 2] print(f'정렬 전: {numbers}') print() for i i..