기록

문제 보기 [사용한 알고리즘] 그리디 [문제 접근] 주어진 단어들의 각 알파벳들의 가치를 계산한 후에 숫자를 대입하고자 하였습니다. [알고리즘] 1. 알파벳의 가치를 계산합니다. 예를 들어서 1의 자리 숫자이면 + 1, 10의 자리 숫자이면 + 10을 더해 각 알파벳들의 가치를 정수로 표현합니다. 2. 가치가 가장 높은 알파벳부터 숫자를 대입합니다. 3. 모든 단어들의 합을 계산한 후 출력합니다. [주의할 점] 처음에는 가중치가 아니라 가장 앞에 있는 알파벳부터 숫자를 대입하고자 하였습니다. 하지만 가장 앞에 있는 숫자부터 대입하면 예외가 발생합니다. 예를 들어서 ABB + BB + BB + BB + BB + BB + BB의 경우 A에 9, B에 8을 대입하는 것이 아니라 A에 8, B에 9를 대입하는 ..

문제 보기 [사용한 알고리즘] 완전 탐색(브루트 포스), 순열 [문제 접근] 1번 선수를 제외한 8명(2~9번) 선수의 가능한 타순을 모두 수행해야만 아인타팀이 얻을 수 있는 최대 점수를 알아낼 수 있습니다. 따라서 가능한 타순은 순열을 통해 파악하였으며, 얻은 순열 값들을 완전 탐색하였습니다. [알고리즘] 1. 순열을 통해 타순을 구합니다. 2. 해당 타순으로 N 이닝을 수행한 점수를 구합니다. 3. 위 과정을 가능한 모든 타순에 대해 수행하고 최대 점수를 출력합니다. [주의할 점] Python3로는 통과한 사람이 없었으며 pypy3도 시간 초과를 위해서 고려할 부분이 많았습니다. 저는 시간 초과를 해결하기 위해서 2가지를 고려하였습니다. - 1, 2, 3루 베이스 정보를 배열이 아닌 변수 값을 사용하..

문제 보기 [ 사용한 알고리즘 ] 완전 탐색(브루트 포스) [ 문제 접근 ] 처음에는 색종이의 크기가 큰 것부터 덮는 그리디 방식으로 구현하였습니다. 하지만 반례가 존재하였으며 모든 상황을 고려하지 않으면 정답을 도출할 수 없기 때문에 완전 탐색 방식으로 접근하였습니다. [ 알고리즘 ] 1. 0의 위치를 찾습니다. 2. 해당 위치에 덮을 수 있는 색종이의 종류를 찾습니다. 3. 해당 위치에 색종이를 덮은 후 탐색을 계속 진행합니다. 4. 0이 존재하지 않으면 현재까지 사용한 색종이의 수와 현재까지 구한 색종이의 최솟값을 비교합니다. [ 코드 ] import sys sys.setrecursionlimit(10 ** 9) def check(array, row, col, depth): # depth 크기의 색..

문제 보기 Union-Find와 우선순위 큐를 활용하여 구현하였다. Union-Find는 두 정점의 연결 관계를 파악하는 데 사용하였고 우선순위 큐는 간선을 관리하기 위해서 사용하였다. 알고리즘은 아래와 같다. 1. 가중치가 높은 순서대로 간선을 추가한다. 2. 해당 간선의 연결 정점을 A, B라고 하였을 때 만약 A와 B의 부모가 다르다면 A와 연결된 집합의 개수 * B와 연결된 집합의 개수 * (전체 간선의 가중치 합 - 현재까지 추가한 가중치 합)을 누적해서 더한다. 3. 해당 정점과 연결된 집합의 개수를 구하기 위해서 자식의 수를 갖는 리스트를 추가적으로 선언하여 관리하였다. import heapq def find_parent(x): if parent[x] != x: parent[x] = find..

문제 보기 구현, 시뮬레이션 문제이다. A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력하면 된다. 최소 시간? 연산의 순서가 정해져 있기 때문에 최소라는 말은 큰 의미가 없다. A[r][c] 값을 k로 만들 수 있는 특별한 연산 방법이 있는 것이 아니라, 연산의 순서에 따라 진행하면서 A[r][c]의 값이 k인지 주기적으로 확인하면 된다. 배열의 크기 연산을 진행하다 보면 행 또는 열의 크기가 변한다. 하지만 행 또는 열의 크기가 100을 넘어가는 경우는 의미없는 값이기 때문에 처음부터 배열 크기를 100 x 100으로 선언하면 행 또는 열의 크기 변화를 신경 쓸 필요가 없다. 행과 열의 크기 비교 행과 열의 크기 변화는 신경 쓸 필요가 없지만 행의 최대 크기와 열의 최대 크기는 ..

