본문 바로가기

전체 글200

[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.
[Algorithm] 프로그래머스 42746 가장 큰 수 | 파이썬 (정렬) ※ 42746 가장 큰 수https://school.programmers.co.kr/learn/courses/30/lessons/42746 문제 해결 TIP문자열 비교에 대해 먼저 알아보자. print('2'위와 같이 '2'와 '20'을 비교하면 '20'이 크지만, '220'과 '202'를 비교하면 '220'이 더 커야한다. 따라서 문자열을 반복해주어 일관된 기준으로 비교해준다. 조건 중 numbers의 원소가 1000 이하인 점을 참고하여 3번 반복한 문자열들끼리 비교 정렬하여 출력하도록 한다. 전체 코드def solution(numbers): numbers = list(map(str, numbers)) numbers.sort(key=lambda x: x*3, reverse=True) .. 2024. 9. 5.
[Algorithm] 삼성 SW 역량테스트 2017 하반기 오전 1번 문제 조삼모사, 코드트리 | 파이썬 ※ 조삼모사https://www.codetree.ai/training-field/frequent-problems/problems/three-at-dawn-and-four-at-dusk/description?page=1&pageSize=20&tier=1%2C10 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai[문제]n개의 일이 주어질 때 이를 아침과 저녁으로 2n​개씩 나누어처리하고자 합니다.일마다 특성이 다르기 때문에 같이할 때의 업무 강도를 나타내는 업무 간의 상성 Pij​가 존재합니다. 예를 들어 업무 상성이 다음과 같이 주어질 때,1, 2번 일을 아.. 2024. 8. 12.
[Algorithm] 삼성 SW 역량테스트 2017 상반기 오전 2번 문제 외주 수익 최대화하기, 코드트리 | 파이썬 (DP, Dynamic Programming) ※ 외주 수익 최대화하기https://www.codetree.ai/training-field/frequent-problems/problems/max-of-outsourcing-profit/description?page=1&pageSize=20&tier=1%2C10 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai[문제]n일의 휴가 동안 외주 개발을 하여 수익을 최대화 하려고 합니다. 수행할 수 있는 외주 작업이 하루에 한 개씩 있고, 각 외주 작업은 수행 완료하는데 걸리는 기한 t와 이를 완료 했을 때의 수익 p가 주어집니다. 두 개 이상의 외주 작업은 동.. 2024. 8. 12.

티스토리툴바