전체 보기232 [백준] 1700 멀티탭 스케줄링 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 해당 문제를 처음 접했을 때, 앞으로 사용할 숫자들을 순환하면서 앞으로 사용하지 않거나 가장 적게 사용하는 숫자들을 제거하도록 구성하였습니다. 그러나 적게 사용하지만 일정 주기마다 해당 숫자를 사용해야하는 특정 상황이 발생하면, 해당 숫자를 위해 계속해서 값을 변경해주어야 합니다. 이로 인하여 최소 교환 횟수를 구하기 어려웠습니다. 위의 방법을 보완하여 앞으로 사용하지 않거나, 가장 나중에 사용하는 숫자를 우선적으로 제거하도록 하였습니다. 2) 알고리즘 그리디 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') # 가장 나중에 사용되거나 앞으로 사용하지 않을 숫자 반환 def get_fa.. 2022. 8. 16. [백준] 2206 벽 부수고 이동하기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 시작 좌표에서 도착 좌표까지 이동 시 최소 거리를 구할 필요가 있으므로 BFS 알고리즘을 이용하였습니다. 그리고 최대 한번 벽을 부수고 이동이 가능하므로 현재 이동에서 벽을 부수고 이동이 가능한지 여부도 계산이 필요했습니다. 기존의 BFS 이용 시 좌표별 거리 계산을 2차원 배열을 이용하였으나, 벽을 부수고 이동이 가능한지 여부를 기록하기 위하여 3차원 배열을 이용하였습니다. 크게 벽을 부수고 이동이 가능한 경우를 기록하는 2차원 배열과 벽을 부수지 않고 이동이 가능한 2차원 배열로 구분하였습니다. 다음 좌표의 벽 유무와 현재 조건에 따라 BFS 탐색을 하였고, 탐색이 모두 끝나면 두 2차원 배열에서 더 작은 값을 정답으로 출력하였습니다. 2) 알고리.. 2022. 8. 15. [백준] 1504 특정한 최단 경로 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 특정 출발점에서 목적지까지 도착하는 최단 경로를 구하기 위하여 다익스트라를 이용하였습니다. 또한, 거리 기록을 최초에 임의의 큰 값을 입력하여 도착 가능한 최단 경로를 구하도록 구성하였습니다. 두 지점의 노드를 필수적으로 통과해야 했으므로 '출발지 -> 노드1 -> 노드2 -> 도착지' 또는 '출발지 -> 노드2 -> 노드1 -> 도착지' 의 두가지 경우를 탐색하였습니다. 출발지, 노드1, 노드2 를 시작으로 하는 다익스트라를 세번 이용하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start: int.. 2022. 7. 30. [백준] 1719 택배 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 모든 집하장에 대하여 다른 집하장으로 이동하는 최소 소요시간을 구하여야 했습니다. 플로이드 워셜 알고리즘을 이용하여 모든 집하장에 대해 이동 최소 시간을 구하도록 하였고, 다른 집하장으로 이동시 가장 먼저 이동해야할 집하장을 기록하기 위하여 2차원 배열을 이용하였습니다. 우선적으로 주어진 경로들은 서로 연결되어 있으므로 가장 먼저 이동할 집하장으로 도착 집하장 번호를 기록하였습니다. 이후 플로이드 워셜 알고리즘을 이용할 때, 중간에 다른 집하장을 거쳐 이동하는 것이 더 빠른 경우가 있어 조건이 필요했습니다. 이러한 경우에는 중간에 거치는 집하장으로 가는 경로에 대해서 가장 먼저 이동하는 집하장을 가져와 기록하였습니다. 2) 알고리즘 플로이드 워셜 3).. 2022. 7. 18. [백준] 6087 레이저 통신 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 출발점에서 4가지 방향으로 진행을 시키고, 좌표에 도달하기에 필요한 거울의 개수를 기록하는 배열을 생성하였습니다. 큐를 이용하여 현재 좌표, 다음 진행 방향, 거울 사용 개수를 하나의 묶음으로 보관하였고, 탐색하였습니다. 그리고 방향 전환이 발생하는 경우에 거울 사용 개수에 1을 추가하였습니다. 2) 알고리즘 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') def solution(start): q = deque() for k in range(4): # 시작 좌표는 4가지 방향으로 시작할 수 있음 q.append((start[.. 2022. 7. 17. [백준] 15961 회전 초밥 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 초밥 벨트를 1차원 배열로 생성하고, K의 간격을 유지하며 연속해서 초밥들을 먹는 경우 탐색이 필요했습니다. 임시의 1차원 배열을 하나 생성하여 연속해서 먹는 초밥들을 기록하였습니다. 이후 집합을 이용하여 중복되는 초밥 종류를 하나로 인식하였고, 쿠폰의 초밥 종류도 집합에 추가하였습니다. 마지막으로 집합의 길이를 비교하며 최고 길이를 확인하였습니다. 그러나 배열을 이용하여 연속적으로 먹는 초밥의 종류를 기록하게 되면 배열을 계속해서 집합으로 변환하는 과정과 요소의 추가 제거, 집합의 길이를 카운트하는 과정이 필요하여 시간 초과 문제가 발생하였습니다. 이러한 문제를 해결하기 위해 초밥 종류의 개수만큼 크기의 1차원 배열을 생성하였고, 해당 초밥 종류를 .. 2022. 7. 16. [백준] 10217 KCM Travel 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 이전의 다익스트라 문제와는 조금 다르게 최소 거리 조건에 비용을 고려하여야 했습니다. 처음 문제를 풀이하였을 때, 1차원 배열을 이용하여 도시별 최소 소요 시간을 기록하였습니다. 그러면서 다음 목적지 탐색하는 과정에서 비용이 한도를 초과하는지 여부를 확인하였고, 한도를 넘지 않으면 무조건 최소 힙에 추가하여 탐색하는 과정으로 풀이하였습니다. 그러나 이 방법에는 최소 힙에 계속해서 요소가 추가되어 입력에 따라 메모리 초과가 발생하였습니다. 이후 2차원 배열을 이용하여 도시별 비용에 따른 최소 소요 시간을 기록하도록 하였습니다. 이를 통해 동일한 도시와 비용에 대한 중복적인 탐색이 발생하였을 때, 최소 소요 시간만을 기록할 수 있게 되었습니다. 그러나 이.. 2022. 7. 15. [백준] 6549 히스토그램에서 가장 큰 직사각형 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 특정 구간의 직사각형 너비를 구하기 위해서는 그 구역의 최소 높이를 알아내야 했습니다. 그리하여 세그먼트 트리를 이용하여 특정 구간의 최소 높이와 최소 높이에 해당하는 숫자의 인덱스 번호를 기록하였습니다. 이후 전체 구간을 시작으로 하여 해당 구역의 직사각형 넓이, 최소 높이의 인덱스를 기준으로 왼쪽과 오른쪽의 직사각형 넓이를 구하였습니다. 분할정복을 이용하여 왼쪽과 오른쪽을 재귀적으로 직사각형의 넓이를 구하며 최대 넓이를 구하였습니다. 2) 알고리즘 세그먼트 트리 분할정복 3) 풀이 코드 사용 언어 - Python import sys sys.setrecursionlimit(100000000) sys.stdin = open('input.txt') de.. 2022. 7. 14. [백준] 14226 이모티콘 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 한번의 연산이 발생할 때, 세가지의 방법 중 하나로 연산이 일어났습니다. BFS를 이용하여 현재 이모티콘, 클립보드 길이의 상황에서 세가지 연산을 모두 큐에 추가하여 탐색을 이어나갔습니다. 한번 탐색한 경우는 추가 탐색을 하지 않기 위하여 탐색 여부를 확인하였습니다. 탐색 여부는 딕셔너리 형태를 이용하였고, 키 값으로는 (이모티콘 길이, 클립보드 길이) 의 튜플 형태로 기록하였습니다. 2) 알고리즘 다이나믹 프로그래밍 BFS 3) 풀이 코드 사용 언어 - Python import sys from collections import deque sys.stdin = open('input.txt') S = int(sys.stdin.readline()) # 목.. 2022. 7. 13. [백준] 17135 캐슬 디펜스 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 재귀를 이용하여 궁수 3명이 놓일 수 있는 좌표의 조합들을 1차적으로 구하였습니다. 궁수들 위치의 조합별로 조건에 맞게 구현하여 모든 경우를 탐색하여 제거할 수 있는 적의 수를 확인하였습니다. 각 궁수별로 제거할 적의 정보를 1차원 배열로 생성하여 기록하였습니다. 모든 적과 모든 궁수가 서로 거리를 비교하였고, 적이 사정거리에 들어왔는지 판별하였습니다. 이후 적의 거리가 더 가깝거나, 거리가 같다면 더 왼쪽에 있을 때 배열의 값을 갱신하였습니다. 이후 배열에 기록된 타겟들을 적의 명단에서 제거하였고, 여러 궁수가 같은 적을 동시에 맞추는 경우도 존재하였습니다. 같은 적을 2번 쏜것을 제거한 적 2로 카운트 하지 않기 위하여 집합을 이용하여 실제로 제거.. 2022. 7. 12. [백준] 17143 낚시왕 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 좌표별로 상어의 정보를 기록하고 관리를 잘하는 것이 중요했습니다. 2차원 배열을 생성하고 낚시왕의 이동이 진행될 때마다 모든 좌표를 탐색하는 방법은 시간이 오래 걸려 비효율적이라 생각하였습니다. 그리하여 상어들의 정보를 딕셔너리(객체) 형태로 관리하였습니다. 상어의 좌표를 키로 하고, 속력/방향/크기 의 정보는 값으로 지정하였습니다. 상어를 잡는 것과 낚시왕의 이동은 어렵지 않았는데, 상어들의 속력에 따라 좌표 이동을 계산하는 규칙을 찾는 것이 어려웠습니다. 상어는 진행방향으로 주어진 속력의 칸만큼 이동이 되는데, (행 또는 열의 크기 - 1) * 2 의 속력을 갖게 되면 제자리로 돌아오는 규칙이 있습니다. 문제 예제 1번의 상황을 보면 B상어가 수직.. 2022. 7. 11. [백준] 15684 사다리 조작 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 문제를 풀이하기 위하여 몇가지 조건 사항을 구현해야 했습니다. 어느 한 열에서 출발하여 본인의 열로 돌아와야 한다. 가로 선이 연속으로 설치 되어서는 안된다. 가로선은 최대 3개까지 설치가 가능하고, 최소로 설치해야한다. 1번 조건을 위해 사다리 정보를 표현하는 2차원 배열을 만들었고, 가로선이 만들어지면 2개의 좌표가 영향을 받습니다. 그리하여 가로선이 생기는 두개의 좌표에서 좌표를 기준으로 오른쪽에 가로선이 생기면 1을 기록하고 왼쪽으로 생기면 -1을 기록하였습니다. 이러한 값 설정으로 열에서 사다리를 타고 내려올 때, 좌표의 값에 따라 오른쪽이나 왼쪽으로 이동 여부를 판별할 수 있었습니다. 또한, 변수의 증가량 여부에 따라 원래 본인 열로 돌아오.. 2022. 7. 10. 이전 1 2 3 4 5 ··· 20 다음
