파이썬45 [Algorithm] 이분탐색(Binary search algorithm, 이진 검색 알고리즘) 이분탐색이란? 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이다. 재귀와 반복문으로 구현할 수 있다. 재귀 함수로 구현한 이분 탐색def binary_search(array,target,start,end): if start > end: return None mid = (start + end)//2 if array[mid] == target: return mid elif array[mid] > target: return binary_search(array,target,start,mid-1) else: r.. 2025. 1. 16. [Algorithm] PCCP 기출문제 340213 동영상 재생기 | 프로그래머스 ※ 340213 동영상 재생기https://school.programmers.co.kr/learn/courses/30/lessons/340213 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 해결 TIP모든 시간이 "00:00" 형태로 되어 있어 분과 초를 따로 계산하기 번거롭다. 시간을 모두 초로 변환하여 계산해준다. 전체 코드def change_to_sec(time): minutes, seconds = time.split(':') time = int(minutes)*60 + int(seconds) return timedef solution(video_len,.. 2025. 1. 9. [Algorithm] 백준 14620 꽃길 | 파이썬 (브루트포스) ※ 14620 꽃길https://www.acmicpc.net/problem/14620 문제 해결 TIP메인 로직은 backtrack안의 for문이다. 우선 첫번째 꽃을 심는다. 이후 두번째 꽃은 가능한 모든 위치에 심으면서 최소 비용이 나오는지 확인한다. 세번째 꽃도 가능한 모든 위치에 심으면서 최소 비용이 나오는지 확인한다. 이후, 꽃을 다시 뽑고, 첫 번째 꽃은 다른 위치에 심고 다시 반복 진행한다. 전체 코드N = int(input())money_graph = [list(map(int, input().split())) for _ in range(N)]visited = [[False] * N for _ in range(N)]dx = [0, 0, 1, -1]dy = [1, -1, 0, 0]# 꽃을 심을.. 2024. 9. 21. [Algorithm] 백준 4485 녹색 옷 입은 애가 젤다지? | 파이썬 (다익스트라) ※ 4485 녹색 옷 입은 애가 젤다지?https://www.acmicpc.net/problem/4485 문제 해결 TIP다익스트라를 2차원 배열 형태에 적용해보자. 전체 코드import heapq# 방향 설정: 상, 하, 좌, 우dx = [0, 0, -1, 1]dy = [-1, 1, 0, 0]def dijkstra(n, graph): # 비용 테이블을 무한대로 초기화 distance = [[float('inf')] * n for _ in range(n)] distance[0][0] = graph[0][0] # 우선순위 큐에 시작점 넣기 (비용, 좌표) queue = [(graph[0][0], 0, 0)] while queue: dist, x, y = heap.. 2024. 9. 11. [Algorithm] 백준 1261 알고스팟 | 파이썬 BFS ※ 1261 알고스팟https://www.acmicpc.net/problem/1261 문제 해결 TIP이전 미로만들기와 동일한 문제이다. n, m 값의 범위만 재설정해준다. 전체 코드from collections import dequedx = [0,0,-1,1]dy = [-1,1,0,0]def bfs(x,y): queue = deque() queue.append((x,y)) visited = [[-1] * m for _ in range(n)] visited[x][y] = 0 while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + .. 2024. 9. 11. [Algorithm] 백준 2665 미로만들기 | 파이썬 BFS ※ 2665 미로만들기https://www.acmicpc.net/problem/2665 문제 해결 TIPvisited 배열에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 저장한다. bfs로 탐색하면서, 흰 방인 경우를 먼저 탐색한다.(appendleft) 검은 방일 경우에는 이전 visited값에 1을 추가해준다. 전체 코드from collections import dequedx = [0,0,-1,1]dy = [-1,1,0,0]def bfs(x,y): queue = deque() queue.append((x,y)) visited = [[-1] * n for _ in range(n)] visited[x][y] = 0 while queue: x, y = queue.p.. 2024. 9. 11. [Algorithm] 프로그래머스 14938 서강그라운드 | 파이썬 (다익스트라) ※ 14938 서강그라운드https://www.acmicpc.net/problem/14938 문제 해결 TIP최단경로 문제와 동일한 다익스트라 알고리즘으로 구현한다. 이때, 단방향이 아닌 양방향으로 간선 정보를 저장해야 한다. 또한, 수색범위 조건을 추가해준다. 전체 코드import sysimport heapqinput = sys.stdin.readlineINF = int(1e9)def dijkstra(start): q= [] heapq.heappush(q,(0,start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] 2024. 9. 6. [Algorithm] 프로그래머스 1238 파티 | 파이썬 (다익스트라) ※ 1238 파티https://www.acmicpc.net/problem/1238 문제 해결 TIP최단경로 문제와 동일한 다익스트라 알고리즘으로 구현한다. 이때, 시작 노드가 고정된 오는 길 뿐만 아니라 가는 길도 계산해야 함으로, 추가해준다. 전체 코드import sysimport heapqinput = sys.stdin.readlineINF = int(1e9)def dijkstra(start): q= [] heapq.heappush(q,(0,start)) distance[start] = 0 while q: dist, now = heapq.heappop(q) if distance[now] 2024. 9. 5. [Algorithm] 프로그래머스 1753 최단경로 | 파이썬 (다익스트라) ※ 1753 최단경로https://www.acmicpc.net/problem/1753 문제 해결 TIP주어진 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는다. 다익스트라 알고리즘으로 구현한다. 우선순위 큐를 초기화하고 큐가 비어있을 때까지 인접 노드를 확인하며 더 짧은 경로를 찾아 해당 거리를 업데이트한다. 전체 코드import sysimport heapqinput = sys.stdin.readlineINF = int(1e9)def dijkstra(start): q= [] heapq.heappush(q,(0,start)) distance[start] = 0 #q = [(0, 1)] while q: dist, now = heapq.heappop(q) .. 2024. 9. 5. 이전 1 2 3 4 5 다음
