알고리즘 문제풀이210 [백준] 10986 나머지 합 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 특정 구간의 합이 특정 수로 나누어 떨어지는 경우를 찾아야했습니다. 구간의 합을 빠르게 구하기 위하여 누적합을 이용하였습니다. 숫자만큼 반복하여 처음부터 마지막 수까지 누적합을 구하였고, 특정 수로 나눈 나머지만을 구하여 기록하였습니다. 구간의 시작과 마지막이 동일한 경우는 나머지가 0으로 기록되면 경우의 수에 포함할 수 있으므로 누적합에서 0으로 기록된 개수를 찾으면 됬으므로 간단하였습니다. 그러나 모든 구간들의 나머지를 구하기 위해 2중 반복문을 사용하였으나 입력으로 무수히 많은 수가 들어온다면 시간초과 문제가 발생하였습니다. 2중 반복문을 사용하지 않고, 경우의 수를 구하는 방법이 필요했습니다. 누적합의 A~B 구간의 합의 나머지가 X 이고, A.. 2022. 6. 22. [백준] 3584 가장 가까운 공통 조상 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 노드들의 연결 관계를 먼저 정리한 이후, 두 노드를 큐에 담았습니다. 두 노드를 번갈아가며 부모 노드들을 모두 탐색하였습니다. 탐색 중 이미 방문한 노드인 경우가 공통 조상 노드이기 때문에 해당 노드를 반환하였습니다. 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def solution(a, b): visited = [False] * N # 노드 방문 여부 q = deque([a, b]) # 큐, 초기에 시작할 두개의 노드 while q: node = q.popleft() if not visited[node].. 2022. 6. 21. [백준] 2580 스도쿠 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 빈칸에 입력이 가능한 숫자들을 채워가며 스도쿠의 조건을 만족시켜야 했습니다. 빈칸으로 주어진 좌표들을 모두 리스트로 정리하였고, 좌표들을 반복하며 해당 좌표에 입력 가능한 숫자들을 모두 구한 후 숫자들을 넣어보며 탐색하였습니다. 2) 알고리즘 DFS 재귀 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def get_can_num(y, x): # 행, 열, 사각형을 확인해서 들어갈 수 있는 번호 구하기 can_num = {1, 2, 3, 4, 5, 6, 7, 8, 9}.difference(sudoku[y]) # 현재 행에서 들어갈 수 있는 번호 for j in range(9): # 현.. 2022. 6. 20. [백준] 1937 욕심쟁이 판다 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 입력으로 주어지는 대나무 숲의 크기가 크므로 모든 좌표에 대해 이동 가능한 거리를 탐색하면 시간 초과 문제가 발생합니다. 그러므로 각 좌표에 이동 가능한 최대의 거리를 기록이 필요하여 DP를 이용하였습니다. 처음에 BFS를 이용하여 가장 적은 대나무 양의 좌표를 탐색하여 이동 가능한 거리를 기록하였고, 기록이 안된 좌표들이 남아있을 경우 다음으로 적은 대나무 양을 가진 좌표를 탐색하여 거리를 구하였습니다. 그러나 기록이 되지 않은 좌표들이 남아있을 때 마다 계속해서 2차원 배열 탐색이 필요하였고, 이전에 기록한 이동 가능한 거리가 탐색의 경우에 따라 값이 변하게 되었습니다. 이러한 과정으로 인해 탐색의 양이 증가하여 시간 초과가 발생하였습니다. 이러한.. 2022. 6. 17. [백준] 2668 숫자고르기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 문제의 조건을 만족시키도록 정수를 뽑기 위해서는 첫째줄의 번호들을 순서대로 모두 뽑을때, 사이클이 생성되는 집합을 찾아야 했습니다. 첫번째 줄에서 선택한 인덱스와 두번째 줄에서 나온 숫자가 같은지 판별을 하기 위하여 두개의 변수를 이용하여 관리하였습니다. 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(start): global answer stack = [start] # 스택 chk_first = [] # 첫번째 줄에서 선택한 인덱스 chk_second = [] # 두번째 줄에서 나온 숫자 while stack: node = stack.p.. 2022. 6. 16. [백준] 2251 물통 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 각 바구니로 물을 이동시킬 때, 물을 최대한 많이 옮겨야했습니다. A->B, A->C, B->A, B->C, C->A, C->B 로 물을 옮기도록 하는데, 두 바구니를 비교하여 이동가능한 물의 양을 구하여 이동시켰습니다. 탐색 여부를 확인하는 딕셔너리 변수를 이용하여 중복 탐색을 방지하였습니다. 딕셔너리 변수의 키 값으로는 (A바구니 물의 양, B바구니 물의 양)으로 지정하였습니다. 2) 알고리즘 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def solution(): q = deque([(0, 0)]) # 처음 A, B.. 2022. 6. 15. [백준] 13023 ABCDE 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 그래프에서 계속해서 다음 깊이를 탐색하는 것으로 깊이가 5가 되는 관계가 있는지 탐색이 필요했습니다. DFS를 재귀로 구현하여 ABCDE 관계가 있는지 여부를 탐색하였습니다. 2) 알고리즘 DFS 재귀 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(node, ans): # 현재 사람 번호, 탐색 깊이 global answer if ans >= 5: # ABCDE 관계가 된다면 answer = True # 정답 변경 return visited[node] = 1 # 현재 사람 탐색 체크 for next in linked[node]: # 현재 사람과 친구인 사람들 .. 2022. 6. 14. [백준] 10282 해킹 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 하나의 컴퓨터가 해킹되어 의존되어 있는 다른 컴퓨터가 일정 시간이 지나면 감염이 되므로 하나의 컴퓨터에서 다른 여러 컴퓨터를 감염 시킬때 모두 소요되는 시간이 다르므로 시간이 병렬적으로 진행되도록 할 필요가 있습니다. 특정 컴퓨터 하나가 감염이 완료되는 시간을 기록하도록 변수를 이용하였습니다. 다음으로 의존성 있는 다른 컴퓨터를 감염시킬 때, 현재 완료된 시간에 다른 컴퓨터로 감염이 되는데 필요한 시간을 더하여 감염이 완료되는 시간을 기록하였습니다. 최소 힙을 이용하여 감염이 가장 빠르게 완료되는 컴퓨터를 하나씩 탐색하여 감염되는 컴퓨터의 수와 시간을 기록하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sy.. 2022. 6. 12. [백준] 1507 궁금한 민호 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 모든 도시를 기준으로 하여 다른 도시로 이동할 때 필요한 최소 거리가 입력으로 주어집니다. 입력으로 주어진 최소 거리 정보를 유지하면서 도로의 개수를 최소로 만들어, 남아있는 도로 거리의 총합을 구하여야합니다. 도로 거리 구하는 것이 불가능한 경우는 입력으로 주어진 최소 거리 정보가 잘못된 정보일 경우였습니다. 그래서 입력으로 주어진 정보를 그대로 이용하여 최초 1회 플로이드 워셜로 도시 간 최소 거리를 한번 더 구하였습니다. 이후에 값이 변한다면, 문제에서 요구하는 불가능한 경우로 -1을 출력하였습니다. 입력으로 주어진 2차원 배열의 최소 거리 정보가 다른 도시를 거치지 않고 두 도시를 바로 잇는 도로의 길이라고 가정하였습니다. 그리하여 두 도시를 .. 2022. 6. 11. [백준] 1613 역사 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 모든 사건을 기준으로 하여 다른 사건과의 전후 관계를 알아내야 하므로 플로이드 워셜을 이용하여 풀이하였습니다. 2) 알고리즘 플로이드 워셜 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N, K = map(int, sys.stdin.readline().split()) # 사건의 수, 사건 비교 수 history = [[0] * N for _ in range(N)] # 사건 순서 정보 for _ in range(K): before, after = map(int, sys.stdin.readline().split()) history[before-1][after-1] = 1 # 이전 사건,.. 2022. 6. 10. [백준] 10159 저울 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 모든 물건들에 대해서 각 물건이 다른 물건들과 무게 비교가 가능한지 탐색하는 문제입니다. 모든 물건들에 대해서 탐색이 필요하므로, 플로이드 워셜을 이용하엿습니다. 물건들을 비교하였을 때 순서에 대한 정보는 필요가 없으므로, 해당 물건 보다 크거나 작은지에 대한 정보만 기록하였습니다. 2) 알고리즘 플로이드 워셜 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 물건의 개수 M = int(sys.stdin.readline()) # 물건 비교한 횟수 order = [[0] * N for _ in range(N)] # 물건들 간 무게 .. 2022. 6. 9. [백준] 1956 운동 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 특정 마을에서 운동을 출발하여, 다시 출발 마을로 돌아오는 길이 짧은 경우를 구해야 했습니다. 하나의 마을에서 출발하는 경우, 다익스트라를 이용하면 편리하지만 모든 마을에서 사이클이 존재하는지 확인이 필요하므로 플로이드 워셜 알고리즘을 이용하였습니다. 플로이드 워셜 알고리즘을 이용하여 모든 마을에서 최소 사이클을 한번에 구하도록 하였습니다. 2) 알고리즘 플로이드 워셜 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') V, E = map(int, sys.stdin.readline().split()) # 마을, 도로 개수 distance = [[1e10] * V for _ in range.. 2022. 6. 8. 이전 1 2 3 4 5 6 7 ··· 18 다음
