gaki gaki

heap 을 사용한 다익스트라 알고리즘으로 구현. 다익스트라 부분은 코드 길이가 겨우 6~7줄. 생각보다 쉽다. 어렵게 생각하지말자. import heapq; V,e = map(int, input().split()); start = int(input()); infos = list([] for _ in range(V + 1)); heap = []; for i in range(e): u,v,w = map(int, input().split()); infos[u].append([w,v]); INF = 1e9; D = [INF] * (V + 1); D[start] = 0; def diakstra(start, heap, D, infos): heapq.heappush(heap, [0, start]); while (h..

문제풀이 처음에는 플로이드 와샬(O(n^3)) 을 사용했지만, 시간초과가 났다. 그 다음에는 다엑스트라(O(nlogn)) 을 사용했지만, 풀지 못했다. 그러다가 가장 쉽고 직관적인 BFS 를 사용해서 풀게되었다. 시간복잡도 O(n^2) 이하. (visited 에서 예외처리를 해주기 때문) 소스코드 from collections import deque from collections import defaultdict; def solution(n, edge): link = defaultdict(list); visited = [0] * (n+1); ret = [0] * (n+1); for a,b in edge: link[a].append(b); link[b].append(a); queue = deque(); i..

문제링크 https://www.acmicpc.net/problem/15997 15997번: 승부 예측 첫 번째 줄에 조별리그를 진행할 국가명 네 개가 공백으로 구분되어 주어진다. 주어지는 모든 국가명은 알파벳 대문자로만 구성된 길이가 1 이상 10 이하인 문자열이다. 두 번째 줄부터 일곱 번 www.acmicpc.net 문제풀이 이 문제는 해결 방법을 떠올리기도 어렵고, 구현하는게 복잡한 문제이다. 총 4개의 팀이 6번의 매치를 하는데 각 매치마다 이기거나, 지거나, 비기는 모든 경우의 확률을 완전탐색한 뒤 1등과 2등을 뽑아 1등과 2등에게 각각의 확률을 더해주는 식으로 문제를 풀면된다. 이 문제를 구현하기 까다로웠는데 그 이유는, 1. 재귀함수와 for 문, 스택을 이용한 완전탐색 구현 2. 데이터 ..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제풀이 이 문제는 begin 이라는 문자열을 몇 번 변환해서 target 이라는 문자열로 만들 수 있는지 묻는 문제이다. 이 문제에 핵심 아이디어는 BFS 를 사용해서 푸는것이다. 먼저 words 문자열 안에 target 이라는 문자열이 존재하지 않으면 0 을 리턴하는 예외처리를 해준다. 그 다음, 처음 주어..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제풀이 이 문제는 dfs 를 사용해서 연결된 네트워크 set 의 개수가 몇개인지 구하는 문제이다. 문제에서 네트워크의 연결 상태를 n * n 의 2차원 배열로 주었다. 하지만, 이러한 데이터 형태는 사용하기가 까다로워 먼저 데이터를 사용하기 편하게 파싱했다. [ [1], [0,2], [1] ] 위와 같은 형태로 파싱했으며, 이는 0 번째 노드는 ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 문제 풀이 이 문제는 재귀를 이용한 완전탐색으로 쉽게 해결할 수 있다. 숫자 앞에 + 나 - 둘 중 1개가 올 수 있으므로, 총 만들수 있는 경우의 수는 2^n 이다. 즉 Big(O) = 2^n 이다. 문제에서 n 의 범위가 20 이하라고 했으므로( 백만번 계산 ), 시간초과는 절대 안걸린다. 시간 복잡도 Big(O) = 2^n..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 문제풀이 원을 따라 위치한 집들을 털 때, 최대로 훔칠 수 있는 값을 리턴하는 문제이다. 이 문제에서는 기준점을 정해주는 것이 풀이의 첫단추를 꿰는 것이다. 나는 1번 째 집을 기준점으로 정했고, 1번째 집을 터는 경우와 털지 않는 경우 두 가지로 나누어서, 두 케이스 중 최댓값을 리턴하는 식으로 진행했다. 그리고 1번째 집부터 n 번째 집까지 순서대로..

문제 링크 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 문제풀이 삼각형의 경로를 지나면서 최대값을 가지는 경로를 구하는 문제이다. 삼각형 트리안에 들어가는 값들은 0보다 크거나 같은 정수이기 때문에, 맨 아랫줄 삼각형의 누적값들 중 최대값을 고르면 되는 문제이다. Sum(i,j) = V(i,j) + max(Sum(i-1, j-1), Sum(i-1, j)) 라는 점화식을 이용해 풀면 되는데, i, j 값이 오바되지 않도록 예외처리만 신경써주면 쉬운 문제이다. 시간복잡도 n 층의 n ..