Jungeun's Devlog

문제난이도: 골드5알고리즘 분류: 깊이 우선탐색요약: 첫째 줄의 집합과 둘째 줄의 집합을 이루는 수가 일치하면서 최대한 많은 수를 뽑을 때, 뽑힌 정수들에 대한 정보 출력하기 풀이입력 정보를 받아 그래프를 만들고 사이클이 발생하는 노드를 알아내어 문제를 해결한다. 이를 위해 dfs를 사용하여 각 노드에서 출발하는 사이클을 탐색한다. 인접 리스트로 정보 저장 첫째 줄과 둘째 줄의 숫자 관계를 그래프로 표현하여 같은 수로 이루어진 집합을 찾아야 한다. 입력을 인접 리스트 형식으로 변환하여 저장한다. 첫째 줄의 숫자를 노드로, 그와 일치하는 둘째 줄의 숫자의 위치를 간선으로 표현하여 각 노드의 이웃 노드들을 저장한다.  예제 입력에 따른 그래프 관계를 나타내면 다음과 같다.12345673115546  gr..

문제난이도: 골드4알고리즘 분류: 다이나믹 프로그래밍요약: 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력하기 풀이가장 긴 바이토닉 수열을 갖기 위해 (증가하는 수열의 길이 + 감소하는 수열의 길이)가 최대가 되는 수열을 찾아야 한다. 이를 위해 dp 배열을 사용하여 dp[i]에 arr[i]를 마지막 원소로 가지는 부분 수열에서의 최대 길이를 저장한다. 예제로 주어진 수열을 살펴보면수열1 5 2 1 4 3 4 5 2 1i번째 원소를 마지막으로 하는 증가하는 부분 수열의 최대 길이1 2 2 1 3 3 4 5 2 1i번째 원소를 마지막으로 하는 감소하는 부분 수열의 최대 길이1 2 3 3 3 4 1 2 5 1두 수열의 합2 7 4 2 7 6 7 8 4 2가장 긴 바이토닉 수열은 8번째 원소..

문제난이도: 골드5알고리즘 분류: 수학, 브루트포스 알고리즘, 정수론, 소수 판정, 에라토스테네스의 체요약: 서로 다른 수가 적힌 카드가 있고 수 나누기 게임을 모두 진행했을 때, 각 플레이어의 점수를 출력하기 풀이모든 수에 대해 두개씩 비교를 진행하면 시간복잡도가 O(N^2)이다. 입력 크기가 최대 100,000개이기 때문에 시간 초과가 발생한다. 모든 숫자 쌍을 직접 비교하는 대신, 효율적으로 문제를 해결하기 위해 에라토스테네스의 체 알고리즘의 개념을 응용하여 해결할 수 있다. 나머지가 0이라는 뜻은 한쪽이 다른 쪽의 배수라는 뜻이다. 각 플레이어가 가진 수의 배수 관계만 비교해가며 빠르게 확인한다. 비교 대상이 줄어 모든 수를 확인하지 않아도 되고, 에라토스테네스의 체와 유사한 시간복잡도를 보인다...

문제난이도: 골드5알고리즘 분류: 다이나믹 프로그래밍, 배낭 문제요약: 배낭에 넣을 수 있는 무게의 최댓값이 주어지고 일정 무게와 가치가 있는 짐이 있을 때, 가치의 합이 최대가 되도록 하는 값을 출력하기 풀이Knapsack 문제배낭에 넣을 수 있는 무게의 최댓값이 주어지고 일정 무게와 가치가 있는 짐이 있다. 이때, 최대 용량을 초과하지 않으면서 배낭에 넣을 수 있는 최대 가치의 합을 찾는 문제이다.배낭에 짐을 넣을 때, 짐을 쪼갤 수 있는 경우와 쪼갤 수 없는 경우가 존재한다.쪼갤 수 있는 경우 -> 분할가능 배낭문제 (Franction Knapsack Problem)쪼갤 수 없는 경우 -> 0-1 배낭문제 (0-1 Knapsack Problem)이 문제는 0-1 배낭문제로, 각 물건에 대해 넣기/안..

문제난이도: 골드4알고리즘 분류: 구현, 브루트포스, 백트래킹요약: 주어진 배열에 여러 회전 연산을 각각 한 번씩 적용하며, 이 연산들의 순서를 자유롭게 변경하여 회전한 후 얻을 수 있는 모든 배열 중 최솟값을 찾아 출력하기 풀이순열backtracking을 이용해서 순열을 구현할 수 있지만, itertools 모듈의 permutations 함수를 통해 더 빠르게 구할 수 있다.permutations(객체 n, 뽑을 개수 r)객체: [[a,b,c], [d,e,f]]반환값: ([a,b,c], [d,e,f]), ([d,e,f], [a,b,c]) 경우의 수에 대한 쌍을 튜플 형식으로 리턴하나의 회전 순열이 다른 순열에 영향이 가지 않도록 deepcopy를 통해 복사를 진행해야한다. 회전회전 연산에 대해 r,..

