SW개발/코딩테스트

    [프로그래머스]정수 삼각형 - DP

    https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr Top Down 방법 def solution(triangle): height = len(triangle) # Top-down 방법으로 풀이 for i in range(1, height): for j in range(i+1): print(i, j) # 가장 왼쪽의 경우 왼쪽수를 모두 더하면서 내려감 if j == 0: triangle[i][j] += triangle[i-1][j] # 가장 오른쪽의 경우 오른쪽수를 모두 더하면서 내려감 el..

    [프로그래머스]N으로 표현 - DP

    https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr def solution(N, number): # N과 number가 같은 경우라면 1을 반환한다. if N == number: return 1 # N은 최대 8번까지 이용할 수 있으므로, 8개의 set(집합)을 가진 리스트를 만든다. dp = [set() for _ in range(8)] # N을 N번 나열하는 것에 대한 경우를 미리 초기화해서 넣어준다. # 마지막에 추가하지 않는 이유는 해당 수를 사용해서도 사칙연산이 가능하기 때문이다. # [{5}, {55}, {555}, ...] for index, case in enumerate(dp..

    [프로그래머스]여행경로 - 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 = [False] * n # 우선순위큐 사용 heap = [] # 시작정점을 0으로 선택, 가중치도 0으로 설정(cost, start) heapq.heappush(heap, [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..