본문 바로가기

알고리즘

 (82)
백준[16934] 게임 닉네임 (Python3) 제한 시간 2초 치고는 데이터 범위가 작다 싶었는데, 키가 문자열이라 그런지 생각보다 실행 시간이 길었다. 트라이를 사용해 풀었다. 생각이 필요했던 부분이 입력된 입력된 닉네임이 고유한 닉네임이면 접두사를 별칭으로 해주고, 다음에 같은 닉네임을 입력받으면, 닉네임 + 중복 수를 별칭으로 해줘야 하는 거였다. 따라서, 삽입 전에 탐색을 통해 중복되는 닉네임이 있는지 확인할 필요가 있었다. 탐색에선 먼저 접두사를 구한 다음, 구해진 접두사의 길이가 닉네임의 길이와 같다면 중복된 닉네임으로 간주해 해당 닉네임의 카운트를 붙인 별칭을 반환해 출력했다. 코드 from collections import defaultdict class Trie: def __init__(self): self.root = {} self..
백준[13505] 두 수 XOR (Python3) XOR 연산으로도 풀 수 있지만, 트라이로 풀었다. XOR 연산이 1과 0으로 이루어지기 때문에, 각 수들을 이진수로 변환한 값들을 트라이로 만들어주면 된다. 편의상 최대 자릿수를 구한 다음, 이 길이에 맞춰 다른 이진수들에 padding 값으로 0을 붙였다. 이걸 안 해주니 탐색 코드에서 이진수 자릿수까지 검증해야 해서 불편했다. 탐색 과정은 다음과 같다. 현재 자릿수와 반전되는 수가 노드에 있는지 본다. (1이면 0, 0이면 1) 있다면 임시 배열에 1 추가. 아니면 0 추가 임시 배열에 있는 값으로 십진수 변환 코드 class Trie: def __init__(self): self.root = {} def insert(self, S): current_node = self.root for s in S..
백준[17612] 쇼핑몰 (Java, Python3) 자료 구조를 만들어 정렬하거나 관찰을 통해서 풀 수 있는 문제 추가시간이 없기 때문에, 10^7 내에 끝내야 한다. 완전 탐색 매초 각 계산대의 물건 카운팅을 1씩 감소시키면서 0이 된 계산대엔 새로운 대기자를 넣는다. 시간 복잡도 계산을 하면서 헷갈렸던 게 고객은 큐로 관리하고, 계산대만 루프를 통해 확인하는 식이기 때문에 O(KW)로 완전 탐색이 가능하다 생각했지만 골 2란 점이 계속 신경 쓰였다. 그래서 조금 최적화하는 방향으로 갔다. 완전 탐색 최적화 계산대를 탐색하는 빈도를 줄이는 방향으로 갔다. 현재 계산대에 물건이 가장 적은 값을 찾는다. 모든 계산대에 그 값만큼 빼준다. 모든 계산대의 물건값이 0이면서 대기 큐가 빌 때까지 반복한다. 우선순위 큐 태그를 확인하니 우선순위 큐 문제길래, 여기..
백준[16928] 뱀과 사다리 게임 (Python3) 테스트케이스 짜보는 연습해 보기 좋은 문제 완전 탐색 현재 지점부터 +1 ~ +6까지의 지점을 갔을 때에 대한 결과를 큐에 넣고, 100이 될 때까지 탐색한다. 하지만, 뱀을 만나게 되면 다시 돌아가게 돼서 그 지점부터 탐색이 계속 진행되기 때문에 무한 루프가 된다. 완전 탐색 최적화 1에서 7을 가는 최단 경로는 주사위 6이 나와서 이동하는 경우다. 그 외의 방법으로 가는 경우는 비효율적이므로 배제한다. 따라서, 방문 처리 배열을 하나 만들어 이동할 지점에 도달하기 위해 굴린 주사위 수가 현재 굴린 주사위 수 + 1보다 크면 큐에 현재 정보를 추가한다. 주의해야 할 점 사다리를 탈 때 무작정 이 사다리가 더 높이 간단 이유로, 그 사다리만 골라서 가면 안 된다. 뱀을 통해 내려간 곳 근처에 있는 사다리..
백준[13904] 과제 (Python3) 큐 + 정렬로 풀었는데 태그 까보니 우선순위 큐로도 풀 수 있었던 문제 N의 범위가 작기 때문에 완전 탐색으로 풀 수 있다. 지문 분석 최대한 점수를 많이 주는 과제를 해결해야 한다. 단, 기한이 충분하다면 기간이 얼마 안 남은 다른 과제를 푸는 게 더 유리한지 확인한다. 완전 탐색 날짜를 기준으로 오름차순 정렬한다. N 개의 -1 원소를 갖는 일차원 배열을 선언한다. 각 인덱스는 1일, 2일 ... N일이다. 만약 그날 얻을 수 있는 점수가 -1이고, 제출 기한 내라면, 현재 과제 점수를 넣는다. 그게 아니라면, 1일부터, 그 이전까지 얻은 과제 중 최솟값을 찾아 교체한다. 이를 반복하면 O(N ^ 2)로 해결 가능하다. 더보기 def main(): N = int(input()) works = [] f..
백준[2513] 통학버스 (Python3) 2023 카카오 코테 2번? 하고 똑같다. 코테에서도 무난하게 풀어서 그런지, 생각보다 큰 어려움은 없었다. 지문을 분석해 보면, 버스는 가장 먼 거리에 있는 아이들을 우선으로 태우는 것이 유리하다. 또한, 버스 정원을 다 채우기 위해 왼쪽 오른쪽 왔다 갔다 할 필요가 없다. 학교를 기준으로 왼쪽, 오른쪽에 대한 큐 2개를 만들었다. 단지의 위치가 학교보다 왼쪽에 있다면, (학교 위치 - 단지 위치, 학생 수) 형태로 넣고 학교보다 오른쪽에 있다면, (단지 위치 - 학교 위치, 학생 수) 형태로 넣는다. 그 후 위치 값을 기준으로 정렬한다. 그 후, 단지의 학생 수와 버스 정원을 비교해, 다 태울 수 있다면, 해당 단지에 대한 정보를 pop 하고, 다 태우지 못하면 남은 정원만큼 학생 수를 차감하는 식으..
백준[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 증가시킨다. 이제 남은 박스들을 가지고 위의 ..

티스토리툴바