알고리즘연습

image만들 수 있는 최대 랜선의 길이를 찾아야 하는데 랜선의 길이가 최대 2^31-1이기 때문에 브루트포스를 활용할 수는 없고 이분탐색을 활용하였다start = 1, end = 입력받은 랜선 중 가장 긴 랜선 길이 로 설정해 놓고 중간값(mid)으로 랜선을 나누어서

image주어진 정수의 개수와 찾아야 할 정수의 개수가 모두 최대 100,000개이므로 순차탐색하면 시간초과가 날 것이다.이분탐색을 활용하면 시간 안에 해결할 수 있을 것 같아서, 먼저 이분탐색을 위해 주어진 순열 A를 오름차순 정렬하고 시작하였다.순열의 처음과 끝을

image브루트 포스 방식으로 해결하는 문제이다.0부터 최대 높이 256까지 반복하면서, 높이가 target일 때 쌓아야 할 블록 개수와 제거해야 할 블록 개수를 계산한다.(제거하는 블록 개수 + 인벤토리 블록 개수) >= 쌓아야 할 블록 개수 인 경우 작업시간(tim

imageBFS를 활용하는 문제땅의 각 좌표를 방문하다가 1인 땅을 발견할 때마다 해당 땅을 기준으로 BFS를 수행한다. BFS를 수행하면서 방문하는 1은 방문한 다음 0으로 바꾼다.BFS가 한 번 수행될 때마다 인접한 1들의 구역을 하나 찾은 것이므로 cnt를 1씩

image현재 채널이 100번이므로 ans를 abs(100 - 찾는채널)로 초기화한다고장난 숫자 버튼을 포함하지 않는 모든 채널에 대하여 찾는 채널로 이동하기 위해 버튼을 눌러야 할 횟수를 계산하고 ans의 최소값을 업데이트한다최대 채널번호가 500000이고 채널은 찾

image인접한 좌표를 체크하면서 최단거리를 찾는 문제이므로 BFS를 활용하였다처음부터 익어 있는 모든 토마토들로부터 인접한 덜 익은 토마토를 익게 하므로 큐에 익어 있는 모든 토마토들의 좌표를 추가한다큐에서 좌표를 하나씩 꺼내면서 BFS를 수행하며 인접한 덜 익은 토

image이차원 배열이 주어졌던 이전 토마토 문제에서, 3차원 배열이 주어지며 인접 토마토의 방향이 왼쪽, 오른쪽, y축으로 위,아래, z축으로 위,아래 6방향으로 늘어난 문제이다기존의 로직에서 2차원 배열을 3차원 배열로, z축 방향을 계산하는 코드를 추가하면 되었다

image인접한 4개 좌표의 색을 확인하며 같은 색의 구역을 체크하는 문제이므로 BFS를 활용하였다큐에 저장된 좌표를 꺼내어 방문할 때마다 현재 구역의 번호 cnt를 좌표에 표시하여 방문처리를 했다적록색약인 사람이 보는 좌표의 경우 처음부터 적색과 녹색을 'A'라는 같

image처음에 떠올린 방법 두 가지는 브루트 포스와 DFS이다.브루트 포스로 해결하려면 회전을 고려한 모든 테트로미노를 좌표로 표현하여 graph 밖으로 나가지 않는 선에서 숫자들의 합을 비교하면 되지만 코드 길이가 길어지고 훌륭한 해결방법은 아니다.두 번째 방법은

image다음 회의가 시작되려면 현재 회의의 시작시간이 이전 회의의 종료시간 이후(같아도 ok)이어야 하고, 순차적으로 탐색하려면 회의 배정표가 회의 종료시간을 기준으로 오름차순, 종료시간이 같으면 시작시간을 기준으로 오름차순 정렬되어 있어야 한다.순차탐색하다가 다음

image그래프는 여러 개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수 있는데 이때 서로 연결되어 있는 여러 개의 고립된 부분 그래프 각각을 연결 성분이라고 부른다.연결 요소이려면 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 하며, 다

image좌표를 먼저 오름차순 정렬한 다음, 순차적으로 0부터 순번을 매긴다좌표가 정렬되어 있으므로 순번을 매길 때에는, 오른쪽 숫자가 왼쪽 숫자와 같으면 순번이 같고, 같지 않으면 순번이 1만큼 크다정답을 출력할 때에는 원래 좌표의 순서에 맞게 순번을 출력해야 하므로

image간단한 DP 문제이다이차원 배열 dN, dN에 fibonacci(N)의 0, 1 출력횟수를 저장한다.피보나치 함수의 재귀구조에 의해 dN의 0, 1 출력횟수는 dN-1과 dN-2의 0, 1 출력횟수를 각각 더한 값과 같다.

image규칙성을 찾고 분할정복을 활용하는 문제였다.2^N \* 2^N 좌표를 4개 구역으로 반복적으로 나누면서 답에 도달한다.현재 구역에서 좌표 (r,c)가 몇 사분면에 있는지 확인한 다음, 각 사분면에 따라 (r,c), ans 값을 수정한다.1사분면에 있는 경우 해

image입력받는 단어의 개수가 최대 100만개이므로 단어 하나하나에 대해 전체 단어 중에서 중복여부를 일일이 찾을 수는 없다먼저 N, M 단어를 모두 하나의 리스트에 저장한 다음 sorted() 함수를 사용하여 O(NlogN) 정도의 시간복잡도로 정렬하면 같은 단어

image주어진 이름에 대한 번호를 출력하기엔 해시테이블 구조인 딕셔너리를, 번호에 대한 이름을 출력하려면 인덱스를 사용하는 리스트를 활용하면 된다고 판단하였다.주어진 입력이 숫자인지 확인하는 메소드: str.isnumberic(), str.isdigit()...

image좌표를 4개 정사각형으로 분할해 가면서 색종이가 될 수 있는 구역과 그 색깔을 찾는 분할정복, 재귀 문제이다solution 함수에서는 탐색시작 좌표의 색깔을 저장해 두고 해당 좌표로부터 매개변수로 주어진 N x N 만큼의 구역이 모두 같은 색깔인지 확인한다.모

image최소 힙에 대한 개념과 구현방법을 연습하는 문제였다.참고자료: 링크

image대기시간이 짧은 사람이 먼저 ATM을 사용해야 전체 사람들의 대기시간 합이 최소가 된다따라서 입력받은 대기시간을 오름차순 정렬한 다음 대기시간 합을 구하면 된다

image배열이나 리스트로 접근하면 시간초과가 발생하는 문제이다비트마스킹을 사용하는 문제라고 한다. 파이썬에서는 숫자 앞에 0b를 붙여서 이진수를 표현한다.이진수의 자릿수에 0 또는 1로 특정 원소의 유무를 표현하는 문제이다원소 n의 유무를 n번째 자릿수에 표시하기 위

image파이썬의 heapq 모듈을 사용하면 최소 힙(MIN-HEAP)의 기능을 사용할 수 있다.최소값을 구하여 제거할 땐 최소힙을, 최대값을 구하여 제거할 땐 최대힙을 사용하기 위해 2개의 힙을 사용하였다.다만 파이썬은 최소 힙만 제공하므로 최대 힙을 구현하려면 삽입

image나머지 분배법칙과 분할정복을 활용하는 문제이다나머지 분배법칙: (a x b) % c = (a % c) x (b % c) % cb가 짝수일 때 (A^b) % c = (A^(b//2) % c) \* (A^(b//2) % c) % cb가 홀수일 때 (A^b) % c

image다이나믹 프로그래밍을 활용하여 해결하였다.삼각형의 각 수에 대해, 자신의 윗줄 왼쪽과 오른쪽 수들 중 큰 수를 자신과 더하면, 각 수에 도달할때까지의 최대값만을 저장할 수 있게 된다.마지막 행까지 위 계산을 수행한 다음, 마지막 행의 최대값을 출력하면 정답이다

image대표적인 트리 순회 알고리즘인 전위(preorder) 순회, 중위(inorder) 순회, 후위(postorder) 순회를 구현하는 문제이다. 재귀를 사용한다트리의 각 노드와 자식노드를 표현하기 위해 노드를 key로, (leftchild, rightchild)

image다이나믹 프로그래밍을 활용하였다.현재 스티커를 뗀다고 가정하면 이전에 바로 왼쪽 스티커는 뗄 수 없었을 것이다.따라서 왼쪽 대각선 방향의 스티커를 떼거나, 떼지 않을 수도 있으므로, 이전 스티커들의 합은 왼쪽 대각선 방향 스티커와 그 이전 열(i-2열)의 두

image표에서 직사각형 구간의 합을 구하는 문제이다.기존 표의 (x,y)좌표 각각에 대해 (0,0)~(x,y) 구간의 합을 구해놓으면 직사각형 (x1,y1)~(x2,y2) 구간합을 O(1)의 연산으로 구할 수 있다.컴퓨터그래픽스 교과목 시간에 구간합을 빠르게 구하는

image리스트나 딕셔너리를 사용하여 인접노드리스트 방식으로 트리를 표현한 다음, BFS나 DFS 방식으로 트리의 정점부터 인접 노드들을 탐색하면서 부모 노드를 갱신해나갔다.

image백트래킹 문제이다. 백트래킹이란 문제를 해결해가다가 주어진 조건을 만족하지 않는다고 판단되는 경우 더 진행하지 않고 이전 단계로 다시 돌아가서 다른 방향으로 탐색하는 문제 해결 방법이다.보통 DFS(깊이우선탐색)으로 구현하며 종료 조건을 갖는 재귀 구조를 갖는

image백트래킹 문제이다. 문제 조건에서 비내림차순(같은 숫자를 여러번 사용하는 것을 허용하는 오름차순) 수열을 요구했기 때문에 현재 추가한 숫자(i) 다음으로 탐색할 숫자의 범위를 range(i, n+1)로 하기 위해 for 문 내에서 dfs(i)를 호출한다.

image백트래킹 문제이다. 수열을 사전순으로 출력해야 하므로 먼저 주어진 N개의 수를 오름차순 정렬한 다음 기존의 N과 M 문제와 유사한 방식으로 해결하였다.같은 수를 중복할 수는 없으므로 for문 안에 if i not in ans 조건을 만족하는 숫자만 수열에 추가

image백트래킹 문제이다. 중복되는 수열을 거르기 위해 이전의 N과 M 문제에서 한 가지 조건을 더 추가해야 한다현재 깊이에서 이전에 사용했던 숫자를 나타내는 prev 변수를 도입하여, 현재 수열에 추가할 숫자가 이전에 사용한 숫자(같은 깊이에서)가 아닌 경우인지를

imageB가 짝수이면 2를 나누고, 끝자리가 1이면 끝자리 1을 제거하는 과정을 반복하다가 이 외의 경우에는 A로부터 만들어질 수 없으므로 -1을 출력하고 도중에 A가 만들어지면 반복횟수를 출력한다.

image다익스트라 알고리즘을 사용하는 문제이다다익스트라 알고리즘은 노드 간 음의 비용이 존재하지 않을 때 시작 노드(start)로부터 각 노드까지의 최소 비용을 구하는 데 유용하다노드를 방문할 때마다 최소비용을 갖는 인접 노드를 선택해야 하는데 이때 최소힙을 사용하면

image배낭 문제(knapsack problem)의 대표적인 예시이다.배낭문제는 물건을 나눌 수 있는 배낭 문제(fractional knapsack problem)와 물건을 나눌 수 없는 0-1 배낭 문제로 나뉜다.전자는 각 물건의 단위무게당 가치를 가지고 가치가 높

image다이나믹 프로그래밍을 활용하는 문제이다두 문자열 길이를 각각 n, m 이라고 가정했을 때, (n+1) x (m+1) 크기의 이차원 배열을 활용하여 dp\[i]\[j] = 문자열1의 i번째문자, 문자열2의 j번째문자 까지의 최대 부분문자열 길이로 나타낸다.dp\

BFS를 활용하는 문제이다. 단 가중치가 0-1인 0-1 BFS이다.한 칸씩 움직일 때 1초가 소요되는것과 달리 순간이동할 때는 시간이 소요되지 않으므로, 순간이동의 경우 큐의 맨 앞에 추가해야 한다. 최소시간을 구해야 하므로 소요시간이 작은 것을 먼저 방문해야 하기

imageBFS를 활용하는 문제이다.벽을 한 번만 부술 수 있기 때문에, 이전에 벽을 부쉈는지 여부를 큐에 포함하여 BFS를 수행하도록 코드를 작성했지만 틀렸다.틀린 이유는, 벽을 부순 여부를 체크해야 하는 것뿐만 아니라, 벽을 부수지 않고 온 경우와 벽을 부수고 온

image특정 노드 간 최단거리를 구해야 하므로 다익스트라 알고리즘을 사용하였다최소힙을 사용한 다익스트라 알고리즘의 시간복잡도가 NlogN 이므로 문제에서 N이 최대 100이기 때문에 100 x 100log(100) = 20000 회 정도의 연산으로 충분히 해결할 수

image주어진 식에서 괄호를 사용하여 최소값이 되게 하려면, 음수 뒤에 나오는 양수끼리의 덧셈을 괄호로 묶어야 한다.즉, '-'가 나오면 괄호를 열고, 다시 '-'가 나오면 그 앞에 괄호를 닫는다.예를 들어, 3+2-10-2-3+4의 경우 3+2-(10)-(2)-(3

image분할정복과 재귀를 활용하는 문제로, 이전에 풀었던 색종이 만들기(https://www.acmicpc.net/problem/2630) 문제와 같은 유형의 문제이다.색종이 만들기 풀이

image분할정복과 재귀를 활용하는 문제이다.solution(x, y, n) 함수를 정의하여, 현재 좌표 (x,y)를 최우측 상단으로 하는 n x n 크기의 정사각형이 모두 같은 색으로 이루어져 있는지 확인하고, 만약 하나라도 다른 색이 있으면 괄호를 연 다음 n x

image흔한 그래프 탐색 문제이다. BFS를 활용하였다.방문하지 않은 집(1)을 시작점으로 하여 BFS를 수행하며 단지 내 집의 수를 카운트한다. 한 번 방문한 집은 visited = True로 표시하여 다시 방문하지 않는다.

image문자열, 슬라이싱 관련 문제이다서브태스크 1은 문자열에서 현재 문자를 기준으로 뒤의 2n+1글자가 Pn과 같은지 확인하는 것(시간복잡도 O(n^2))만으로도 해결할 수 있다.하지만 서브태스크 2는 문자열이 길기 때문에 O(n) 또는 O(nlogn)정도의 시간복

image규칙성을 찾는 문제이다1,1,1,2,2 정삼각형까지는 별다른 규칙이 없지만 그 이후부터는 Pn = Pn-1 + Pn-5 의 규칙을 갖는다.

image누적합을 이용하여 구간합을 구하는 간단한 문제구간 (a, b)의 구간합 = (b까지의 누적합) - (a 바로 전까지의 누적합)

image너비우선탐색(BFS)를 활용하는 문제이다현재 좌표에서 주사위를 던졌을 때 도착할 좌표와 현재까지 주사위를 던진 횟수를 큐에 넣고 방문처리한다.단, 도착할 좌표가 방문하지 않은 좌표인 경우에만 큐에 넣는다.또한, 주사위를 던진 결과 뱀과 사다리가 있는 좌표인 경

image배열이 양방향이 뚫려있는 deque이라고 생각하고 'R'이 나올때마다 'D' 작업을 할 방향(좌, 우)을 바꾼다.'D'일 때 현재 방향이 1이면 pop(0)을, -1이면 pop(-1)을 하고, 'R'일때는 방향 x= -1 계산을 하여 방향을 바꾼다.결과를 출력

image두 사람의 좌표에서 반지름이 각각 r1, r2인 원을 그렸을 때 교차점의 개수를 찾는 문제이다두 사람의 좌표가 같고 r1 == r2 인 경우: 무한대max(r1, r2) > 두 사람 간 거리 + min(r1, r2) 인 경우: 0개max(r1, r2) == 두

image간단한 통계문제이다. 신경써야 하는 부분은 최빈값을 구하는 부분이다. 이중 반복문을 사용하지만 않으면 될 것이다.수의 절댓값이 최대 4000이므로 8001개의 인덱스를 갖는 배열을 사용하여 배열\[수] = 빈도 형태로 빈도를 저장하였다.

imageDP 문제이다N번째 01타일 수열은 '1'에 N-1번째 01타일 수열을 붙이고, '00'에 N-2번째 01타일 수열을 붙여서 만들어진다.따라서 점화식은 D\[N] = D\[N-1] + D\[N-2]이다.

image수의 개수가 최대 11개이므로 4가지 연산자의 개수도 최대 10개이다. 그래서 연산자 순열을 구하여 일일이 브루트포스 방식으로 계산해도 괜찮을 것이라 생각하였다.따라서 10개의 연산자들 순열을 itertools.permutations 라이브러리를 사용하여 구한

image조합을 사용하여 팀을 나누고 각 팀의 능력치 합 차이를 비교하였다.조합을 쉽게 구해주는 파이썬의 itertools.combinations 라이브러리와 A팀을 제외한 다른 팀(B팀)을 구하기 위해 not in 문을 활용한 코드이다.

imageDP 활용 문제이다.퇴사일로부터 역순으로 오늘까지의 최대 수입을 계산하는 점화식을 구하였다.오늘이 근무 가능한 날인 경우, 퇴사일로부터 내일까지의 수입과 근무 시 오늘까지의 수입을 비교한다.오늘 근무하는 경우의 수입은 오늘 근무할 경우 다음에 근무 가능한 날을

image전형적인 단방향 그래프 bfs 문제였다.신뢰관계를 이차원 리스트로 저장하고 각 컴퓨터를 시작노드로 하여 bfs를 수행하면 된다.

imagebfs 탐색으로 인접한 안전 좌표 중 방문하지 않은 좌표만 큐에 넣고 방문하도록 하였다.

image하노이 탑 알고리즘을 재귀로 구현하는 문제이다.1번부터 n-1번 원반을 다른 비어있는 축으로 옮기는 하위 문제를 재귀적으로 푼다.n번 원반을 최종적으로 옮겨야 할 축으로 옮긴다.1번부터 n-1번 원반을 다른 비어있는 축에서 최종적으로 옮겨야 할 축으로 옮기는

코드 결과 image 풀이 방법 우선 서류평가 순위를 기준으로 입력받은 순위를 오름차순 정렬한 다음, 1위의 면접평가 점수를 합격자 면접평가 순위 리스트에 추가한다. 그다음, 2위부터 순차적으로, 가장 최근에 추가된 합격자의 면접평가 순위보다 현재 지원자의 면접평

코드 결과 image 풀이 방법 전형적인 bfs 문제이다. 이미 비슷한 문제를 많이 풀어보았기 때문에 bfs 알고리즘 구현만 할 수 있다면 쉽게 풀 수 있었다.

imageDFS를 활용해야 하는 문제이다.재귀를 사용하여 DFS를 구현하였으며, 인접한 좌표 중 현재까지 나오지 않은 알파벳인 경우에만 방문한다.현재까지 나온 알파벳을 list에 추가하여 관리하고 if not in 문으로 체크하면 시간초과가 발생하였다.따라서 알파벳의

image이 문제의 경우 문제를 9개의 subproblem으로 나누는 것보다는, 전체 문제를 3개 줄의 subproblem으로 나누어서 해결하는 것이 빠르고 구현이 쉽다.탈출 조건은 n == 1 일 때이고 별 1개를 리스트에 담아 리턴한다.recursion(n)은 크기

image현재 도시에서 시작하여 리터당 가격이 현대 도시보다 작은 도시가 나올 때까지는 현대 도시의 리터당 가격을 기준으로 주유하고,리터당 가격이 현재 도시보다 작은 도시서부터는 최소 리터당 가격(minPrice)을 갱신하여 위와 같이 주유한다.자세한 내용은 코드의 주

image다이나믹 프로그래밍 문제라고 생각했으나 점화식을 세우기가 어려웠다.동전 종류를 순회하면서, 해당 동전 금액(c)을 더하여 총합 i의 금액을 채울 수 있다면 dpi에 dpi-c를 합산하는 것이 핵심이다.

image총 예산의 범위가 크고 최적의 상한액을 구해야 하므로 이분탐색으로 해결하였다.while문 조건을 start <= end 로 지정했으므로 탈출 시점에 start는 end보다 1 크다. 따라서 탈출후에 정답으로 end를 출력하거나 (start-1)을 출력하면

image현재 도시로부터 방문 가능한 도시들을 DFS로 방문하며 비용을 계산하고 최소비용을 찾는 문제이다.모든 도시를 방문한 경우(cnt == N) 시작 도시로 돌아갈 수 있는지 확인하고 가능하다면 시작도시로 돌아가는 비용을 추가한 후 최소비용이라면 갱신한다.도시를 시

imageN과 M 유형의 문제와 유사한 문제이다. 백트래킹을 활용하는 문제이고 백트래킹은 DFS로 구현하였다.정답에 문자를 추가할 때 자음/모음 개수를 증가시키고, DFS 수행 후 다시 문자를 제거할 때는 자음/모음 개수를 원래대로 돌려놓는다.charset에서 현재 방

image3주간 군사교육을 받고 와서 그래프 알고리즘을 상기시킬 겸 기본문제를 풀이하였다. bfs로 해결하였다.

image다익스트라 또는 bfs로 해결할 수 있는 문제이다. 다익스트라 알고리즘 복습 겸 해당 알고리즘으로 풀이하였다.

image다익스트라 또는 bfs로 해결할 수 있는 문제이다. 다익스트라 알고리즘 복습 겸 해당 알고리즘으로 풀이하였다.

image주어진 두 좌표를 통해 만들어지는 직사각형 영역을 1로 채워서 표시하고, 나머지 영역의 개수와 넓이는 bfs 알고리즘으로 풀이하였다.

image각 인덱스에 대해 '현재 인덱스까지의 가장 긴 감소하는 부분수열 길이'를 배열 d에 저장한다.현재 인덱스 이전의 수열에서 현재 인덱스의 수보다 큰 수를 찾고, 해당 수의 인덱스까지의 d값들 중 가장 큰 값 + 1 을 현재 인덱스의 d값으로 저장한다.배열 d의

image100000개 중에서 두 수를 임의로 골라서 풀 수는 없는 문제이다.두 수의 합이 0에 가장 가까우려면 입력받은 수들이 각각의 절댓값 기준으로 정렬되어 있는 상태에서 탐색하는 것이 편할 것 같았다.모든 수들이 절댓값 기준으로 정렬되어 있다면, 모두 양수이거나

다이나믹 프로그래밍 문제이다.top down 방식으로 가능한 볼륨을 모두 추리는 방식으로 코드를 작성했으나 그러면 리스트에 최대 2^50개의 볼륨이 들어갈 수 있어서 메모리 초과가 났다DP를 활용해야 하는데, dp 배열을 어떻게 정의하느냐가 핵심이다. 볼륨 범위가 정해

image다이나믹 프로그래밍을 활용하는 문제이다LCS 문제에서는 길이만 출력했다면 이 문제는 가장 긴 부분문자열도 출력하는 문제이다.LCS 알고리즘에서 dp 배열에 길이를 저장했던 것과 달리, 알고리즘은 동일한데 길이 대신 현재까지 가장 긴 부분문자열을 저장하면 된다.

image다이나믹 프로그래밍 문제이다.dp\[i]에 i를 최소횟수로 연산하여 1로 만드는 방법(수열)을 저장하도록 하였다.먼저 1을 빼는 연산을 하기 위해 di-1에 i를 추가한 수열을 di에 저장한다.i가 3으로 나누어 떨어지면, di//3에 i를 추가한 수열의 길이

image최소 스패닝 트리(MST)의 가중치를 구하는 2가지 알고리즘 중 하나인 크루스칼 알고리즘을 구현하였다. 다른 하나는 프림 알고리즘이 있다.최소 스패닝 트리는 트리의 모든 정점을 연결하는 부분 트리(스패닝 트리) 중 간선들의 가중치 합이 최소인 것을 말한다.크루

image백트래킹을 활용하는 문제이다. 시간초과에 상당히 까다롭다.빈 좌표에 들어갈 수 있는 숫자들은 해당 좌표의 같은 행/열, 그리고 좌표가 소속된 3x3 블록에서 사용하지 않은 숫자여야 한다.DFS로 빈 좌표에 숫자를 넣어보다가 이후의 빈 좌표에 넣을 숫자가 없어

image다이나믹프로그래밍을 활용하여 해결하였다.DPS = S번째에서 E번째까지가 펠린드롬이면 1, 아니면 0으로 표기한다S번째에서 E번째까지가 펠린드롬이려면 먼저 DPS+1 == 1이어야 하고, S번째 수와 E번째 수가 같아야 한다.만약 |S-E| == 1 이면 두

image1번 집의 색과 N번 집의 색이 달라야 하므로 먼저 1번 집 색깔을 정해놓고 색을 칠해 나갔다2~N번 집의 색은 현재 집을 0~2번 색으로 칠할 때 각각 이전 집에서 선택할 수 있는 색 중 최소값을 취하며 dp배열을 채운다마지막으로, n번 집까지의 최소비용을

imageUnion-Find 알고리즘으로 사이클 여부를 판단하는 문제이다.두 점을 연결하기 전에 각각의 parent를 확인하여 사이클인지 우선 확인하고, 사이클이 아니라면 union 연산으로 두 점을 연결한다.union 연산 시 부모가 작은 쪽이 큰 쪽의 부모가 된다.

image위상정렬 알고리즘을 공부하였다.위상정렬이란 사이클이 발생하지 않는 방향그래프에서 노드들을 간선 방향을 거스르지 않게 나열하는 것을 의미한다.위상정렬 알고리즘은 주로 큐를 사용하여 구현하며, 진입차수(현재 노드로 들어오는 간선 개수)라는 개념이 사용되고 과정은

image배낭문제 알고리즘 문제이다.DPi = i개의 앱에서 비용 j로 얻을 수 있는 최대 메모리 로 설정하고 푸는 문제이다.

image위상정렬을 활용하는 문제이다.큐가 비었을 때 진입차수가 0이 아닌 노드가 존재하면 사이클이 발생했다는 의미이므로 0을 출력한다.

image위상정렬 + 우선순위큐임의의 문제에 대해 먼저 풀어야 좋은 문제(a; 선수문제)의 개수를 진입차수로 보고 위상정렬을 수행하여 해결하는 문제이다.선수문제가 없는 문제를 큐에 넣고 방문하되, 숫자가 작은 문제부터 푼다는 조건을 만족시켜야 하기 때문에 항상 큐에서

image분류: 문자열추월이라고 판단하는 기준: 들어올 때 X 앞에 있던 차들 중 하나의 차라도 나올 때 X 뒤에 있으면 X가 해당 차를 추월한 것이다들어올 때 X 앞에 있던 차들을 frontCars, 나올 때 X 뒤에 있던 차들을 backCars 리스트에 저장하였다.

image너비우선탐색(bfs)을 활용하여 몇 번째 누른 버튼인지 큐에 넣어 카운트하면서 탐색하다가 G에 도달하면 종료한다.한 번 방문한 층은 다시 방문하지 않아도 되므로 visited 배열에 방문여부를 기록한다.

image분류: DP, 정렬전봇대 A를 기준으로 입력받은 순서쌍 (A, B)를 오름차순 정렬한 다음, 전봇대 B를 기준으로 가장 긴 증가하는 부분수열을 구하고 전깃줄의 총 개수에서 빼면 된다.

image분류: DP, 정렬전봇대 A를 기준으로 입력받은 순서쌍 (A, B)를 오름차순 정렬한 다음, 전봇대 B를 기준으로 가장 긴 증가하는 부분수열을 구하고 전깃줄의 총 개수에서 빼면 된다.

image이분탐색을 활용하였다.start 값은 가장 시간이 긴 강의시간으로, end 값은 총 강의시간으로 초기화하였다.mid 분량의 블루레이가 몇 개 나오는지 카운트하여 bnum에 기록하고, 개수가 M개를 넘으면 더 카운트할 필요가 없기 때문에 break로 탈출하게 하

imageDP를 활용하여 해결하였다. 왼쪽, 중간, 오른쪽 위치마다 이전 줄에서 택할 수 있는 값들 중 최대/최소값을 더해가며 마지막 줄까지 계산한다.다만 이 문제는 메모리 제한이 4MB이기 때문에 처음부터 전체 리스트를 저장하여 사용하면 메모리 초과가 발생하므로 한

imagen의 크기가 최대 50이기 때문에 특별한 알고리즘을 사용하지 않고 완전탐색으로 구현만 잘 하면 해결되었다.모든 n x n개 문자에 대해 가로, 세로로 인접한 문자와 서로 교환 후 문제에서 원하는 가장 긴 부분행/열 길이를 계산해보고 최대값을 갱신하는 방식으로

image현재 다리에 올라와 있는 트럭 무게의 합이 L을 넘지 않게 하면서 트럭을 다리에 추가하고 이동시켰다이동시키는 것은 트럭을 다리에 추가할 때 남은 길이(w)를 추가정보로 저장하여 이동할 때마다 남은 길이를 1씩 줄여서 구현했다현재 다리에 있는 트럭의 총 무게에서

image문자열 관련 문제이다어렵게 생각할 필요 없이 다음의 3가지 경우로 답이 결정된다펠린드롬이면서 모든 문자가 같은 경우 답은 -1이다모든 문자가 같지는 않지만 펠린드롬인 경우 처음 또는 끝의 마지막 문자만 제거해도 가장 긴 답이 되므로 답은 (문자열 길이)-1 이

imageBFS로 간단하게 해결할 수 있는 문제였다.

imageDP를 활용하여 해결하였다.x명의 병사를 열외시켜 가장 긴 감소하는 부분수열이 되도록 만들면 된다.주어진 수열에서 가장 긴 감소하는 부분수열의 길이를 구하고, 전체 병사 수에서 빼면 정답이다.

imageBFS의 개념으로 간단하게 풀이할 수 있는 문제였다.

image주식 가격 추이를 미리 알고 있으므로, 가격이 낮을 때 사고 가장 고점에서 지금까지 샀던 것을 모두 팔아야 한다.예를 들어 1 1 3 1 2 이면 1 1 일때 사서 3에 팔고, 그다음 1일때 사서 2에 팔면 최대 수익이다.따라서 오늘(i일) 이후의 주식 가격의

image각 자리 수가 모두 다르기 때문에 최대 10자리의 수이지만 조건에 맞는지 테스트해야 하는 수는 총 10! = 3628800 개이다. 최대 10자리 수 사이의 각 부등호가 올바른지 판단하기 위해서 최대 9번의 계산이 필요할 것이다.따라서 최대 연산횟수는 10!

image길이 L의 테이프는 L개의 연속된(간격이 1인) 구멍을 막을 수 있다.먼저 구멍의 좌표들을 leaks 배열에 저장하고 오름차순 정렬한다.첫 구멍을 시작으로 길의 L의 테이프로 막히는 구멍들을 leaks에서 제거하고, 새로운 테이프를 사용할 때마다 ans 값을

image인접리스트 adj에 각 동기의 친구들을 저장한다 (양방향)1번(상근)의 각 친구들의 인접노드(친구)를 순회하면서 초대멤버로 등록하면 된다

image브루트포스로 리스트에서 추출한 연속한 k개의 원소 + 보너스 초밥 리스트의 set 길이(중복제거)를 확인하면 된다연속한 k개의 원소는 start:end 두 인덱스를 사용하여 구할 수 있는데, end < n 이면 그냥 start:end를 추출한다.end >

image특별한 알고리즘을 사용하진 않아도 되는 시뮬레이션 문제이다. map과 sort 함수를 활용하니 코드가 간단해졌다.자세한 구현 방법은 주석을 활용했다

imageDP 점화식을 세우면 해결할 수 있는 문제이다D1 = (1)D2 = (1,2), (2,1)D3 = (1,2,3), (2,1,3), (1,3,2)D4 = (1,2,3,4), (2,1,3,4), (1,3,2,4), (1,2,4,3), (2,1,4,3)피보나치 수열

imageDP 방식으로 해결하였다DPi = DNA 문자열의 i번째 문자로 끝나는 길이 P인 부분문자열에서의 A,C,G,T 개수예를들어 ACCATGGACTGA 문자열에서 P가 7일 때 DP11을 구하면 ATGGACT에서의 A,C,G,T 개수를 구하여 2,1,2,2 가 된

image핵심은 가장 큰 기둥을 기준으로 양쪽 기둥들 중 일부를 선택하는데, 결과적으로 산 모양이 나오도록 선택해야 한다는 것이다.그래서 우선 기둥들의 (위치, 높이)를 담은 리스트를 높이가 가장 큰 순서대로 정렬하였다.정렬된 리스트를 순서대로 탐색하면서, 기둥을 선택

imageDFS를 활용하여 각 색깔의 영역의 크기를 구하여 해결했다.