문제난이도: 골드4알고리즘 분류: 자료구조, 정렬, 이분 탐색, 두 포인터요약: n개의 수가 주어졌을 때, 이 중 어떤 수가 다른 두 수의 합으로 표현될 수 있는 수의 개수 출력하기 풀이예외 처리타겟과 다른 두 수의 합으로 표현 -> 타겟을 제외한 temp 리스트 생성 시간 복잡도1) Two Pointers 탐색배열 정렬 -> O(N logN)하나의 타겟마다 두 인덱스 변수를 사용해서 O(N) 시간이 소요되기 때문에 모든 원소에 대한 탐색을 진행하면 O(N^2)전체 시간복잡도: O(N^2)2) Brute Force 탐색배열 정렬 -> O(N logN)하나의 타겟에 대해 조합 가능한 숫자 쌍을 확인하려면 이중 for문 사용 O(N^2), 모든 원소에 대한 탐색을 진행하면 O(N^3)전체 시간복잡도: O(N..

문제난이도: 골드5알고리즘 분류: 문자열, 두 포인터요약: 주어진 문자열이 회문인지 유사 회문인지 일반 문자열인지 출력하기 풀이회문 판단left, right 변수를 사용해서 투 포인터로 풀이 유사회문 판단중간에 일치하지 않는 문자가 나왔을 경우1) 해당 위치에서 왼쪽 값 제거 후, 나머지 문자가 회문인지2) 해당 위치에서 오른쪽 값 제거 후, 나머지 문자가 회문인지 확인1), 2)에서 회문이 아니면 (다른 문자 개수 >= 2) 일반 문자열로 처리 코드import sysinput = sys.stdin.readlineT = int(input())def is_palindrome(word): left = 0 right = len(word) - 1 while left

문제난이도: 골드3알고리즘 분류: 구현, 시뮬레이션요약: 주어진 정보를 통해 n개의 드래곤 커브를 구현했을 때, 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력하기 풀이커브 구하기각 세대마다 생성되는 커브의 개수와 방향에 관한 규칙을 살펴보았다.동(0) 북(1) 서(2) 남(3)세대선분의 개수방향01 (2^0)012 (2^1)0 124 (2^2)0 1 2 138 (2^3)0 1 2 1 2 3 2 1 세대가 증가할수록 선분의 개수는 2배씩 증가하고,방향은 이전 세대의 리스트의 마지막 원소부터 90도 회전한 방향으로 추가되는 것을 볼 수 있다.  방문 여부 표시드래곤 커브 좌표를 표시하기 위해 visited 2차원 배열을 생성하고, 방문한 좌표에 대한 값을 업데이트한다. curve 리스트..

문제난이도: 골드4알고리즘 분류: 구현, 그래프, 시뮬레이션, 너비 우선 탐색요약: 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수 출력하기 풀이공기와 접촉된 칸에 대한 처리queue에 공기의 좌표를 담고 하나씩 값을 꺼내 공기와 접촉된 칸에 대해 녹이는 작업을 진행한다.이때, 판의 가장자리에는 치즈가 놓여있지 않다는 전제에 따라 (0, 0)부터 탐색한다.(0, 0)을 시작으로하면 치즈의 구멍에 대한 접근이 불가능한 것을 처리할 수 있다. 해당 좌표 값에 방문하지 않았을 경우에 대하여공기일 경우: queue에 추가치즈일 경우: 공기와 접촉되어 있으므로 해당 칸을 공기로 바꾸고 녹인 개수를 업데이트한다.(board[ny][nx] =..

문제난이도: 골드1알고리즘 분류: 구현, 그래프, 시뮬레이션, 너비 우선 탐색요약: 파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 1을 없으면 0을 출력하기 풀이빨간/파란 구슬의 x, y 좌표를 queue에 담아서 진행 1. 한 방향으로 이동중인 구슬이 멈추는 조건다음 위치가 벽이거나현재 위치가 구멍일 때2. 빨간/파란 구슬이 끝까지 이동했을 때의 위치와 움직인 횟수 확인이동한 빨간/파란 구슬 위치가 같을 경우움직인 횟수 비교 후, 이동거리가 더 많은 구슬이 뒤로 한칸 이동  코드from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())board = ..