전체 글

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)란?원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 다음 조건을 만족하는 수열이다.각 원소가 이전 원소보다 크다. (증가하고 있다)그 길이가 최대이다 예를 들어, { 6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 } 이다. 구현 방법DP를 이용한 방법이분탐색을 이용한 방법 DP를 이용한 방법 알고리즘 설명간단하지만 시간복잡도가 O(n^2)로 이분탐색보다는 큰 알고리즘이다dp[i]:  i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이라고 한다면,주어진 배열에서 인덱스를 한 칸씩(i+=1) 늘려가면서 확인합니다.내부 반복문으로 i보다 작은 인덱스들을..

문제 바로 가기 > 2225번: 합분해 다이나믹 프로그래밍을 풀 수 있는 문제이다.알고리즘 풀이만약 입력에 예제처럼 6, 4가 주어졌다면6= 0(3번 더해서 0이 되는 경우) + 66= 1 (3번 더해서 1이 되는 경우) + 56= 2 (3번 더해서 2가 되는 경우) + 46= 3 (3번 더해서 3이 되는 경우) + 36= 4 (3번 더해서 4가 되는 경우) + 26= 5 (3번 더해서 5가 되는 경우) + 16= 6 (3번 더해서 6이 되는 경우) + 0 따라서 dp[K][N]: N이하의 정수를 K번 더해서 합이 N이 되는 경우의 수라고 한다면 위의 경우에는 다음과 같이 표현할 수 있다. dp[4][6]=dp[3][0]+dp[3][1]+dp[3][2]+dp[3][3]+dp[3][4]+dp[3][5]+d..

