백준136 [백준] 2458 키 순서 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 학생의 키를 비교하기 위하여 DFS, BFS, 다익스트라 탐색을 고려하였으나, 학생들간 비교 정보에 대해서 모든 학생들을 기준으로 확인해야 했으므로 여러번 탐색이 필요하였습니다. 이러한 경우 제한 시간 문제가 발생하였습니다. 이후 플로이드 워셜을 고려하였으며, 처음에는 현재 학생보다 키가 큰 경우에는 배열의 값을 1, 작은 학생의 경우 -1 의 가중치를 주었습니다. 이후 판별에서는 탐색하는 학생과 같은 레벨에 있는 학생이 있는지 여부로 판별하려 하였으나, 예외 사항이 발생하였습니다. 가중치를 1과 -1로 주게 되어 같은 레벨에 존재하지 않지만, 키를 비교할 수 없는 경우가 발생하였습니다. 이러한 문제를 해결하기 위하여 -1 의 가중치를 제거하고, 학생.. 2022. 6. 7. [백준] 11404 플로이드 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 초기에 특정 노드에서 다른 노드로 가는 최단 거리를 구하기 위하여 다익스트라를 이용하여 구하였습니다. 그러나 모든 노드에서 다른 노드로 이동하는 최단 거리를 구하여야 했기에, N개에 노드에 대해서 다익스트라를 N번 이용하여야 했습니다. 이로 인하여 시간 초과가 발생하였습니다. 모든 노드에서 다른 모든 노드로 이동하는 최단 거리를 한번에 구하기 위하여 '플로이드 워셜' 알고리즘을 이용하였습니다. 다익스트라와 플로이드 워셜 알고리즘의 용도에 대해 비교를 간단하게 해보자면, 다익스트라는 특정 노드에서 출발하여 다른 노드들로 향하는 최단 거리를 빠르게 구할 수 있다면, 플로이드 워셜 알고리즘은 모든 노드에서 다른 노드들로 향하는 최단 거리를 구할 수 있습니다.. 2022. 6. 5. [백준] 2589 보물섬 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 문제를 처음 접했을때, 트리의 지름을 구하는 원리를 이용하였습니다. 여러 육지로 이루어진 하나의 대륙(덩어리)의 한 좌표에서 가장 멀리 있는 좌표를 구한 이후 다시 그 좌표에서 가장 멀리 있는 값을 구하였습니다. 그러나 육지가 트리와 같은 형태를 이루지 않는 경우가 존재하였습니다. 예를 들어 하나의 노드를 선택하여 루트노드로 지정하였다면 다른 노드들은 자식 노드가 되는데, 특정 경우에 어떤 좌표를 루트노드로 지정하였는데 리프노드가 다시 루트노드와 이어지는 순환하는 형태를 나타냈습니다. 이러한 경우에 올바른 정답을 찾을 수 없었습니다. 이후 모든 좌표들을 한번씩 BFS를 이용하여 탐색하며 가장 먼 거리를 구하였고, 그 거리들 중 가장 긴 값을 계속해서 .. 2022. 6. 3. [백준] 1766 문제집 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 어떤 문제들을 풀어야만 다음 문제를 풀 수 있으므로 위상 정렬을 이용하여 풀이하였습니다. 처음 문제를 접하였을 때, 세번째 조건인 쉬운 문제부터 풀어야 한다는 조건을 만족시키기 위하여 한문제를 풀이하고 문제 번호가 낮은 문제부터 다시 탐색하며 풀이를 진행하였습니다. 그러나 반복문을 이용하여 계속해서 앞쪽 문제부터 순서대로 탐색을 진행하여 불필요한 탐색이 많아졌고 시간초과가 발생하였습니다. 시간을 단축하기 위하여 한 문제를 풀이하고 계속 처음 앞쪽 문제부터 탐색을 진행하는 것이 아니라 최소힙을 이용하여 먼저 풀어야하는 문제를 다 푼 경우 최소힙에 추가하였습니다. 이로 인하여 가장 쉬운 문제부터 푸는 조건을 만족시키며 시간 단축이 가능했습니다. 2) 알고.. 2022. 5. 30. [백준] 1655 가운데를 말해요 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 숫자가 순서대로 입력되었을때, 숫자들이 계속해서 정렬을 유지해야합니다. 초기에 하나의 큐를 이용하여 값을 정렬하고, 새로운 값이 들어올때 새로운 큐를 만들어 순서를 정렬하였으나 입력의 개수가 많아지게 되어 시간 초과가 발생하였습니다. 이후 최소힙과 최대힙을 이용하여 중간값을 유지시키도록 하였습니다. 중간값이 있을때, 중간 값보다 큰 값이 들어오는 경우, 최소힙에 새로운 값을 넣었습니다. 이렇게 하면 중간 값보다 크지만, 그 이후 값들은 작은 값들을 우선적으로 꺼낼 수 있습니다. 중간 값 보다 작은 값은 최대힙에 넣어, 중간 값과 가까운 수를 먼저 꺼낼 수 있도록 하였습니다. 숫자가 짝수개의 길이라면 두개의 값 중 작은 값을 꺼내야 하기에, 중간값보다 .. 2022. 5. 26. [백준] 14890 경사로 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 지나갈 길의 경우를 모두 리스트에 담아 두었고, 이 길을 돌아가며 경사로를 이용하여 지나갈 수 있는지 확인하였습니다. 경사로 가능 여부 조건을 확인하며 구현하였습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def solution(c): prev = c.pop() # 이전 땅의 높이 stack = [prev] # 경사로를 놓을 수 있는 여분의 땅 while c: # 다음 땅이 남아있다면 next = c.pop() # 다음 땅의 높이 if prev == next: # 이전 땅과 높이가 같으면 스택에 경사로 stack.append(next) # 여분땅 추가 e.. 2022. 5. 23. [백준] 16235 나무 재테크 📖 문제 🧑🏻💻 풀이 과정 1) 문제 풀이 문제 제한 시간이 아주 적기 때문에 계절별 로직을 함수로 만드는 경우 시간 초과 문제가 발생할 수 있습니다. 계절별로 한번에 처리가 가능한 경우들을 모아서 처리하는 방식으로 진행하였습니다. 처음 문제를 접근했을때, 나무들을 리스트를 이용하여 관리하는 경우에 년도가 흐를때마다 정렬을 해주어야 하기 때문에 최소힙을 이용하여 나무의 나이가 적은 순서대로 뽑아서 로직을 수행하려고 하였습니다. 그러나 최소힙은 push 와 pop 하는 과정에서 매번 O(logN) 의 시간복잡도를 갖고 있었고, 풀이에 오랜시간이 소요되었습니다. 이후 시간 단축을 위해 deque 를 이용하였습니다. 기존의 나무들은 시간의 흐름에 따라 나이가 1년씩 증가하거나 죽어서 없어지는 경우만 존재하고.. 2022. 4. 29. [프로그래머스] 지형 이동 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 2차원 배열의 각 좌표에 숫자 값이 적혀있고, 상하좌우로 인접한 좌표의 값의 차이에 따라 사다리를 사용하게 되는데, 사다리 이용하는 비용을 최소로 하는 방법을 구하여야 했습니다. 어느 한 좌표를 시작으로 하여 사다리 없이 이동이 가능한 좌표들을 모두 방문합니다. DFS 로 탐색하는 중에 인접한 좌표와 높이 차이가 있어 사다리가 필요한 경우에, 높이 차이의 값과 인접한 좌표를 최소힙에 기록하였습니다. 이후 모든 좌표를 방문하지 못하였을 경우, 최소힙에서 높이 차이가 가장 적은 다음 좌표를 이용하였습니다. 다음 좌표에서도 사다리 없이 이동 가능한 모든 좌표를 방문하며, 높이 차이를 최소힙에 기록하였습니다. 2) 알고리즘 DFS 최소힙 3) 풀이 코드 사용.. 2022. 4. 28. [백준] 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. 이전 1 2 3 4 5 6 7 8 ··· 12 다음
