알고리즘 문제풀이210 [백준] 14938 서강그라운드 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 하나의 노드를 기준으로 하여 특정 거리 범위 안에 있는 노드들을 탐색이 필요하였습니다. 노드를 기준으로 하여 다른 노드까지의 최소 거리를 구하기 위하여 다익스트라를 이용하였습니다. 모든 노드들을 기준으로 하여 다익스트라로 수색 범위 내의 노드들의 아이템 개수를 카운트 하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start, m): # 다익스트라 (시작 노드 번호, 수색 범위) global answer distance = [-1] * (N+1) # 다른 노드까지의 거리 h = [(0, start)] .. 2022. 4. 23. [백준] 17144 미세먼지 안녕! 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 크게 미세먼지가 확산되는 이동과 공기청정기가 가동되어 미세먼지가 이동하는 두개의 함수로 나누어서 작성하였습니다. Python 으로 제출하였을 경우 시간초과 문제가 발생하였습니다. PyPy 로 제출하여 통과하였습니다. 추후에 단순 2중 반복문이 아닌 미세먼지가 현재 있는 위치만 기록하여 반복시키는 방법을 이용하여 다시 풀이할 예정입니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') R, C, T = map(int, sys.stdin.readline().split()) # 행, 열, 시간 board = [list(map(int, sys.stdin.readline().. 2022. 4. 22. [백준] 2638 치즈 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 치즈가 포함되어 있는 좌표들과 DFS 를 이용하여 외부의 공기 영역을 우선적으로 구하였습니다. 시간의 흐름에 따라 치즈에서 외부 공기와 두칸 이상 맞닿은 치즈를 없애주었고, 새로 외부 공기 영역을 구하였습니다. 2) 알고리즘 DFS 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def set_air(melted = []): # 공기의 영역을 새로 구하는 함수 stack = melted or [(0, 0)] # 녹는 치즈가 있으면 초기값으로 설정 없다면 0,0 을 초기값으로 설정 while stack: node = stack.pop() if not air[node[0]][node[1].. 2022. 4. 21. [백준] 2252 줄 세우기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 학생들의 절대적인 키가 아닌 상대적인 키를 입력으로 받고 있습니다. 이러한 경우 한 학생을 기준으로 그 학생보다 크거나 작은 학생들의 목록만 알아낼 수 있습니다. 위상 정렬 알고리즘을 이용하여, 한 학생보다 키가 작은 모든 학생들을 줄을 세우고나면 해당 학생을 줄을 세우는 방식으로 접근하였습니다. 2) 알고리즘 위상 정렬 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') N, M = map(int, sys.stdin.readline().split()) # 학생의 수, 키를 비교한 횟수 linked = [[] for _ in range.. 2022. 4. 20. [백준] 12852 1로 만들기 2 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 현재 숫자에서 조건의 연산을 진행하며 나아갈때 이전의 연산들을 기록하여야 했으므로 딕셔너리를 이용하여 기록하였습니다. 또한 메모리 확보를 위하여 이전에 사용한 기록들은 불필요하므로 지속적으로 관리하지 않고 제거하였습니다. 2) 알고리즘 다이나믹 프로그래밍 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 찾으려는 수 dp = {0 : [], 1: [1]} # 각 숫자별 연산 순서 (최소만 기록) for idx in range(1, N+1): # 찾으려는 수까지 반복 if idx * 3 len(dp[idx]) + 1) or not .. 2022. 4. 19. [백준] 1005 ACM Craft 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 문제를 접하고 도착하는 노드에서 거꾸로 BFS 탐색을 이용해 같은 거리만큼 떨어진 노드들의 시간들 중 가장 오래 걸리는 시간을 기록하여 구하려 하였습니다. 그러나 시간초과 문제가 발생하였고, 원인을 정확히 파악하지 못하였으나 거꾸로 진행하는 방식은 값을 구하는 과정에서 오류가 발생할거 같다는 생각이 들었습니다. (건물이 순서대로 건설 되는것이 아니라 병렬적으로 건설이 가능하여 노드들의 위치와 필요한 건물들의 상황에 따라 최소 시간에 오류가 발생) 그래서 앞에서부터 진행하는 방식을 이용하였습니다. 다음 노드에서 단방향으로 들어오는 간선의 개수를 카운트하고 그 카운트가 0이 되었을때 다음 노드를 실행하도록 하였습니다. 2) 알고리즘 다이나믹 프로그래밍 위.. 2022. 4. 16. [백준] 20040 사이클 게임 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 노드들 간에 사이클로 연결이 되어있는지 판단을 하기 위하여 서로소를 이용하였습니다. 서로소는 두개의 노드가 연결이 되어 있다면 하나의 동일한 최상위 부모를 가리키게 됩니다. 따라서 두 노드의 최상위 노드가 서로 다르면 연결이 되어 있지 않으므로 연결을 시켜주고, 두 노드의 최상위 노드가 같으면 이미 연결이 되어 있으므로 현재 간선을 잇게 된다면 사이클이 형성되는 방식을 이용하였습니다. 2) 알고리즘 서로소 알고리즘 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def find(x): # 최상위 부모 노드 탐색 if x != s[x]: # 현재 노드가 최상위가 아니면 x = find(.. 2022. 4. 15. [백준] 17404 RGB거리 2 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 이전에 사용한 색상과 다르게 선택해야하고, 가장 첫 집과 마지막 집의 색상이 달라야 하므로 인덱스로 색상을 관리하였습니다. 입력이 3가지 색상이므로 크기 9의 1차원 배열을 생성하였습니다. 0~2 인덱스는 빨간색으로 시작하는 경우로 각 인덱스는 빨간색, 초록색, 파란색으로 끝나는 경우들을 의미합니다. 3~5 와 6~8 인덱스는 각각 초록색과 파란색으로 마지막에 끝나는 경우는 위와 동일합니다. 2) 알고리즘 다이나믹 프로그래밍 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 집의 개수 answer = 1e10 # 비용 (초기 최댓.. 2022. 4. 14. [백준] 2467 용액 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 두 개의 용액들을 서로 비교하여 혼합하였을 경우 특성값이 0에 가까운 용액들을 찾아야 했습니다. 0을 만들기 위해서는 현재 용액에 -1을 곱한 값이 리스트에서 어느 위치에 들어갈 수 있는지 이분 탐색을 이용하여 찾았습니다. 찾은 인덱스 값의 앞뒤 용액들을 모두 현재 용액과 혼합했을때 특성값을 계산하여 0에 가장 가까운 수가 되는 경우를 탐색하였습니다. 2) 알고리즘 이분 탐색 3) 풀이 코드 사용 언어 - Python import sys from bisect import bisect_left sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 용액의 수 num_li = list(map(int,.. 2022. 4. 13. [백준] 2096 내려가기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 행이 아래로 진행이 될때마다 최댓값과 최솟값을 기억하며 내려가야 하므로 다이나믹 프로그래밍을 이용하였습니다. 초기에 문제를 접했을때, 주어진 모든 숫자들을 2차원 배열에 저장하였고 최댓값과 최솟값을 저장하는 3차원 배열의 리스트를 생성하였습니다. 그리고 각 행을 진행하면서 행별 최댓값과 최솟값을 저장하였습니다. 그러나 N의 범위가 최대 100,000으로 최악의 경우에 메모리 초과가 발생하였습니다. 그로 인하여 3차원 배열 DP를 3*2 크기의 2차원 배열로 변경하였습니다. 또한, 주어진 모든 숫자를 입력받은 후 계산을 진행하지 않고, 숫자가 주어질때 바로바로 연산을 진행하여 숫자들을 저장하는 변수를 사용하지 않게 진행하여 문제를 해결하였습니다. 2) .. 2022. 4. 12. [백준] 1918 후위 표기식 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 변환된 정답을 저장하는 스택과 연산자와 괄호를 저장하는 스택을 생성하여 관리하였습니다. 알파벳은 바로 정답 스택에 쌓았고, 괄호와 연산자의 우선순위에 따라 정답에 추가하였습니다. 2) 알고리즘 자료구조 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') infix = sys.stdin.readline().rstrip() # 중위 표현법 answer = [] # 후위 표현법으로 변형된 정답 op = [] # 괄호 및 연산자가 들어갈 스택 for c in infix: # 앞에서부터 반복 if c.isalpha(): # 알파벳이라면 바로 정답에 넣기 answer.append(c) elif c .. 2022. 4. 11. [백준] 17070 파이프 옮기기 1 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 처음에 문제를 접하고 간단하게 BFS 방식으로 탐색을 시도하였습니다. 그러나 모든 경우를 탐색하여야 하므로 시간 초과가 발생하였습니다. 그 이후 각 좌표에 올 수 있는 경우의 수를 구하는 방식으로 풀이하였습니다. 2) 알고리즘 다이나믹 프로그래밍 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 가로, 세로 길이 home = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 집의 상태 0-빈칸, 1-벽 dp = [[[0] * (N+1) for _ in range.. 2022. 4. 10. 이전 1 ··· 4 5 6 7 8 9 10 ··· 18 다음
