기록

문제 보기 [사용한 알고리즘] 정렬, 그리디 [문제 접근] 양수 가장 큰 수 두 개, 음수 절댓값 가장 큰 수 두 개씩 묶는 것이 최종 합을 최대로 나오게 할 수 있다고 생각하였다. 추가적으로 1은 묶지 않는 것이 좋고, 0의 경우 음수 1개가 남은 상황에서는 묶는 것이 좋다고 생각하였다. [알고리즘] 1. 입력받은 숫자를 오름차순 정렬한다. 2. 1보다 큰 수를 따로 저장한다. 3. 0 이하의 수를 따로 저장한다. 4. 2, 3의 과정에서 따로 구한 수를 2개씩 묶고 곱한다. 묶이지 않는 숫자는 그대로 더한다. 5. 2, 3 과정에서 묶이지 않은 숫자를 더해서 최종 합을 출력한다. [코드] from collections import deque if __name__ == "__main__": n = in..

문제 보기 [사용한 알고리즘] 구현 [문제 접근] a값과 b값은 수식을 통해서 구할 수 있습니다. 만약 a, b값이 주어진 N개의 숫자를 모두 만족시키면 다음 수를 출력하고, 만족시키지 못하면 B를 출력합니다. 모든 숫자가 동일한 경우에는 동일한 숫자를 출력하고, N이 2보다 작은데 두 숫자가 다른 경우는 A를 출력하였습니다. [알고리즘] 1. (array[2] - array[1]) // (array[1] - array[0]) 식으로 a 값을 구합니다. array[1] - array[0] * a 식으로 b값을 구합니다 2. a, b값으로 주어진 N개의 숫자를 모두 만족시키는지 확인합니다. 3. 모두 만족시키면 다음 수를 출력하고, 만족시키지 못하면 B를 출력합니다. * N이 1이면 A, N이 2이고 두 ..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색), 구현 [문제 접근] 세 단계 과정을 통해 문제를 구현하고자 하였습니다. 첫째, 주어진 N x M 모눈종이에서 외부 공기 위치를 구합니다. 둘째, 각 치즈 상, 하, 좌, 우에 인접한 외부 공기 위치 개수를 파악합니다. 셋째, 외부 공기가 2개 이상인 치즈를 녹입니다. 위 과정을 모든 치즈가 녹을 때까지 진행합니다. [알고리즘] 1. 외부 공기 위치를 구합니다. (맨 가장자리를 출발점으로 BFS 탐색을 하여 외부 공기를 파악합니다) 2. 각 치즈의 인접한 외부 공기 위치 개수를 구합니다. 3. 외부 공기가 2개 이상인 치즈를 녹입니다. 4. 위 과정을 모든 치즈가 녹을 때까지 반복합니다. [코드] from collections import deque..

문제 보기 [사용한 알고리즘] 브루트 포스, 조합 [문제 접근] 배양액을 놓을 수 있는 공간에 초록색 배양액과 빨간색 배양액을 놓는 모든 경우에 대해서 시뮬레이션하였습니다. 배양액을 놓고 시간에 따라 퍼지는 동작을 실행해야만 꽃의 개수를 파악할 수 있기 때문에 모든 경우의 수를 확인하였습니다. [알고리즘] 1. 배양액을 놓을 수 있는 공간 중 초록색 배양액을 놓을 공간을 구합니다. 2. 배양액을 놓을 수 있는 공간 중 빨간색 배양액을 놓을 공간을 구합니다. 3. 1, 2 과정을 거친 후 시간에 따라 배양액이 퍼지는 과정을 시뮬레이션합니다. 4. 1~3 과정을 모든 경우의 수에 대해 적용해보고 피울 수 있는 꽃의 최대 개수를 출력합니다. [코드] from itertools import combination..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색) [문제 접근] 집합 배정 정보를 관리하는 리스트를 선언한 후, 1번 정점부터 차례대로 연결된 정점들의 정보를 이용해서 집합을 배정합니다. 이후 2번 정점, 3번 정점... 마지막 정점까지 진행하면서 오류가 발생하면 NO를 출력, 끝까지 진행하면 YES를 출력하였습니다. [알고리즘] 1. 1번 정점부터 집합 배정을 시작합니다.2. 해당 정점을 처음 방문하는 경우 1을 대입합니다. 이후 해당 정점과 연결된 정점들은 2를 배정하고, 그 정점들과 연결된 정점들은 1을 배정하는 BFS 탐색을 하였습니다. (만약 해당 정점을 방문한 적이 있다면 해당 정점의 값을 통해 연결된 정점들의 값을 대입하면 됩니다. 예를 들어 해당 정점이 1의 값을 가지면 연결된 정점들..

문제 보기 [사용한 알고리즘] 그리디 [문제 접근] 주어진 단어들의 각 알파벳들의 가치를 계산한 후에 숫자를 대입하고자 하였습니다. [알고리즘] 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으로 선언하면 행 또는 열의 크기 변화를 신경 쓸 필요가 없다. 행과 열의 크기 비교 행과 열의 크기 변화는 신경 쓸 필요가 없지만 행의 최대 크기와 열의 최대 크기는 ..