Algorithm8 동적 계획법 (DP) 1. 중복이 많은 완전 탐색피보나치 수열 : 첫재 및 둘쨰 항이 1이며 그 뒤의 모든 항은 바로 앞 두항의 합인 수열점화식 : f(0) = 1, f(1) = 1, f(n) = f(n-1) + f(n-2)만약 완전 탐색(백트레킹)으로 해결한다면?f(5)가 필요하다면 ? → f(4) + f(3) 이 필요해f(4)가 필요하면 → f(3)과 f(2)가 필요해f(3)이 필요하면 → f(2)와 f(1)이 필요해탑 다운 방식으로 해결하려고 한다면 너무 비효율적이고 중복으로 구해야 하는 부분이 많다.→ 시간 복잡도 : 약 O(2^n)…. 너무 오래 걸리고 비효율적이다.그렇다면 먼저 계산한 값들을 저장해놓고 필요할 때 사용하면 편하겠는데??? → 메모이제이션 2. 메모이제이션메모이제이션 : 작은 문제의 결과값을 저장해놓.. 2024. 6. 27. MST (Minimun Spanning Tree, 최소 신장 트리) 그래프와 트리비선형 자료구조 : 객체간의 관계를 관리하며 하나의 자료 뒤에 여러 개의 자료가 존재그래프 : 노드(정점, 위치), 간선(위치간 관계), 가중치(간선에 할당된 비용)로 이루어진 자료구조유향 그래프, 무향 그래프 : 단방향이면 유향, 양방향이면 무향트리 : 사이클 없이 모든 노드가 하나의 연결 요소인 그래프사이클 - 단순 경로(노드가 중복되지 않은 경로)의 시작점과 종점이 동일한 그래프→ 노드의 개수가 n개일 때, 간선의 개수는 n-1개 이다.기본 트리는 루트를 고려하지 않음, 루트를 고려하면 루티드 트리가 된다.신장 트리(Spanning Tree) : 그래프 내의 모든 정점을 포함하는 트리→ 최소 연결(간선의 수가 가장 적은 부분 그래프)→ n개의 노드에 n-1개의 간선으로 모두 연결된 그래.. 2024. 6. 26. [백준] 17143번 낚시왕 (Gold 1) 문제링크 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제 접근 1. 2차원 배열에 상어가 존재 2. 각 상어들은 (방향 / 크기 / 속도)를 가진 객체 3. 매초마다 사람은 오른쪽으로 한칸씩 이동하면서 상어를 잡는다. 4. 상어가 이동하는 방향은 1->2->1 혹은 2->1->2 혹은 3->4->3 혹은 4->3->4 이다. 5. 즉, 상어는 아무리 많이 이동해도 매초 (R-1) * 2 마다 같은 위치에 위치하고 같은 방향을 바라보게 되어 실제로 움직이는 것은 (Speed % ((R-1.. 2024. 4. 20. [백준] 17616번 등수 찾기 (Gold 3) 문제 링크 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 문제 접근 문제는 "최대 몇등부터 몇등까지 할 수 있냐" 를 구하는 문제다. 이 말은 "내 앞에 확정 몇명이 있고 + 내 뒤에 확정 몇명이 있냐" 를 묻는 것과 동일하다. 문제의 입력 형태 "a b"는 "a가 b보다 앞에 등수에 위치한다"는 뜻으로, 이를 통해서 2차원 벡터 vector arr[MAX] 를 통해 단방향 연결을 구현했다. 또한 vector rev_arr[MAX]를 통해 반대 .. 2024. 4. 18. [알고리즘/프로그래머스] 아이템 줍기 (Lv.3) [ 문제이해 ] 이 문제는 좌표평면에 여러개의 사각형이 놓여 하나의 다각형의 형태로 이루어져 있을 때, 다각형의 둘레를 따라 캐릭터가 이동하며 아이템이 놓여있는 곳까지의 최소 거리를 구하는 문제이다. 문제의 경우에서는 2개 이상의 다각형 또는 한 직사각형이 다른 직사각형을 완전히 포함하는 경우를 제외하기 때문에 어렵지 않은 문제였다. [ 문제풀이 ] 이 문제에서의 키 포인트라면 좌표 평면을 기준으로 플레이어가 둘레를 따라 움직여야 한다. 하지만 일반적인 DFS로 해결하려 한다면 위의 빨간줄을 따라 캐릭터가 이동한다면 캐릭터가 (3, 5)에 위치한다면 (4, 6)으로 이동할 뿐 아니라 (3, 6)으로도 이동할 수 있다. 이 방법은 생각보다 매우 쉽게 해결되었다. 그 방법은 바로 모든 좌표를 2배로 늘려주어.. 2023. 10. 4. [알고리즘/프로그래머스] 양과 늑대 (Lv.3) [ 문제이해 ] 문제의 기본 유형은 이진 트리 모양의 초원에 각 노드마다 양 또는 늑대가 한마리씩 놓여있다. 이때, 루트 노드에서 출발하여 각 노드를 돌아다니면서 노드에 있는 동물을 데리고 다니는데 양의 수가 늑대의 수보다 항상 많아야 한다. 만약 늑대의 수가 더 많다면 양은 모두 잡아먹혀 양은 0마리가 된다. 또한, 한번 방문한 노드를 다시 방문할 수 있고, 중간에 양이 잡아 먹히지 않으면서 가장 많은 수의 양을 모으는 경우에서 양의 수를 결과값으로 내면 된다. [ 문제풀이 ] 사실 문제 자체는 어렵지 않아 처음 문제를 접했을 때, 간단한 DFS문제로 해결하면 되는 줄 알았다. 하지만 보통의 DFS의 경우 한번 방문한 노드의 경우 다시 방문하지 않는다. 이 문제에서는 방문한 노드를 다시 방문해도 되지만.. 2023. 10. 4. 플로이드 와샬 개념 + 구현(최단 경로 찾기) 최단 거리를 구하는 다양한 알고리즘이 있지만 오늘은 플로이드 와샬의 개념과 구현에 대해서 한번 포스팅 해보려고 한다. 1. 플로이드 와샬 알고리즘 개념플로이드 와샬 알고리즘과 다른 최단 경로를 찾는 알고리즘의 차이점은 플로이드 와샬의 경우 모든 정점에서 모든 정점으로의 최단 경로를 한번에 구한다. 즉 정점과 정점, 모든 쌍의 최단 경로를 구하는 것이다. 방법은 먼저 가능한 모든 쌍을 표현하는 행렬(이차원 배열)을 선언하고 다이나믹 프로그래밍(dp)의 방식으로 각각의 원소들(각 쌍의 최단거리)을 업데이트 해나간다.업데이트 기준를 행하는 기준은 현재 거쳐가는 정점이다거쳐가는 정점을 기준으로 알고리즘을 수행한다.i 에서 j 로 가는데 해당 정점을 경유해서 가는 것이 더 빠르다면 그 정점을 거쳐서 가는걸로 업데.. 2023. 10. 2. [알고리즘/프로그래머스] 길 찾기 게임 (Lv.3) 코테 스터디에서 공부한 문제로 프로그래머스의 길찾기게임 문제이다. [ 문제풀이 ] 기본적인 문제 해석은 노드의 위치가 주어질 때 이진 트리를 완성하고 각 트리의 전위 순회, 후위 순회를 진행하면 되는 문제였다. 전위 순회, 후위 순회의 경우 재귀적으로 해결하면 어렵지 않은 알고리즘이지만, 이 문제의 경우 주어진 노드들을 연결하여 트리를 완성하는 것이 관건인 문제였다.트리를 완성하는 단계는 아래에 설명으로 표시하겠다. #1. TREE 구성 기본적으로 트리를 작성하기 위해 TREE라는 구조체를 새로 정의할 수 있어야 하는 문제였다.문제에서는 주어진 노드들의 좌표와 문제에서 설명된 이진 트리의 특성을 통해 이진 트리를 완성하기만 하면 쉬운 문제다. 먼저 Tree의 경우 필요한 변수들을 생각해보았다. 1. 트리.. 2023. 10. 2. 이전 1 다음
