본문 바로가기

알고리즘

 (82)
백준[1467] 수 지우기 (Python3) 생각보다 골 때리는 문제지만, 플2 치곤 약한 거 같다. 스택으로 풀면 쉽게 풀 수 있는데 왜 스택 태그가 없는지 의문 완전 탐색 입력된 N 자릿수를 지우는 모든 경우에 대해 구한다. 하지만 적당히 많은 수를 지우게 된다면 시간 초과를 받는다. 예를 들자면, N = 1000, 지워야 할 수가 300개이면 1000C300으로 시간 초과를 받는다. 완전 탐색 최적화 지우려는 수가 입력된 N의 맨 끝에 있을 수 있으니, N은 처음부터 끝까지 탐색해야 한다. 여기서 무엇을 출력할지, 무엇을 지울지 2가지를 기준으로 잡고 최적화를 할 수 있다. 나는 무엇을 출력할지에 대해 스택 자료구조를 가지고 다음 기준을 잡았다. N의 각 자릿수와 지워야 할 수들에 대해 카운팅을 한다. 스택의 상단과 현재 자릿수 n을 비교해 ..
백준[10835] 카드게임 (Python3) 처음에 잘못 생각해서 그리디하게 풀다 반례를 못찾아서 고통받았다 태그 확인해보니 dp여서 많이 당황했던 문제 그리고 몰랐는데, 파이썬으로 재귀 호출 10^ 6으로 하면 바로 메모리 초과 나더라. 10^6이 생각보다 메모리 공간을 많이 먹는듯 룰을 분석하면 3가지다. 1. 왼쪽만 버린다. 2. 왼쪽, 오른쪽 둘 다 버린다. (점수 X) 3. 왼쪽 > 오른쪽인 경우 오른쪽을 버린다. (점수 O) 처음 상태부터 경우의 수를 키워나가는 것이 편하게 풀 수 있다 생각해 bottom-up 방식으로 풀었다. 재귀함수의 기저는 왼쪽 또는 오른쪽의 카드 더미가 0일 때이고, 기존에 계산된 값이 있다면 그 값을 반환한다. 이제, 왼쪽 상단과 오른쪽 상단을 비교해 오른쪽이 크다면, 오른쪽 상단을 버리고 그게 아니라면, 둘다..
백준[8980] 택배 (Python3) 쉬운 줄 알았는데 생각보다 많이 어려웠던 문제. 정렬 기준을 잘못 잡아서 삽질을 좀 했다. 지문 분석 트럭이 가장 많은 박스를 배송할 경우는, 박스들이 많이 있는 상황이다. 즉, 처음 출발할 때만 보면 된다. 그리고 박스를 최대한 많이 보내기 위해선, 박스들의 도착지가 현재 위치와 최대한 가까워야 한다. 따라서, 기존에 담긴 박스보다 새로 담을 박스가 더 배송지가 가깝다면 기존에 담긴 박스를 필요한 만큼 버린다. 지문에선 버린다는 표현은 없지만 나는 이런 식으로 이해하는 게 더 지문 분석이 쉬웠다. 시도한 방법 1 각 마을들에 대한 큐를 만들어 박스 배송 정보를 넣어준다. 트럭은 1번 마을부터 시작해 박스를 내리고 싣는다. 하지만 이 방법은 트럭에 있는 박스 배송 정보들이 출발지, 도착지 순으로 정렬된 ..
백준[2212] 센서 (Python3) 관찰이 필요한 문제 생각하는 방향에 따라서 어렵게 풀 수도 있고, 쉽게 풀 수도 있다. 지문 분석 수신 가능 영역의 길이를 최소화하기 위해선, 센서 간의 거리가 큰 곳부터 집중국을 설치해야 한다. 예제 2를 기준으로 센서들의 위치를 나열하면 3 6 7 8 10 12 14 15 18 20 이 되는데 정답이 되도록 집중국을 설치하면, 집중국의 포함 범위는 다음과 같다. 3 / 6 7 8 / 10 12 / 14 15 / 18 20 이제 각 집중국을 /로 나눈 영역 내 최대 1개의 아무 센서에 설치하면 된다. 예를 들자면, 6 7 8 위치에 있는 센서들 기준으로, 집중국은 6에 설치하나 7에 설치하나 해당 영역에서의 수신 가능 영역 길이는 항상 2이다. 또한, 빗금 친 곳 기준 간격을 재보면 3, 2, 2, 3..
백준[16906] 욱제어 (Python3) dfs만 써도 풀 수 있지만, 연습을 위해 트라이를 사용했다 예제 볼 때는 단어 길이가 오름차순인줄 알았지만, 제출하고 보니 무작위였다. 트라이 풀이 매 탐색마다 0 또는 1을 붙이는 2가지 분기로 나뉜다. 만약, 현재 만들어진 단어가 다른 단어의 접두사인 경우(트라이에 끝이 명시돼 있음) 탐색을 중단하고 다른 단어를 알아봐야 한다. 이렇게 생긴 문자열이 만들려는 단어 길이와 일치하면 해당 단어를 트라이에 추가해준다. 더보기 import sys sys.setrecursionlimit(10 ** 5) class Trie: def __init__(self): self.root = {} self.answer= [] def insert(self, word): current_node = self.root for ..
백준[19942] 다이어트 (Python3) 문제 자체는 쉬웠지만, 최적의 경로를 사전 순으로 빠른 것을 출력하란 것 때문에 생각이 좀 필요했던 문제. 하지만, 그렇게 어렵게 생각할 필요는 없는 문제였다. 최적의 답을 찾기 위해, 재료를 순서대로 탐색하며 먹을지, 안 먹을지 결정하면 된다. 즉, 매 순간 2가지 선택지가 있으므로, 2^15만큼의 시간 복잡도가 필요하다. 따라서 백트래킹을 사용해 문제를 풀이했다. 사전 순으로 빠르게 출력하란 것은 내가 첫번째 인덱스부터 탐색을 했다면, 신경쓸 필요가 없다. 왜냐하면, 백트래킹 탐색 순서가 낮은 인덱스부터 차례대로 올라가기 때문이다. 탐색한 경로를 리스트 형태로 관리하면서, 기존보다 적은 비용으로 목표 영양소를 섭취할 수 있다면 기존 값을 교체한다. 백트래킹을 쓰지 않는 경우, 파이썬이라면 i tert..
백준 [15971] 두 로봇 (Python3) 처음부터 꼬아서 생각했다가 복잡하게 푼 문제 경로를 계산하는 방법은 3가지가 있다. A가 한 칸 뒤로 가고, B가 한 칸 앞으로 감. B가 한 칸 뒤로 가고, A가 한 칸 앞으로 감. A, B가 그냥 현재 위치에서 통신 위 3가지 경우를 고려하면 A부터 출발하든, B부터 출발하든 특정 간선 하나는 지나지 않는다. 이 간선은 바로 A부터 B 또는 B부터 A까지 가는 간선 중 가장 비용이 큰 간선이다. 이렇게 구한 총 비용 중, 가장 큰 비용을 빼면 답이 나온다. 나는 위 3가지 경우를 다 고려해서 A부터 B까지 모든 경로 구한뒤에 B부터 탐색을 시작해, 매 지점마다 저 3가지를 고려했다. 그래도 N의 범위가 작기 때문에 통과는 됐지만 좋은 해결책은 아니었다. from collections import de..
백준[17671] 로봇 (Python3) 다3 치고 생각보다 풀만했던 문제. 관찰을 하면서 탐색 범위를 조금씩 좁혀나간다면 충분히 해결할 수 있다. 랑이집사님이 알려주신 완전 탐색부터 시작하는 최적화를 잘 써먹은 문제 완전 탐색 로봇의 움직임을 3가지를 나눠 계산한다. 1. 왼쪽으로 한 칸 갈 때 2. 가만히 있을 때 3. 오른쪽으로 한 칸 갈 때 이 방법으로 문제를 해결할 경우 O(3^N)으로 시간 초과가 난다. 이를 줄이기 위해, 로봇이 움직이는 거리를 높이거나, 일부 로봇은 움직이지 않는 식으로 탐색 범위를 좁혀나가야 한다 생각했다. 완전탐색 최적화 1 처음부터 로봇을 최소한만 겹칠 수 있게 이동 겹치게 된다면 안 겹치도록 입력된 위치에서 + 를 해준다. 하지만, 이 방법은 로봇들이 서로 가까이에 있다면, 불필요하게 많이 이동하는 경우가 ..

티스토리툴바