728x90

Problem Solving 15

백준 1753. 최단경로 (+파이썬 풀이)

Question. 최단경로 문제다. 코딩테스트에 정말 자주 나오는 문제이니 풀어보자. Answer. 최단경로 알고리즘 중에서도 '다익스트라 알고리즘' 문제다. 2021.01.16 - [Computer Science/Datastructure & Algorithm] - 최단경로 알고리즘 (1) - 다익스트라 알고리즘 최단경로 알고리즘 (1) - 다익스트라 알고리즘 *최단경로 알고리즘: 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 *최단경로 알고리즘의 종류 1) 다익스트라 알고리즘 2) 플로이드 워셜 알고리즘 3) 벨만 포드 알고리즘 코딩테스 sohyunwriter.tistory.com 다익스트라 알고리즘은 매우 많이 나와서 아예 함수로 아래와 같이 snippet으로 만들어뒀다. import he..

백준 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: ..

[코딩 인터뷰 완전 분석 6E] "농구"

Question. 코딩 인터뷰 완전 분석 6E - 06. 수학 및 논리 퍼즐 - 농구 농구 골대가 하나 있는데 다음 두 게임 중 하나를 해 볼 수 있다. 게임 1: 슛을 한 번 쏴서 골대에 넣어야 한다. 게임 2: 슛을 세 번 쏴서 두 번 골대에 넣어야 한다. 슛을 넣을 확률이 p라고 했을 때 p가 어떤 값일 때 첫 번째 게임을, 혹은 두 번째 게임을 선택하겠는가? Answer. sol 1) Time Complexity Space Complexity

[코딩 인터뷰 완전 분석 6E] "무거운 알약"

Question. 코딩 인터뷰 완전 분석 6E - 06. 수학 및 논리 퍼즐 - 무거운 알약 약병 20개가 있다. 이 중 19개에는 1.0그램짜리 알약들이 들어있고, 하나에는 1.1그램짜리 알약들이 들어 있다. 정확한 저울 하나가 주어졌을 때, 무거운 약병을 찾으려면 어떻게 해야 할까? 저울은 딱 한 번만 쓸 수 있다. Answer. 저울을 딱 한 번만 쓸 수 있다는 것이 강한 제약조건이다. 그렇기 때문에 한 번 저울을 사용할 때 가능한 많은 알약들을 사용해야 한다. 약병에서 알약을 뽑는 개수를 달리 함으로써 이를 약병의 index로 사용하면, 나온 무게를 보고 약병의 index를 알 수 있다. 예를 들어 문제를 단순화해서 약병이 2개 있다고 가정해보자. 하나는 1.0그램짜리 알약이 들어있고, 또 하나는..

[백준] 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..

[백준] 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가 같지 않..

[백준] 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..

[프로그래머스] "네트워크" (+파이썬 코드)

Question. 프로그래머스 깊이/너비 우선 탐색(DFS/BFS) > 네트워크 Answer. computers라는 인접행렬(adjacency matrix) graph가 주어지는데, 해당 graph에서 connected component가 몇 개인지 구하는 문제이다. bfs로 풀 수도 있고, dfs로 풀 수도 있다. 주어진 인접행렬을 이용해 DFS로 풀면 다음과 같다. sol1) 인접행렬 + dfs 1) i번째 노드를 방문하지 않았다면, 스택에 i번째 노드를 넣는다. 2) stack의 요소를 하나씩 pop 하며 visited 배열에 해당 노드를 true 처리한다. 3) 해당 노드와 연결된 노드들 중 방문하지 않은 노드들을 스택에 넣어준다. ---> dfs 함수 부분 4) 1~3을 n개의 노드에 대해 반복..

여러 좌표가 주어질 때 이쁘게 별(*) 찍기

오늘 코딩테스트를 보다가 오랜만에 '별 찍기' 문제를 보게 됐다. 해당 문제에서 좀 까다로웠던 부분만 하위 문제로 새롭게 만들어봤다. Q. 여러 좌표가 주어질 때 이쁘게 별(*) 찍기 (-1, 0), (1, 0) 과 같은 좌표가 주어지면, 주어진 좌표는 '*'로 표시하고, 나머지는 '.'로 표시한다. 즉, ['*.*'] 로 출력한다. 물론 board의 크기 제한은 없지만, ['...', '*.*']로 출력하면 안 된다. 즉, '...'는 굳이 필요 없으므로 제거한다. 별로 어렵지 않은 문제인데, 구현을 어떻게 하면 간단히 할까라는 생각을 시험 끝나고 생각해보다가, 다음과 같이 함수화시켜봤다. points_to_star 함수는 점들이 주어지면 해당 점들에 대해 '*'로 board에 표시해주는 함수다. 코드..

Problem Solving 2021.02.07
728x90