본문 바로가기

전체보기

 (180)
백준[17610] 양팔저울 (Python3) 추를 통해 잴 수 없는 모든 경우의 수를 세는 문제 처음에 시간 복잡도 계산을 잘못해서 맞는 풀이임에도 계속 고민하다 생각보다 시간을 오래 썼다. 애매한 지식이 실수를 만들었다. 완전 탐색 3가지 경우에 대해 생각할 수 있다. 추를 놓지 않는 경우 추를 올려놓는 경우 추를 반대쪽에 올려놓는 경우 2번의 경우 현재 무게에서 +를 해주고, 3번의 경우 -를 해준다. 이렇게 나오는 각 무게들에 방문 표시를 해준 뒤 1부터 모든 추의 합까지 탐색하면서 방문 처리되지 않은 값을 세면 된다. 더보기 from collections import defaultdict class Trie: def __init__(self): self.root = {} self.name = defaultdict(lambda: 1) def ..
백준[9202] Boggle (Python3) 그래프를 이용해 푸는 트라이 문제 신경써야 할 부분이 중간중간 있기 때문에 한번 논리가 꼬이면 고생한다. 지문 분석 현재 이동한 곳의 경로가 사전에 등록된 단어가 될 수는 없지만, 돌아서 가는 경우 등록된 단어일 수있다. 예를 들자면 현재 주사위에 다음과 같이 써져있다 하고 사전에 등록된 단어는 CDBA라 하자. AB CD C에서 탐색을 시작한다 할 때, 바로 A로 가면 사전에 등록된 단어가 되지 않지만, C->D->B->A 순으로 가면 사전에 등록된 단어가 된다. 따라서 bfs로 하기엔 각 큐마다 방문 상태를 별개로 저장해야 하는 불편함이 있었고, 범위가 4*4 였던 점을 이용해 백트래킹을 사용했다. 또한, 사전에 등록된 한 단어에 도달하는 과정에서 다른 단어들을 충족한 경우 이 단어들도 같이 계산해줬..
백준[10165] 버스 노선 (Python3) 관찰이 필요한 정렬 문제 막상 풀고 보면 그렇게 어렵진 않은데, 순환 구조 때문에 생각이 계속 꼬였다. 지문 분석 맨 처음엔 0번 정류소를 지나치는 노선을 2개로 분리해서 볼려 했지만 시간 초과를 받았다. 또한, 분리된 두 노선이 다른 어떤 노선과 포함되거나 포함하는지를 검증하는 과정이 매우 까다로웠다. 따라서, 노선을 쪼개기보다는 각 노선 시작점 또는 도착점 위치를 변경하는 방식으로 풀이를 생각했다. 시도한 방법 1 정류장이 원형이 아닌 무한한 일자 형태라고 가정한다. 0번 정류소를 지나치는 노선 중, 시작점과 0번 정류소 간의 거리가 가장 긴 값을 찾는다. 그 후, 모든 정류소 시작, 도착 위치를 그 값만큼 더해준다. 이 경우 예제 2번이 반례가 됐다. 시도한 방법 2 각 노선들의 시작점과 도착점을 ..
백준[10836] 여왕벌 (Python3) bfs로 풀었다면 시간초과를 받았을 문제 정올 문제답게 관찰이 필요한 문제이다. 문제를 보면 흥미로운 사실을 하나 알 수 있는데 애벌래들의 초기 성장 수치는 오른쪽으로 갈 수록 커진다. 그리고 애벌래들은 왼쪽, 왼쪽 위, 위쪽만 확인한다. 즉, 왼쪽 위보단 위쪽이 위치상으로는 더 오른쪽으로 있기 때문에 그냥 위쪽 값만 보면 된다. 즉, (1, 1)부터 (M, M)까지의 애벌래들은 각각 (0, 1) ~ (0, M)의 애벌래의 성장 수치를 그대로 받는다. 또한, 모든 애벌래의 성장 수치는 첫행, 첫열의 애벌래와 똑같고, 추가로 고려할 사항은 없다. 따라서 첫행, 첫열 애벌래들의 성장 수치를 더한 뒤 나머지 애벌래들은 바로 위쪽 애벌래의 성장 수치 합을 그대로 가져다 쓰면 된다. 더보기 M, N = map(i..
백준[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..

티스토리툴바