백준136 [백준] 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. [백준] 15685 드래곤 커브 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 끝점에서 시계 방향으로 90도를 회전하였을 때, 어느 한 점이 끝점을 기준으로 하여 좌표에 어떤 변화가 일어났는지 알아야 했습니다. 90도 회전시 좌표 값의 변화량만 알게 되면, 드래곤 커브의 세대별 좌표를 모두 알아낼 수 있습니다. 문제 예제 1번에서 첫 입력을 예를 들어 (3,3) 을 시작으로 하면, 시작 방향에 따라 끝점은 (4,3) 가 됩니다. 이때 시작점과 끝점을 비교하면, x좌표는 1이 증가하고 y좌표는 변화가 없습니다. 이때 끝점을 기준으로 회전하면 (3,3)의 좌표가 (4,2)로 이동됩니다. 끝점이였던 (4, 3)와 변화된 좌표 (4,2)를 비교하면 x는 변화가 없고, y는 1이 감소하게 됩니다. 이를 토대로 x좌표 증가량만큼 y좌표가 .. 2022. 7. 9. [백준] 18436 수열과 쿼리 37 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 반복적으로 특정 구간의 홀수, 짝수의 개수를 확인해야 하는 문제입니다. 2진 트리를 생성하여 수열의 값들을 리프 노드에 순서대로 기록하고, 부모 노드는 특정 수열의 범위의 값들을 기록하는 세그먼트 트리를 이용하였습니다. 세그먼트 트리의 각 값은 튜플 형태로 (짝수의 개수, 홀수의 개수) 형태로 기록하였습니다. 2) 알고리즘 세그먼트 트리 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') def make_segment_tree(node, start, end): # 세그먼트 트리 생성 if start >= end: # 리프 노드인 경우 if nums[start] % 2: # 수열 홀수 짝수.. 2022. 7. 8. [백준] 10423 전기가 부족해 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 발전소가 존재하는 도시에서 출발하여, 다른 도시로 전기가 제공되기 위해 케이블을 설치해야 했습니다. 케이블 설치 비용이 적게 하여 설치가 필요하여, 가중치를 고려하여야 했습니다. 케이블 설치 비용을 적은 것부터 탐색하여 설치하기 위하여 최소힙을 이용하였습니다. 발전소가 있는 도시들을 모두 최소힙에 넣어두고, 탐색을 시작하였습니다. 다음으로 연결된 도시를 케이블의 가중치와, 연결된 도시의 번호를 최소힙에 추가하였고, 케이블 설치 비용이 낮은것부터 설치하도록 하였습니다. 2) 알고리즘 최소 신장 트리 최소힙 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def s.. 2022. 7. 7. [백준] 2623 음악프로그램 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 PD들이 정한 가수의 순서를 모두 만족시키기 위하여, 어떤 한 가수가 순서가 되기 위해서는 그 가수의 앞에 오는 가수들이 모두 순서가 정해졌어야 합니다. 이러한 조건을 만족시키며 순서를 정하기 위해 위상정렬을 이용하였습니다. 2) 알고리즘 위상정렬 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N, M = map(int, sys.stdin.readline().split()) # 가수, 보조PD 수 next = [[] for _ in range(N)] # 각 가수 다음에 순서와야 하는 가수 need = [0] * N # 가수 순서 오기 위해 필요한 앞 사람 수 answers = [] .. 2022. 7. 6. [백준] 2660 회장뽑기 📖 문제 🧑🏻💻 풀이 과정 1) 문제 접근 및 이해 한 사람이 다른 모든 사람과의 관계 거리가 어떻게 되는지에 대한 정보를 모든 사람을 기준으로 하여 구하여야 했습니다. 처음에 BFS를 이용하여 다른 사람들과의 관계 거리를 구하려 하였으나, 사람의 수가 많아지는 경우에 사람 수에 맞게 BFS 탐색이 필요했습니다. 이러한 경우에 시간 초과 문제를 고려하게 되었고, 이 문제에 조금 더 적합할것 같은 플로이드 워셜을 이용하여 풀이하였습니다. 2) 알고리즘 플로이드 워셜 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') N = int(sys.stdin.readline()) # 사람 수 answers = [[1e10] * N for _ in ra.. 2022. 7. 5. 이전 1 2 3 4 5 ··· 12 다음
