Algorithm

algorithm 목차

BFS는 탐색 시작점에서 인접한 정점들을 전부 탐색한 뒤, 다음 인접한 정점을 탐색하는 알고리즘이다. 일반적으로 최단 경로를 찾는 문제에서 많이 사용되는 알고리즘이다.G그래프를 생성한다.vi 배열이 필요하면 vi도 만들지만, G를 사용할 수 있으면 사용하자시작점 좌표를

인접한 두 개의 원소를 비교하여 자리를 계속 교환한다. 값들이 맨 마지막 인덱스부터 차례차례 정렬이 되는 형태이다.

n = 3, 1 -> 0001 0 : 0001 : 1002 : 0103 : 1104 : 0015 : 1016 : 0117 : 1110 : 000 & 100/010/001 => 1 : 100 & 100/010/001 => 1,2 : 010 & 100/010/001 =>

서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 것을 순열(permutation)이라고한다.

조합 > 서로 다른 n개의 원소에서 r개를 중복없이 순서에도 상관없이 선택하는 것을 조합(combination)이라고 한다. (1) 백트래킹을 이용한 Hard Coding (2) 모듈사용

리스트 내에서 최소값을 찾아 해당 값의 인덱스를 저장하고, 리스트를 탐색하여 최솟값이 인덱스 첫 번째 위치와 교환한다.

한 개 이상의 Node로 이루어진 유한 집합비선형원소들 간에 계층관계를 가지는 계층형 자료구조원소들 간에 관계가 1:n인 자료구조상위 → 하위로 내려가며 확장되는 트리 구조cycle이 없음Node( = 정점)수가 N개 라면, 간선수는 N-1개Tree는 연결 컴포넌트

이진트리 > 모든 노드들이 2개의 서브트리를 가지는 특별한 현태의 트리이다. 1. 이진트리 종류 (1) 포화 이진 트리(Full Binary Tree) > 모든 레벨의 노드가 포화상태로 차 있는 이진 트리이다. (2) 완전 이진 트리(Complete Binary T

DFS는 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면,가장 마지막에 만났던 갈림길 간성이 있느느 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 반복해 모든 정점을 방문하는 순회 방법이다.

병합 정렬은 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법을 채택하는 방법이다.즉, 정확히 반으로 나누고 나중에 정렬한다.⭐ index 버전

분할정복은 주어진 문제를 작은 사례로 나누고(Divide) 각각의 문제들을 해결하여 정복(Conquer)하는 알고리즘이다.모든 경우에 대해 NlogN이다 원래 문제가 분할하여 더 작은 하위 문제로 분할이 가능할 때 까지 나눈다.각 하위의 문제를 재귀적으로 해결한다. 정

다익스트라 알고리즘은 DP를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.⭐ 최대 힙⏩ 매 상황 방문하지 않은 가장 비용이 적은 노드를 선택⏩ 한 번 처리된 노드의 최단 거리는 고정⏩ 종료 시 테이

우선순위 큐는 우선순위를 가지는 데이터들을 저장하는 큐를 의미한다. 데이터를 우선순위에 따라 처리하고 싶을 때 사용하는 자료구조이다.일반큐 : 선형적인 형태를 가지고 있다.우선순위 큐 : 트리 구조로 본다.⭐ 단순히 리스트를 이용해서 구현할 수 있다.⭐ 힙(heap)을

백준 10844_쉬운 계단 수 https://www.acmicpc.net/problem/10844 N이 1일 때는 1,2,3,4,5,6,7,8,9 각 숫자들이 한번씩 사용된다. N이 2일 떄는 1에 의해 (0,1) 2에 의해 (1,3) 등등가가 숫자에서 -1,+1 한

https://www.acmicpc.net/problem/1890시작점이 0,0이고, 도착지가N-1, N-1 로 정해져있다.시작점에서 갈 수 있는 경로에만 DP 테이블을 채워주면 된다.그래서 dpr에 값이 존재 할 때만 테이블을 작성해준다.💯 DP 문제의 경

https://www.acmicpc.net/problem/1912

https://www.acmicpc.net/problem/1699이 문제는 제곱수의 합이 N이 될 수 있는 제곱수의 최소 갯수를 구하는 문제다.제곱수 중 가장 작은 값인 1로 먼저 dp테이블을 채우고 다른 제곱수 들이 더해졌을 때 해당값을 만드는 최소 갯수를

https://www.acmicpc.net/problem/1987해당 문제는 (0,0) 지점에서 조건에 부합하게 이동할 수 있는 최장거리를 구하는 문제다. 가장 먼 거리를 구해야했기 때문에 DFS를 먼저 떠올렸다. 그러나 일반적인 DFS를 했을 때, 첫 경로가

https://www.acmicpc.net/problem/2293

분리집합이란 교집합이 존재하지 않는 두개 이상의 집합을 관리하는 자료구조이다. 서로소 집합, Union - Find라고도 부른다. 주어진 원소(sp)의 부모 node를 반복적으로 탐색하여, 최종적으로 root node를 return한다. 2\. Union

신장트리란 그래프에서 모든 정점을 포함하고 정점 간 서로 연결이 되며 싸이클이 존재하지 않는 tree 그래프를 의미한다.위의 그래프에서 아래와 같은 그래프가 나올 수 있다.아래 그래프와 같은 그래프들을 신장트리라 칭한다. 신장트리는 각각의 간선들이 가중치를 가지고있다.

백준 2225\_합분해

데이터들 중에서 최솟값과, 최댓값을 지속적으로 탐색해 선택적으로 제거하고 싶을 때 우선순위 큐를 활용해서 구현할 수 있다. 이때 최솟값과 최댓값 두 종류의 동작이 있기 때문에 이중 우선순위 큐라고 부를 수 있을 것이다.https://school.programm

https://www.acmicpc.net/problem/1309사자가 주어진 테이블에 조건에 맞게 배치할 수 있는 경우의 수를 묻는 문제이다. ⏩ no : 사자를 배치 않할 때⏩ 1번 : 왼쪽에 배칠 할 때⏩ 2번 : 오른쪽에 배칠 할 때⏩ 각 N에 대해 사

https://www.acmicpc.net/status?user_id=gusehd502&problem_id=1520&from_mine=1업로드중..DFS를 재귀 형태 풀어낸 DP문제이다.도착 지점에서 DFS를 시작하여 한번 탐색한 지점에 도달했을 때 그 지점의

Floyd-Warshall 알고리즘이란? 경로에 가중치가 주어진 경우, 모든 최단 경로를 구해내는 알고리즘이다. 최단경로를 구한다는 점에서 다익스트라와 비슷하지만, 하나의 정점에서 시작해 모든 정점까지의 최단거리를 구하는 것과 차이가 있다.출발 -> 도착지로 초기 가중

https://velog.io/@kimdukbae/%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%AC-Topological-Sorting주말에 정리할 예정

이진 탐색은 정렬된 배열 내부의 데이터에서 탐색 범위를 절반씩 좁혀 나가며 원하는 값을 찾아가는 과정이다.

LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 수열이다. Subsequence는 연속적이지 않아도 되는 부분 수열을 의미한다. 즉 두 수열을 비교할 때 공통적으로 나타나는 부분중 가장 긴 것을 의미한다.https://www.

ㅁㄴㅇ