SW개발/코딩테스트
[프로그래머스]여행경로 - DFS/BFS
https://programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr DFS 알고리즘 이용 from collections import defaultdict def solution(tickets): # 특정 티켓의 인접 리스트를 구하는 함수 # 즉, 도착지가 여러개인 경우를 1가지로 모아줌 # defaultdict(, {'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL..
[프로그래머스]단어 변환 - DFS/BFS
https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr BFS 알고리즘 이용 from collections import deque def solution(begin, target, words): queue = deque() length = len(words) word_length = len(begin) # 단어를 변환할 수 있는지 여부를 체크하는 함수 def can_chan..
[백준]1197번 - 최소 신장 트리, Kruskal, Prim
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 크루스칼 알고리즘 import sys # 특정한 노드의 부모가 누구인지 찾는 함수 def find(target): if target == parent[target]: return target parent[target] = find(parent[target]) return parent[target] # 부모 노드를 합치는 함수 def union(a, b..
[프로그래머스]섬 연결하기 - 그리디, 최소 신장 트리, Kruskal
https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr # 크루스칼 알고리즘 def solution(n, costs): answer = 0 visited = [0] # 크루스칼 알고리즘 적용을 위해 가중치를 오름차순으로 정렬한다 costs.sort(key=lambda x: x[2]) # 방문한 정점의 갯수가 n이 된다면 반복문을 중단 while len(visited) < n: for cost in costs: s, e, c = cost # 시작점과 끝점중 하나라도 방문한 리스트에 들어 있을 경우 if s in vi..
[프로그래머스]섬 연결하기 - 그리디, 최소 신장 트리, Prim
https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr # 프림 알고리즘, 우선순위큐 이용(heapq) import heapq def solution(n, costs): answer = 0 # 각 정점의 인접정보와 가중치를 저장하는 리스트 cost_all = [[]for _ in range(n)] # 방문 체크를 위한 리스트 visited = [] # 우선순위큐 사용 heap = [] # 시작정점을 0으로 선택, 가중치도 0으로 설정(cost, start) heapq.heappush(heap, [0, 0]) # 정..
[프로그래머스]조이스틱 - 그리디
https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr def solution(name): min_move = len(name) - 1 answer = 0 for index, char in enumerate(name): # 위, 아래로 움직이는 값 구하는 부분, 유니코드를 활용해 반복문이 필요 없다. answer += min(ord(char) - ord('A'), ord('Z') - ord(cha..
[프로그래머스]큰 수 만들기 - 그리디
https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr def solution(number, k): # 스택을 활용한다 stk = [] # number 리스트를 순회함 for num in number: # 제거해야할 값(k)가 남아있고, stk에 값이 있고, stk의 마지막의 값보다 현재 나온수가 더 크다면 # (큰 숫자가 큰 자릿수를 가지게 하기 위해) # 스택의 마지막 숫자를 없애버리고, 제거해야할 값을 하나 줄임 while k > 0 and stk and stk[-1] < num: stk.pop() k -= 1 # 기본적으로 값을 한개씩 넣어줌, (위의 조건에 부합할 경우에만 스택에서 값..
[프로그래머스]입국심사 - 이분탐색
https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr def solution(n, times): answer = 0 left, right = 1, max(times) * n while left = n: right = mid - 1 # 최대 인원수보다 심사 가능한 인원이 작다면 예상되는 시간을 늘린다 else: left = mid + 1 # 마지막의 정답은 left값으로 설정 answer = left return an..
[프로그래머스]8주차_최소직사각형 - 위클리 챌린지
https://programmers.co.kr/learn/courses/30/lessons/86491 코딩테스트 연습 - 8주차_최소직사각형 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133 programmers.co.kr def solution(sizes): max_width = 0 max_height = 0 for card in sizes: # 큰 값을 한쪽으로 몰아 넣는 과정 if card[0] < card[1]: card.reverse() # 큰 값을 갱신하는 부분 max_width = max(max_width, card[0]) max_height = max(max_he..
[프로그래머스]카펫 - 완전탐색
https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr def solution(brown, yellow): panel = brown + yellow answer = [] for width in range(3, panel+1): if ((width-2) * ((panel // width) -2) == yellow): # height 값 answer.append(panel // width) # width 값 answ..