본문 바로가기

알고리즘

 (82)
백준[17616] 등수 찾기 (Python3) 전형적인 그래프 탐색 문제를 응용했다. 이 문제에서 주목할 점은, 정점 X와 뒤, 앞으로 연결된 정점 개수를 파악하는 것이다. 즉, bfs를 두 번 돌려야 한다. 예제 3을 기준으로 보면 우리가 보려는 노드는 정점 1이니, 이 기준으로 본다면 정점 1과 3이 연결돼있고, 3은 4, 5와 연결돼있으니, 정점 1의 뒤엔 3, 4, 5가 있다. 정리하면, 정점1의 뒤에 있는 정점 개수는 3고, 앞에 있는 정점 개수는 0개다. 반면, 정점 2는 정점 1과 어떤 방향으로 연결돼있는지 알 수 없다. 정점 3보다 앞에 있단 것만 알지, 정점 1의 어느쪽에 연결돼는지를 알 수 없다. 다행인건 문제에서 가능한 등수의 최소, 최대만 구하는 것이기 때문에, 애매한 정점들은 하나의 경우에 묶어 생각할 수 있다. 1. 정점 1..
백준[15973] 두 박스 (Python3) 상황별로 여러 분기가 필요한 문제. 완전탐색 노가다로 모든 경우에 대해 조건을 작성한다. 풀 수는 있지만, 코드가 너무 길어지고 중간에 WA를 받기라도 한다면 너무 피곤해진다. 완전탐색 최적화 도형의 순서를 정한다. 예를 들자면, 두 도형이 있을 때, x축을 기준으로 왼쪽에 있는 도형은 반드시 하나가 있을 것이다. 나는 왼쪽에 오는 박스를 A, 오른쪽에 오는 박스를 B로 정해 고려할 경우의 수를 반으로 줄였다. 그 다음 박스 A의 x2 좌표와 박스B의 x1 크기를 비교하면, 분기 초입을 2가지로 축소할 수 있다. 편의상 박스 A의 x2는 Ax2식으로 표기한다. + Ax2 == Bx1 + + 특정 값들이 같다면 POINT이다. + + Ay1, By1, By2 가 특정 값 범위라면 LINE이다. + Ax2 ..
백준[19585] 전설 (Python3) TLE 해결법을 몰라서 풀이 살짝 본 문제 딕셔너리 키값이 아스키 문자 하나인 경우, 숫자로 바꿔주는 게 TLE 받을 일이 적어질 거란 것을 알았다. 시간 초과 - 재귀 풀이 색상 이름이 aa, aaa인 경우 비교 과정에서 aa에서 색상 이름 비교를 중단하고 닉네임을 비교할지, 색상을 마저 비교할지에 대해 분기를 태워야 한다 생각했다. 80%대에서 TEL를 받았다. 문자열 뒤집기 다른 사람들 풀이 보고 적용한 풀이 색상 같은 경우 그냥 앞에서 비교하면 되지만, 닉네임 같은 경우 어디부터 시작할지를 모른다. 하지만 확실한 것은 수상할 팀명의 마지막은 무조건 닉네임이 들어간다. 따라서 닉네임을 입력받을 때, 뒤집어서 입력받고 비교하는 부분도 팀명을 뒤집어서 비교한다. 이 과정에서 문자열의 끝을 의미하는 토큰..
백준[14867] 물통 (Python3) 독해력이 필요한 문제. 지문 분석을 잘못해 그리디로 생각해버렸다. 다른 물통에 물을 옮길 땐, 제한을 넘지 않는다면 '모두 옮겨야' 하는 건데, 일부만 넣을 수 있다고 이해해서 고생 좀 했다. dp나 방문 처리를 해서 풀기엔 a, b의 범위의 최대 값이 100,000이기 때문에 메모리 초과가 발생한다. 이 방문 처리를 어떻게 할지 생각한 결과 set을 사용하기로 했다. 완전 탐색 다음 6가지에 대해 생각할 수 있다. 물통 A를 가득 채운다. F(A) 물통 B를 가득 채운다. F(B) 물통 A를 비운다. E(A) 물통 B를 비운다. E(B) 물통 A의 물을 B로 옮긴다 M(A, B) 물통 B의 물을 A로 옮긴다 M(B, A) 다만 5, 6의 경우 물을 '다 옮기면' 제한을 넘는지 확인할 필요가 있다. 이 ..
백준[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..

티스토리툴바