본문 바로가기

Problem Solving15

백준 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.
[코딩 인터뷰 완전 분석 6E] "농구" Question. 코딩 인터뷰 완전 분석 6E - 06. 수학 및 논리 퍼즐 - 농구 농구 골대가 하나 있는데 다음 두 게임 중 하나를 해 볼 수 있다. 게임 1: 슛을 한 번 쏴서 골대에 넣어야 한다. 게임 2: 슛을 세 번 쏴서 두 번 골대에 넣어야 한다. 슛을 넣을 확률이 p라고 했을 때 p가 어떤 값일 때 첫 번째 게임을, 혹은 두 번째 게임을 선택하겠는가? Answer. sol 1) Time Complexity Space Complexity 2021. 3. 9.
[코딩 인터뷰 완전 분석 6E] "무거운 알약" Question. 코딩 인터뷰 완전 분석 6E - 06. 수학 및 논리 퍼즐 - 무거운 알약 약병 20개가 있다. 이 중 19개에는 1.0그램짜리 알약들이 들어있고, 하나에는 1.1그램짜리 알약들이 들어 있다. 정확한 저울 하나가 주어졌을 때, 무거운 약병을 찾으려면 어떻게 해야 할까? 저울은 딱 한 번만 쓸 수 있다. Answer. 저울을 딱 한 번만 쓸 수 있다는 것이 강한 제약조건이다. 그렇기 때문에 한 번 저울을 사용할 때 가능한 많은 알약들을 사용해야 한다. 약병에서 알약을 뽑는 개수를 달리 함으로써 이를 약병의 index로 사용하면, 나온 무게를 보고 약병의 index를 알 수 있다. 예를 들어 문제를 단순화해서 약병이 2개 있다고 가정해보자. 하나는 1.0그램짜리 알약이 들어있고, 또 하나는.. 2021. 3. 4.
[코딜리티] Lesson 10. Prime and composite numbers - CountFactors 문제 (+파이썬 코드) Question. CountFactors 약수 개수 구하는 문제다. Answer. O(sqrt(n)) ​ i*i 2021. 2. 21.
[백준] 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.