본문 바로가기

알고리즘/백준

 (61)
백준[17615] 볼 모으기 (Python3) 관찰이 필요한 문제 모든 경우에서 볼들을 이동시킨 결과는 [빨강, 파랑] 또는 [파랑 빨강]이 나오게 된다. 따라서, 끝 점의 볼들을 센 다음, 가장 많은 종류의 볼들이 모인 곳을 기준으로 다른 볼들을 움직여야 한다. 이제 4가지 경우에 걸쳐 끝점의 볼을 기준으로 같은 종류의 볼을 모은다. 즉, 맨 왼쪽이 빨간색이라면, 다른 위치에 있는 빨간 볼을 모두 왼쪽으로 모은다. 4가지 경우는 다음과 같다. 1. 맨 왼쪽이 빨간 볼인 경우. 2. 맨 왼쪽이 파란 볼인 경우 3. 맨 오른쪽이 빨간 볼인 경우 4. 맨 오른쪽이 파란 볼인 경우 위 4가지 경우를 통해 움직여진 볼의 개수의 최소값이 답이다. 더보기 N = int(input()) redC, blueC = 0, 0 S = input() for s in S:..
백준[1092] 배 (Python3) 풀이 방향은 금방 알았지만 구현 과정에서 많이 짜증났던 문제. 파이썬 포문에선 인덱스 변수 증감이 안 되다 보니 억지로 맞추다가 2번정도 틀렸다 다른 사람들 풀이보니까 remove를 썼던데 그냥 나도 remove를 썼다면 한번에 풀지 않았을까란 생각이 든다. 지문 분석 무거운 크레인은 무거운 박스를 우선으로 들어야 한다. 가벼운 것 부터 들게 된다면, 박스는 점점 무거워지고, 그 과정에서 노는 크레인들이 발생하기 때문이다. 박스와 크레인을 내림차순 정렬해야 한다. 완전 탐색 옮길 박스가 현재 매달려는 크레인에 달 수 있는지 본다. 만약, 그렇지 않다면 해당 박스는 건너뛰고 다음 박스를 달 수 있는지 본다. 이렇게 모든 크레인을 한번씩 순회하면 전체 시간을 1 증가시킨다. 이제 남은 박스들을 가지고 위의 ..
백준[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 였던 점을 이용해 백트래킹을 사용했다. 또한, 사전에 등록된 한 단어에 도달하는 과정에서 다른 단어들을 충족한 경우 이 단어들도 같이 계산해줬..

티스토리툴바