알고리즘 문제풀이/Python179 [프로그래머스] 지형 이동 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 2차원 배열의 각 좌표에 숫자 값이 적혀있고, 상하좌우로 인접한 좌표의 값의 차이에 따라 사다리를 사용하게 되는데, 사다리 이용하는 비용을 최소로 하는 방법을 구하여야 했습니다. 어느 한 좌표를 시작으로 하여 사다리 없이 이동이 가능한 좌표들을 모두 방문합니다. DFS 로 탐색하는 중에 인접한 좌표와 높이 차이가 있어 사다리가 필요한 경우에, 높이 차이의 값과 인접한 좌표를 최소힙에 기록하였습니다. 이후 모든 좌표를 방문하지 못하였을 경우, 최소힙에서 높이 차이가 가장 적은 다음 좌표를 이용하였습니다. 다음 좌표에서도 사다리 없이 이동 가능한 모든 좌표를 방문하며, 높이 차이를 최소힙에 기록하였습니다. 2) 알고리즘 DFS 최소힙 3) 풀이 코드 사용.. 2022. 4. 28. [프로그래머스] 다단계 칫솔 판매 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 수익을 벌어들인 노드(사람)에서 시작하여 부모 노드를 따라 올라가며 수익을 분배하는 문제였습니다. 수익을 벌어들인 노드를 시작으로 하여 최상위 노드까지 DFS 를 이용하여 탐색하였습니다. 2) 알고리즘 DFS 재귀 3) 풀이 코드 사용 언어 - Python import sys sys.setrecursionlimit(10000) def solution(enroll, referral, seller, amount): enroll_idx = {} # 사람 명단이 주어진 순서대로 출력이 필요하므로 '이름': '번호' 형태의 딕셔너리 필요 result = [0] * len(enroll) # 수익금 정답을 저장할 리스트 def setIdx(): # 사람들 번호를 .. 2022. 4. 27. [프로그래머스] 디스크 컨트롤러 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 작업의 평균 시간을 줄이기 위해서 현재 대기하는 작업들의 개수를 최대한 줄여주어야 합니다. 그래서 최소힙을 이용하여 작업이 시작되는 순서대로 작업을 가져왔습니다. 작업을 처리할 수 있는 경우에 대기 명단에 넣었고, 작업이 빨리 끝나는 순서대로 작업을 완료하였습니다. 2) 알고리즘 최소힙 3) 풀이 코드 사용 언어 - Python import heapq def solution(jobs): N = len(jobs) # 평균을 구하기 위한 작업의 개수 heapq.heapify(jobs) # 작업들을 최소힙으로 만듦 ms = 0 # 현재 작업의 시간 answer = 0 # 순수 작업한 시간 waiting = [] # 작업 대기 명단 while jobs or .. 2022. 4. 26. [프로그래머스] 가장 먼 노드 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 기준 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제였습니다. 다익스트라를 이용하여 가장 멀리 있는 노드의 거리를 구한 이후 해당 거리에 있는 노드의 개수를 확인하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import heapq def solution(n, edge): linked = [[] for _ in range(n+1)] # 노드의 연결 관계 distance = [0] * (n+1) # 노드들의 거리 for a, b in edge: # 노드 연결 관계 정리 (양방향) linked[a].append((1, b)) linked[b].append((1, a)) def dijkstra(start): # 다익스트.. 2022. 4. 25. [백준] 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. 이전 1 ··· 3 4 5 6 7 8 9 ··· 15 다음
