본문 바로가기

알고리즘/백준

 (61)
백준[6987] 월드컵 (Python3) 정직하게 풀어야 했는데 편법쓰다 3번 틀린 문제 증명하는 방법이 복잡했기 때문에 완전 탐색으로 가야 했다. 동일한 조의 국가들은 다른 국가들과 1번씩 경기를 해서, 각 국가는 총 5번의 경기를 해야 한다. 따라서, 국가들이 경기를 하는 모든 경우의 수를 구한 다음 해당 국가끼리 경기를 했을 때, 이긴 경우, 비긴 경우, 진 경우 3가지에 대해 탐색을 한다. 총 15번의 경기를 하고, 매 경기마다 생기는 경우의 수가 3개이니 시간 복잡도는 O(3^15)이다 코드 더보기 import itertools records = [[0 for _ in range(3)] for _ in range(6)] match = list(itertools.combinations(range(6), 2)) ans = 0 def mai..
백준[16496] 큰 수 만들기 (Python3) 생각보다 쉬운 문제 파이썬이 아닌 언어로 풀었으면 조금 돌아가야 했을 것이다. 시도한 방법 1 입력된 수들을 가장 긴 자릿수만큼 자신의 일의자리 수를 더해준다. 예를 들어 입력이 432, 9999 가 들어온다면, 4322, 9999로 맞춰준다. 그다음 내림차순 정렬을 해, 원본 수를 이어붙인다. 반례로 98, 9888889가 들어오면 98이 먼저 와야 하는데 뒤로 가야 하는 문제가 발생했다. 다른 사람 코드 보는 과정에서 알았는데, 끝자리 수만 추가해주는게 아니라 해당 수를 적당히 이어붙이고, 앞에 10개만 가져와서 비교하면 됐었다. (10개만 가져오는 이유는, 수의 범위가 10억 이하이기 떄문) 시도한 방법 2 두 수 A, B가 있을 때, AB와 BA의 값을 비교한 다음 위치를 바꾼다. N의 범위가 매..
백준[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 하고, 다 태우지 못하면 남은 정원만큼 학생 수를 차감하는 식으..

티스토리툴바