본문 바로가기

Problem Solving/백준8

백준 1753. 최단경로 (+파이썬 풀이) Question. 최단경로 문제다. 코딩테스트에 정말 자주 나오는 문제이니 풀어보자. Answer. 최단경로 알고리즘 중에서도 '다익스트라 알고리즘' 문제다. 2021.01.16 - [Computer Science/Datastructure & Algorithm] - 최단경로 알고리즘 (1) - 다익스트라 알고리즘 최단경로 알고리즘 (1) - 다익스트라 알고리즘 *최단경로 알고리즘: 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 *최단경로 알고리즘의 종류 1) 다익스트라 알고리즘 2) 플로이드 워셜 알고리즘 3) 벨만 포드 알고리즘 코딩테스 sohyunwriter.tistory.com 다익스트라 알고리즘은 매우 많이 나와서 아예 함수로 아래와 같이 snippet으로 만들어뒀다. import he.. 2021. 6. 17.
백준 1927. 최소 힙 (+파이썬 풀이) Question. 최소 힙을 구현하는 문제이다. Answer. 처음 파이썬으로 코딩테스트를 볼 때, heapq 모듈을 사용하는 방법을 몰라 헤맸던 기억이 난다. 코딩테스트에 heapq는 자주 나오니까 아래 내용을 익혀두자. https://www.daleseo.com/python-heapq/ [파이썬] heapq 모듈 사용법 Engineering Blog by Dale Seo www.daleseo.com (내 풀이) import heapq import sys input = sys.stdin.readline ## 시간초과 방지 N = int(input()) heap = [] for _ in range(N): x = int(input()) if x == 0: if not heap: print(0) else: .. 2021. 6. 17.
[백준] 1717. 집합의 표현 (+파이썬 코드) Question. 백준 1717. 집합의 표현 Answer. union-find 알고리즘을 구현하는 문제이다. 즉, union 함수랑 find_parent 함수를 구현할 수 있냐를 묻는 문제. sol 1) union-find 알고리즘을 구현하고, 같은 서로소 집합에 있는지 아닌지 확인해주는 함수를 구현해 풀었다. import sys sys.setrecursionlimit(1000000) # maximum recursion depth exceed (한도 안 늘리면 runtime error 발생) input = sys.stdin.readline def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) re.. 2021. 2. 15.
[백준] 10451. 순열 사이클 (+파이썬 코드) Question. 백준 10451. 순열 사이클 Answer. cycle의 개수를 세는 문제이다. sol 1) 이 문제에서 배열의 번호(start node)와 배열의 값(destination node)을 이용해 graph를 만들었다. 위 문제에서는 인접행렬이나 인접리스트로 그래프를 만들 필요는 없어서 일차원 배열로 graph를 만들었다. 그리고 union-find를 통해 cycle의 개수를 구하면 된다. 1) 배열의 번호가 start node를 의미하고, 배열의 값이 destination node를 의미하는 1차원 배열의 graph를 만든다. graph = [0] + list(map(int, input().split())) 2) start node와 destination node의 parent가 같지 않.. 2021. 2. 15.
[백준] 11724. 연결 요소의 개수 (+파이썬 코드) Question. 백준 11724. 연결 요소의 개수 Answer. 프로그래머스의 "네트워크"랑 비슷한 문제여서 자세한 풀이는 생략한다. sohyunwriter.tistory.com/90 [프로그래머스] "네트워크" (+파이썬 코드) Question. 프로그래머스 깊이/너비 우선 탐색(DFS/BFS) > 네트워크 Answer. computers라는 인접행렬(adjacency matrix) graph가 주어지는데, 해당 graph에서 connected component가 몇 개인지 구하는 문제이다. b.. sohyunwriter.tistory.com sol 1) 인접리스트 + dfs 반복문 주의사항 1) sys.stdin.readline 써야 시간초과 안 남 2) dfs 돌릴 때, visited한 node.. 2021. 2. 15.
[백준] 2748. 피보나치 수 2 - 문제 풀이 (+파이썬 코드) Question. 백준 2748. 피보나치 수 2 Answer. 사실 이 문제는 파이썬에서는 "백준 2747. 피보나치 수" 문제와 동일하다. 파이썬은 int, long 구분을 할 필요가 없고, 숫자가 아무리 커져도 다 담을 수 있기 때문에 2747번에 pass한 코드를 그대로 제출하면 된다. 그러나 cpp, java의 경우 long long 등으로 선언해, 피보나치 수의 값이 int 범위를 넘어갈 경우에도 해당 값을 담을 수 있도록 해야 pass 한다. 아래 파이썬 코드는 [백준] 2747. 피보나치 수 - 문제 풀이 (+파이썬 코드)과 동일하다. sol 1) recursion with memoization # recursion with memoization # time complexity : O(N).. 2021. 2. 5.
728x90