문제 바로 가기 > 4384번: 공평하게 팀 나누기0/1 냅색 알고리즘으로, DP로 풀 수 있다.이 문제는 '부분집합의 합' 문제의 변형으로 볼 수 있다. 우리의 목표는 전체 무게의 절반에 가장 가까운 부분집합을 찾는 것이다.2차원 boolean 배열 dp를 사용합니다.dp[i][j]는 i명의 사람을 선택하여 정확히 j 무게를 만들 수 있는지 여부를 나타낸다 (true/false)알고리즘1. dp 배열 초기화: dp[0][0] = true (0명으로 0kg을 만들 수 있음)2. 각 참가자에 대해:1명부터 전체 인원의 절반까지 선택하는 경우를 고려가능한 모든 무게 조합을 계산하여 dp 배열 갱신for(int i=0; i0; j--){ for(int k=totalWeight; k>=weights..

문제 바로가기> 11000번: 강의실 배정 그리디 알고리즘으로, 우선순위 큐를 이용해서 풀 수 있다. 1 ≤ N ≤ 200,000이므로 브루트포스를 돌리면 당연히 시간초과가 난다. 따라서 정렬을 이용한 우선순위 큐를 이용해 그리디 알고리즘으로 풀어야 한다.  정렬 기준그렇다면 어떤 기준으로 정렬을 해야할까?처음에 필자는 종료시각을 기준으로 (빨리 끝나는 시각 순으로 오름차순) 정렬을 해서 틀렸다...시작 시각으로 정렬을 해야 앞에서부터 차곡 차곡 강의 간의 텀을 짧게 해 배정이 가능한 것이었다. 종료 시간을 우선순위 큐에 넣고 비교정렬 자체는 시작 시각을 기준으로 하였지만, 결국 어떤 강의가 들어갈 자리를 찾기 위해서는 종료시각과 비교를 해야 한다.따라서 그러기 위해서는 종료 시각을 담는 우선순위 큐가 ..

문제 바로가기 > 20055번: 컨베이어 벨트 위의 로봇 단계마다 이동을 할 때 각 단계마다 다음 두 조건을 반드시 지켜야 한다.1. 로봇은 1번칸인 올리는 위치에서만 올릴 수 있다.2. 로봇은 N번칸인 내리는 위치에 도달하면 언제든지 내려야 한다. 각 단계마다 함수로 구현해준다. Step 1 . 벨트와 로봇 회전각 칸을 이동시켜준다로봇을 이동시켜준다이때, 위에 언급한 조건때문에 robot[N-1] (N칸) 위치와 robot[0] (1번째 칸) 위치를 false로 시켜줘야 한다.robot[N-1]=false: 내리는 위치에 도달하면 언제든 내려야 한다.robot[0]=false: 로봇은 올리는 위치에서 3번째 Step에서만 올릴 수 있지, 로봇이 2N칸에서 1칸으로 이동하면 안된다. public st..

Union-Find 연산에서 find()함수의 코드는 일반적으로 이렇게 짠다.public static int find(int x){ if(x==parent[x]) { return x; } return parent[x]=find(parent[x]);} ❗️이때 return을 find(parent[x])이 아니고 왜 parent[x]=find(parent[x]);를 해야할까?다음과 같은 트리 구조가 있다고 하자.1  이런 경우 1이 루트 노드가 되고, parent 배열은 다음과 같다.노드 Idx12345parent[idx]11234 return find(parent[x]);일 경우find(5)를 호출하면:find(5) -> find(4) -> find(3) -> find(2) -..

위상정렬 알고리즘이란?정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 이때 위상정렬은 사이클이 없는 방향 그래프(DAG)에서만 가능하다. 인접 리스트를 사용하면 시간 복잡도가 O(V+E)이고 인접 행렬을 사용하면 시간 복잡도가 O(V^2)이다. 위 DAG 그래프를 위상정렬하면 아래와 같이 여러 결과가 나올 수 있다.구현 방법진입차수를 이용한 BFS 방법과 재귀를 이용한 DFS 방법이 있다.BFS 방법알고리즘 설명진입차수 (in-degree) : 특정한 노드로 들어오는 간선의 개수진출차수 (out-degree) : 특정한 노드에서 나가는 간선의 개수(시작) 진입차수가 0인 정점을 큐에 넣는다.큐가 빌 때까지 다음의 과정을 반복한다.큐에서 ..

프림 알고리즘이란?트리 집합을 단계적으로 확장하는 것이다. 새로운 정점을 연결할 때마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가해줘야 한다. 이때 새로운 정점을 연결하는 것은 가중치를 기준으로 오름차순 정렬한 우선순위 큐에서 꺼낸다는 것이고, 단게적으로 확장하는 것은 이 우선순위 큐에서 뽑을 정점에서 연결 가능하고 방문하지 않은 정점을 우선순위 큐에 추가한다는 것이다.배열로 구현할 경우 시간 복잡도 o(n^2)이고, 최소 힙으로 구현할 경우 시간 복잡도 O(Elog n)이다.구현 방법초기 상태로 정점(=노드)는 서로 연결되어 있지 않다. 정점과 연결된 간선을 하나씩 추가하면서 MST를 만든다. 우선 순위 큐에는 (정점, 가중치) 형식으로 저장되며, 첫 시작은 (시작 정점..

Spanning Tree이란? 신장 트리는 그래프 내의 모든 정점을 포함하는 트리이다. 모든 정점들이 연결 되어 있어야 한다.사이클을 포함해서는 안된다.그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다.MST(=Minimum Spanning Tree)이란?최소 신장 트리는 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 간선의 가중치의 합이 최소여야 한다.n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.사이클이 포함되어서는 안된다. MST 알고리즘 구현 방법- 크루스칼 알고리즘 Kruskal Algorithm- 프림 알고리즘 Prim Algorithm 크루스칼 알고리즘이란?간선을 가중치가 작은 순서대로 그래프에 포함시킨다. ..

문제 바로가기 > 2602번: 돌다리 건너기 완전탐색하면 시간초과가 나므로 dp를 사용해야 한다. 문제 설정두 개의 다리 angleBridge와 devilBridge가 있으며, 원하는 값 answer 대로 발판을 밟아 가며 끝까지 건너야 한다. 이때, 다리를 건너널 때는 두 개의 다리를 번갈아가면서 건너야 한다.DP 배열 설정dp[bridge][i][j]bridge: 현재 위치한 다리를 나타내며, 0은 악마의 돌다리, 1은 천사의 돌다리i: answer에서 현재까지 진행한 문자의 인덱스.j: 각 다리에서 현재 확인하고 있는 발판의 인덱스.초기화dp[0][0][n] 및 dp[1][0][n]은 각 다리의 시작점에서 아직 어떤 문자도 밟지 않은 상태를 나타내므로 1로 초기화DP 점화식일치: 만약 현재 다리의 ..