알고리즘 문제풀이/Python179 [백준] 17141 연구소2 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 2차원 배열을 상하좌우를 탐색하여야 하고, 시간의 흐름에 따라 상하좌우 이동하며 바이러스를 퍼트려야 하므로 BFS 탐색으로 접근하였습니다. 2) 알고리즘 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque from itertools import combinations sys.stdin = open('input.txt') def BFS(starts): # 너비 우선 탐색 global remain_empty visited = [[0] * N for _ in range(N)] # 좌표 방문 여부 체크 리스트 q = deque(starts) for n in q: # 첫 시작점 방문 체크 .. 2022. 1. 7. [백준] 1865 웜홀 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 노드간 가중치에 음수가 포함이 되어 다익스트라로는 해결이 어렵다고 생각하여 이전에 학습한 '벨만-포드' 알고리즘을 적용했습니다. 어떠한 지점에서 출발하여 다시 그 지점으로 돌아왔을때 시간이 줄어드는 경우를 찾아야 하는데, 만약에 한번 확인을 하여 계속 해서 값이 줄어드는 싸이클이 존재하는지 여부만 찾으면 된다고 생각했습니다. 2) 알고리즘 벨만-포드 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(): distance[1] = 0 # 출발 도시 거리는 0으로 초기화 for i in range(1, N+1): # 도시의 개수만큼 반복하여 확인 for j in ra.. 2022. 1. 6. [백준] 11657 타임머신 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 노드간 거리를 나타내는 간선의 가중치가 음수가 있는 경우도 있기 때문에, 다익스트라로는 어려울거라 생각했습니다. 간선 가중치에 음수가 들어간 경우 사용하는 벨만-포드 알고리즘을 학습하여 접근했습니다. 2) 알고리즘 벨만-포드 어떠한 노드에서 다른 노드로 이동하는 거리를 구할때 사용 (가중치가 음수가 있는 경우에도 사용 가능) 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(start: int): # 벨만포드 (시작 노드) dist[start] = 0 # 시작 위치의 거리는 0으로 세팅 for i in range(1, N+1): # 도시의 개수만큼 반복하여 확인 .. 2022. 1. 5. [백준] 1504 특정한 최단 경로 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 도착지점에 도착했을때, 필수로 방문해야하는 정점을 방문했는지 확인이 필요하여 최소힙을 사용하는 과정에서 방문한 정점의 리스트의 정보를 같이 최소힙에 저장을 시키는 방식으로 접근했습니다. 그러나 최소힙에 경로를 저장하는 리스트를 같이 할당하여 반복시켰기 때문에 메모리 초과가 발생했습니다. 이 문제를 해결하기 위해 정점 방문 기록을 삭제하고, 다익스트라를 최초 1번 정점, 필수 방문해야하는 정점 2개를 탐색하도록 접근하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start: int): # 다익스트.. 2022. 1. 4. [백준] 1043 거짓말 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 진실을 아는 사람들과 진실을 모르는 사람들이 어떤 파티에서 접촉하면 모두 진실을 알게 되므로, DFS 탐색으로 같이 겹치는 사람들을 구하려 접근 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(person: list): # 진실을 아는 사람들 구하는 함수 (진실을 아는 사람들) visited = [0] * (N+1) # 사람 확인했는지 체크용 리스트 stack = list(person.copy()) while stack: node = stack.pop() if not visited[node]: visited[node] = 1 for e in.. 2022. 1. 3. [백준] 9663 N-Queen 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 전형적인 N-Queen 문제로 완전 탐색, 백트래킹 사용 2) 알고리즘 완전 탐색 백트래킹 3) 풀이 코드 사용 언어 - Python import sys def chk(y, x): for i in range(1, y+1): if x - i >= 0 and cols_selected[x] - i == cols_selected[x-i]: # 현재 열의 행과 옆에 떨어진 열의 행이 같을때 return False # 위로 올라갈수록 대각선에 퀸이 있을때 elif x + i < N and cols_selected[x] - i == cols_selected[x+i]: return False return True def solution(n): global answe.. 2022. 1. 2. [백준] 1759 암호 만들기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 암호가 알파벳 증가하는 순서로 배열되었다고 하므로, 초기에 알파벳들을 사전순으로 사전 정렬 문제의 해당 조건에 충족하는 모든 문자를 찾아야하므로 완전 탐색으로 접근 2) 알고리즘 완전 탐색 (Brute force) 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(n, idx, ans): # 현재 알파벳 선택한 개수, 시작할 인덱스 번호, 지금까지 만든 단어 global vowel_cnt, consonant_cnt if n >= L: # 원하는 길이 만들어졌으면 확인 if vowel_cnt and consonant_cnt >= 2: # 모음이 1개 이상, 자음이 .. 2022. 1. 1. [백준] 10819 차이를 최대로 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 숫자들을 정렬하여 큰수와 작은수를 적절히 이용하여 계산하는 방식으로 접근 문제가 해결되지 않는것을 알아내서 완전 탐색 이용 2) 알고리즘 브루트포스 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def DFS(n, pre, ans): # 숫자를 선택한 횟수, 이전에 선택한 값, 지금까지 계산한 결과 값 global answer if n >= N-1 and answer 2021. 12. 31. [백준] 7662 이중 우선순위 큐 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 값을 추가하고 최솟값과 최댓값을 삭제하는 연산이 존재하여 최소힙을 이용해 데이터를 다루도록 접근 최소힙과 최대힙 2개를 사용하려 했으나 각자의 리스트에서 어떤 값들이 이미 삭제된건지 판별하기 어려울것 같아서 최소힙 하나로 진행 최소힙에서 최댓값 삭제할때는 내장된 max 함수와 리스트의 remove 함수를 이용해 제거하는 방식으로 접근하였으나 시간초과로 실패 최소힙과 최대힙 두개를 사용하는대신 어떤게 삭제 되었는지 판별하는 로직 추가하여 접근 2) 알고리즘 최소힙 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') T = int(sys.stdin.readline()).. 2021. 12. 30. [백준] 1747 소수&팰린드롬 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 소수를 구해야 하므로 '에라토스테네스의 체'를 이용하여 소수 판별 팰린드롬인 수를 구하기 위해 10으로 나눈 나머지 및 몫을 이용해 숫자 역으로 배치하여 판별 2) 알고리즘 에라토스테네스의 체 3) 풀이 코드 사용 언어 - Python import sys N = int(sys.stdin.readline()) # 특정 숫자 prime_num = [1] * 1003002 # 정답이 나올 수 있는 최대 숫자까지만 리스트 생성 prime_num[0] = prime_num[1] = 0 # 0, 1은 소수가 아니므로 for i in range(2, int(1003002**0.5) + 1): # 에라토스테네스의 체 if prime_num[i]: mul = 2 wh.. 2021. 12. 29. [백준] 6497 전력난 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 마을마다 모두 하나씩 길이 연결되어 있어야하고, 그 길의 유지비용이 가장 적게 할 수 있는 경우를 구해야 하므로 '최소 신장 트리' 알고리즘으로 접근 2) 알고리즘 최소 신장 트리 (Minimum Spanning Tree) 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def kruskal(start): # 힙을 이용한 크루스칼 알고리즘 구현 global min_cost heap = [(0, start)] # 최초 시작 지점 초기화 while heap: node = heapq.heappop(heap) if not visited[node[1]]: # 아직 연결되.. 2021. 12. 28. [프로그래머스] 하노이의 탑 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 완전 탐색하여 최소의 값을 구하려 접근 조건이 까다로워 함수 구현이 어려움 재귀를 이용하여 접근 2) 알고리즘 재귀 3) 풀이 코드 사용 언어 - Python def hanoi(n, start, middle, end, answer): # 원반 개수(높이), 원반이 출발하는 기준 기둥, 중간 기둥, 목적지 기둥, 정답 리스트 if n == 1: # 현재 원반이 1층 높이(최상단이라 옮겨야 하는 경우) answer.append([start, end]) # 현재 기둥에서 목적지 기둥으로 옮김 return hanoi(n-1, start, end, middle, answer) # 지금 보고 있는 기둥에서 위에 원반선택, 목적지는 중간에 거쳐야 하는것으로 변경 .. 2021. 12. 27. 이전 1 ··· 11 12 13 14 15 다음