문제 보기 BFS 문제이다. 연구소의 모든 빈칸에 바이러스가 있게 되는 최소 시간을 구하면 된다. 바이러스 후보 위치 파악 모든 빈칸에 바이러스가 있도록 하기 위해서는 바이러스를 놓을 수 있는 위치를 구해야 한다. 따라서 2차원 배열을 탐색하면서 값이 2인 곳의 위치를 따로 저장한다. 조합을 활용하여 모든 경로 탐색 바이러스는 후보 위치 중 최대 m개까지 놓을 수 있다. 파이썬은 itertools의 combination을 통해서 후보 위치 중 m개를 놓는 모든 경우를 쉽게 파악할 수 있다. BFS를 이용한 탐색 최종적으로 선택된 바이러스는 상, 하, 좌, 우를 탐색하면서 퍼져나간다. 모든 경우에 대해서 bfs 탐색을 진행한 후 가장 적은 시간에 모든 빈칸에 바이러스를 퍼트린 시간을 출력하면 된다. 만약 ..

문제 보기 구현, 시뮬레이션 문제이다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료되며, 게임이 종료되는 턴의 번호를 출력하면 된다. A번 말이 이동하려는 칸은 흰색, 빨간색, 파란색, 체스판을 벗어나는 경우 중에 하나이다. 체스판을 벗어나는 경우는 파란색과 동일하기 때문에 총 3가지 경우가 존재한다. 따라서 3가지 연산을 구현하면 된다. 말의 이동을 관리하기 위해서 2차원 배열을 선언하였다. 만약 해당 칸에 말이 없다면 빈 공간 형태이며, 말이 2마리 있다면 첫 번째 말, 두 번째 말 순서로 쌓인 형태이다. 흰색과 빨간색 칸 연산은 매우 유사하며 말을 쌓는 순서만 바꾸면 된다. 전체적인 연산 순서는 아래와 같다. 1. 현재 칸에서 이동하려는 말의 인덱스를 파악한다. (현재 칸에 A, B..

문제 보기 브루트포스, 구현, 시뮬레이션 문제이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구하면 된다. 브루트포스를 구현하기 위해서는 1번 조건에 맞는 x, y, d1, d2 값이 필요하다. 1번 조건: d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N x, y, d1, d2는 1 이상 n이하이기 때문에 밑줄 친 부분의 조건만 추가하면 1번 조건을 만족한다. 추가적으로 2번 경계선 조건에 해당하는 위치에 5를 대입하고, 선거구를 구별하면 된다. 경계선 조건과 선거구 구별 또한 문제에서 주어진 조건을 그대로 코드로 작성하면 된다. 코드 import copy INF = 1e9 def solve(x..

문제 보기 DFS, 구현, 시뮬레이션 문제이다. 원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구하면 된다. 원판 돌리기에서 필요한 연산은 2가지이다. 1. 원판 회전 2. 인접하면서 같은 수를 지우기 원판 회전은 시계 방향, 반시계 방향으로 나눠서 구현하였다. 시계 방향은 array[i] = [array[i][-1]] + array[i][:-1]로 구현하였다. 마지막 값을 제일 앞으로 옮겼다. 반시계 방향은 array[i] = array[i][1:] + [array[i][0]]로 구현하였다. 첫 번째 값을 마지막 위치로 옮겼다. 인접하면서 같은 수 지우는 연산은 dfs로 구현하였다, 현재 위치의 상, 하, 좌, 우에 현재 위치에 있는 값이랑 같은 값이 있으면 계속해서 탐색하도록 하였다. 예를 들어 현..

문제 보기 백트래킹 문제이다. 주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구하면 된다. 주사위 윷놀이 문제는 모든 경로를 해보기 전까지는 어떤 경로가 최댓값을 가지는 지 판단할 수 없다. 따라서 모든 경로를 탐색하면서 조건을 통해 시간을 단축하는 백트랙킹 알고리즘을 구현하고자 하였다. 경로는 크게 4가지로 나눌 수 있다. 1. 바깥쪽으로만 도는 경우 2. [10]을 지나는 경우 3. [20]을 지나는 경우 4. [30]을 지나는 경우 말이 겹치는 경우는 아래와 같다. - 2, 3, 4 경로는 [25] ~ [40] 사이의 경로에서 말이 겹칠 수 있다. - 1 경로는 [10, 20, 30, 40] 위치에서 다른 말과 겹칠 수 있다. 말이 얻을 수 있는 최대 점수는 40점..