본문 바로가기
반응형

분류 전체보기1308

[BOJ] 백준 5582 공통 부분 문자열 출처: https://www.acmicpc.net/problem/5582 Input ABRACADABRA ECADADABRBCRDARA Output 5 DP[i][j] = A 문자열의 i번째 문자와 B문자열의 j번째 문자가 공통 부분 문자열의 마지막 문자로 하는 공통부분문자열의 최대 길이 if (A[i] == B[j]) D[i][j] = D[i - 1][j - 1] + 1; #include const int LM = 4002; int an, bn, D[LM][LM], ans; char A[LM], B[LM]; int main() { scanf("%s %s", A + 1, B + 1); for (int i = 1; A[i]; ++i) { for (int j = 1; B[j]; ++j) { if (A[i] .. 2021. 2. 25.
[BOJ] 백준 3653 영화 수집 출처: https://www.acmicpc.net/problem/3653 Input 2 3 3 3 1 1 5 3 4 4 5 Output 2 1 0 3 0 4 처음 DVD가 놓인 위치를 M+1 ~ N까지 『1』로 표시합니다. 그리고 각 DVD의 위치를 pos[] 배열에 저장합니다. Q) 4번째(= pos[4]) 놓인 DVD 위에 쌓여있는 DVD의 개수는? ▶ 1 ~ (7-1)까지 구간의 합 = 3개입니다. Q) 선택된 4번째 DVD를 어디로 옮기면 될까? ▶ 처음 M부터 해서 시작해서 1번째까지 입니다. (next = M) (그렇기 때문에 N 크기 앞에 M만큼 배열 크기 할당) Q) 여기서 4번째(pos[4] = 3) DVD 위에 놓인 DVD 개수는? 구간 [1, 3-1]까지의 구간합 = 0 + 0 = 0.. 2021. 2. 25.
다익스트라 (Dijkstra) 개념 다익스트라 알고리즘은 Single Source shortest path problem으로 하나의 정점에서 다른 모든 정점까지 최단 경로를 구할 때 주로 사용됩니다. 이때, 간선의 가중치는 only 양수가 전제조건입니다. (음의 가중치 X) 실제, 현실 세계에서는 음의 가중치는 일반적이지 않기에 현실에 적합한 알고리즘이라고 볼 수 있습니다. 시뮬레이션 그래프를 인접행렬로 표현 ▶ dist[] 배열 초기화 ※ 시작 정점 = [5] 가정. ← 방문 표시 - 정점 [5]와 연결된 정점 [2], [4]와 정점 [5] 자체에 대한 dist[] 초기화 ▶ 방문하지 않은 정점 가장 비용이 적은 정점 [4] 선택 ← 방문 표시 [4]번 정점과 연결되었으면서 동시에 아직 한번도 방문하지 않은 정점 [2], [3]에 .. 2021. 2. 25.
그래프 정의 및 구현 방식 (인접 행렬 & 인접 리스트) 그래프는 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 정점을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조로 객체들의 상호 관계를 표현하기 위해 고안된 자료 구조입니다. 여러 도시들을 연결하는 도로망, 사람들 간의 지인 관계, 웹사이트 간의 링크 관계 등이 우리 주변에서 찾을 수 있는 연결 구조의 예라고 할 수 있습니다. 여러 객체들이 서로 연결되어 있다는 점에서 그래프는 트리와 별로 다를 것이 없습니다. 그래프 표현 ▶ 인접리스트와 인접행렬 메모리 or 시간 사용 특성이 굉장히 다르기 때문에, 적절한 표현 방식 선택 인접리스트(adjacency list) - 각 정점마다 하나의 연결 리스트를 갖는 방식 |V|개의 연결 리스트에 실제 간선 수만큼의 원소가 들어.. 2021. 2. 25.
그래프 표현 (인접 리스트 / 인접 행렬) 정점 u - v 간 간선 여부 확인 - 인접 리스트는 adList[u]의 처음부터 읽어나가면서 각 원소를 일일이 확인 - 인접 행렬은은 정점 u, v가 주어졌을 때, 단 한 번의 배열의 접근으로 연결 여부 확인 공간 복잡도 - 인접행렬: V × V 개수 만큼 공간 필요 - 인접리스트: 정점 개수 V와 실제 간선의 개수 E에 좌우 (V + E) (만약 간선의 개수가 V에 수렵한다면 인접행렬 비슷한 공간복잡도를 가짐) 결론 - 간선의 수가 V2에 비해 훨씬 적은 그래프를 희소 그래프 → 인접 리스트 - 간선의 수가 V2에 비례하는 그래프를 밀접 그래프 → 인접 행렬 방향성 그래프 (인접 리스트) import java.util.ArrayList; import java.util.Iterator; import j.. 2021. 2. 25.
[BOJ] 백준 3006 터보소트 출처: https://www.acmicpc.net/problem/3006 Input 3 2 1 3 Output 1 0 0 ① 1의 교환횟수 arr = [5 4 3 7 1 2 6] tree = [1 1 1 1 1 1 1] ← 단말 노드만 표시 Bubble Sort와 같이 교환(swap)하기 때문에 결국, 『1』 앞에 몇개의 숫자가 존재하는지 필요합니다. 세그먼트 트리에서 첫번째 부터 현재 숫자 『1』 앞 위치까지의 구간 합이 필요합니다. → [1, pos[1]-1] = [1, 4] = 4 『1』은 이동하였기 때문에 『0』으로 표시하면 다음 구간합을 구할 때 제외처리 할 수 있습니다. ② 7의 교환횟수 arr = [5 4 3 7 1 2 6] tree = [1 1 1 1 0 1 1] ← 단말 노드만 표시 『7.. 2021. 2. 25.
[BOJ] 백준 11053 가장 긴 증가하는 부분 수열 출처: https://www.acmicpc.net/problem/11053 Input 6 10 20 10 30 20 50 Output 4 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com LIS (Longest Increasing Subsequence) subsequence은 연속하지 않아도 되는 부분 수열입니다. 따라서 subsequence의 개수는 N2 입니다. 완전 탐색 방법으로 접근할 경우 T.. 2021. 2. 25.
[BOJ] 백준 12015 가장 긴 증가하는 부분 수열 2 출처: https://www.acmicpc.net/problem/12015 Input 6 10 20 10 30 20 50 Output 4 [BOJ] 11053 가장 긴 증가하는 부분 수열 제의 경우는 N이 최대 1000이기 때문에 DP로 해결가능하였지만 N의 최대 크기가 증가하였기에 구간의 최대값을 가지는 세그먼트 트리 이용 DP에서는 i 번째 숫자가 입력될 때, 0 ~ i-1번째 숫자 중에서 자기보다 작은 j번째 숫자를 찾아 DP[j]의 최대값을 구하는 것이었습니다. 세그먼트 트리에서는 i 번째 숫자 입력될 때, DP[j]의 최대값을 for문으로 탐색하지 않고 구간의 최대값 세그먼트 트리를 이용하는 것입니다. 즉, tree[]의 단말 노드에는 i번째가 숫자가 입력되었을 때, 0 ~ i-1까지 최대값 +.. 2021. 2. 25.
[BOJ] 백준 2792 보석상자 출처: https://www.acmicpc.net/problem/2792 Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com [탐색] Parametric Search [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 경우가 많습니다... 2021. 2. 25.
[BOJ] 백준 2983 개구리 공주 출처: https://www.acmicpc.net/problem/2983 Input 7 5 ACDBB 5 6 8 9 4 13 1 10 7 4 10 9 3 7 Output 7 4 식물들의 위치는 아래와 같습니다. [Jungol] 1889 N Queen 문제에서도 이용했지만 [Jungol] 정올 1889 N Queen 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1162 Input 4 Output 2 N이 4일 때, 나오는 경우는 두 가지이다. 한 행에 놓을 수 있는 여왕말의 개수는 1개 입니다. 그렇기 때문에 행.. zoosso.tistory.com 2차원 평면에서 같은 선상의 대각선상에 위치한 것은 아래와 같이 알 수 있습니다. ▶ (x.. 2021. 2. 25.
반응형

티스토리툴바