프로그래밍 일반/알고리즘 (6) 썸네일형 리스트형 [백준2579] 계단 오르기 1. 입력파트 2. DP relating to forces that produce movement 계속 변한다. 앞으로 나아간다. 규칙성에 의해 나아간다. programming? 모든 경우의수를 찾아서 최적의 값을 구하자!!! 이전의 값이 배열에 저장되어있어야 효율적이게 된다. 1계단 - 10 2계단 - 20 or 20+10 //처음 했던 실수? 10+20만을 생각했던 것 //끝자리는 무조건 포함해야하니까 끝을 기준으로 적는다. 3계단 - 15+10 or 15+20 4계단 - 25+15+10 or 25+20+10 5계단 - 10+25+[20+10(2계단 반복)] or 10+[3계단 반복] dp[5] = arr[5]+arr[4] + dp[2] || arr[5] + dp[3] [알고리즘] BFS와 DFS 쉽게 이해하기 DFS는 미로찾기와 같습니다. 이미 방문한 지점을 check, flag로 표현해주고 연결된 그 다음지점부터 진행하면 됩니다. 만약 끝까지 갔는데 해당 지점이 막혀있다면, 막히지 않았던 그 전지점으로 돌아가서 시작합니다. BFS는 처음 있는 지점에서부터 시작하는 것과 다릅니다. 처음부터 영역을 넓혀가며 하나하나 확인합니다. DFS(Depth First Search) 깊이 탐색 알고리즘에서 가장 중요한 2가지는 flag과 stack진입 조건입니다. 진입시에 flag로 먼저 판별하면 됩니다. 그리고 stack에 넣을 범위와 조건을 설정하면 됩니다. int number = 7; int flag[8]; vector a[8]; void dfs(int x){ //스택에 진입시 flag로 방문했는지 검증한다. if(f.. [알고리즘] 선택정렬 쉽게 생각하기 Selection Sort 선택 정렬은 i기준으로 i의 오른쪽(정렬되지 않은 곳)에서 가장 작은 값을 찾은 뒤에 i랑 바꾸는 것입니다. arr[i]라는 기준 값을 key나 min에 담는 것은 같지만, 내부적으로 정렬하는 것이면 삽입정렬이됩니다. 그런데 내부는 이미 정렬이 되어있으므로, bubble정렬과 같이 한칸씩 오른쪽로 당겨오게 됩니다. 반면 선택정렬은 기준점 i를 기준으로 정렬되지 않은 모든 값들에 대해서 하나하나씩 검사하면서 최소의 값을 찾습니다. int i, j, min; for(int i=0; i [알고리즘] 삽입정렬 쉽게 생각하기 선택정렬은 왼쪽을 기준으로 가장 작은 값을 찾아가는 방식으로 정렬을 진행합니다.. 버블정렬은 오른쪽을 기준(i점)으로 두고 반대편 왼쪽(j점)에서 0으로 두고 i를 하나하나씩 늘려가는 방법으로 정렬을 진행하는 것이었습니다. 이제 왼쪽을 기준(i점)을 시작점으로 두고 하나하나씩 정렬을 진행하는 방법을 알아보겠습니다. 왼쪽 기준은 두 가지로 나뉘는데요, 왼쪽을 기준으로 안쪽을 정렬하느냐, 왼쪽 기준으로 오른쪽으로 정렬하느냐로 나뉩니다. 여기서 왼쪽(정렬된 쪽)은 이미 정렬 된 곳에 삽입한다고 해서 삽입정렬이라고 부릅니다. 이번에는 삽입정렬을 알아보겠습니다. 삽입정렬의 기본 아이디어는 새로 나온 지점 n에 대해서 안쪽에 있는 값을 하나하나씩 다 순차적으로 검사한다는 점입니다. 그런데 이미 정렬이 되어있으므로,.. [알고리즘] 버블정렬 쉽게 생각하기 정렬(Sort)를 할 때 가장 기초적으로 생각할 수 있는 것은 "오른쪽부터 제일 큰 수를 차근차근 쌓아올리겠다" 입니다. 왼쪽을 기준으로 숫자를 세어나가면서 큰 수를 만나면 바로 오른쪽으로 밀어버리면서 정렬을 진행하는 것입니다. 즉, 오른쪽 기준점에 가장 큰 수 i를 두겠다는 목표를 두고 j가 0부터 i가 있는 지점(i-1)까지 하나하나씩 바로 오른쪽에 숫자와 비교를 하여 큰 수를 오른쪽에 두면 됩니다. 그렇게 하면 결국 j가 0에서 i-1이 되었을 때에는 i번째와 비교하면서 i번째까지 중에 가장 큰 수를 오른쪽에 둘 수 있게 됩니다. j가 0에서부터 i-1까지 한 번 가면 기준점 i에 가장 큰 수가 배치되게 됩니다. 그 다음에는 기준점 i의 다음점 i+1에 가장 큰 수를 찾아야 되고, j는 0에서부터 .. [알고리즘] 알고리즘에서 배워야 할 기초 알고리즘은 문제를 해결하는 순서를 의미합니다. 알고리즘을 수행하기 위해서는 가장 먼저 자료가 있어야 합니다. 이를 위해서 가장 먼저 자료구조를 배웁니다. 자료구조는 문제 해결을 위해 가장 효율적으로 자료를 조직하고 구조화하는 활동을 의미합니다. 자료구조는 크게 선형과, 비선형으로 나뉩니다. 선형에서는 스택, 큐, 배열, 연결리스트 등이 있습니다. 비선형 구조에서는 트리와 그래프가 있습니다. 자료가 저장이 되어있다면, 자료를 보기 좋게 정렬합니다. 버블정렬, 삽입정렬, 선택정렬이 가장 기본적인 정렬입니다. 좌우가 붙은 것이 버블처럼 움직인다고 해서 버블정렬이라고 이름붙였습니다. 삽입정렬은 특정 기준 점 이전에 것을 전부 비교한 뒤에 삽입한다고 해서 삽입정렬입니다. 선택정렬은 i이후에 가장 작은 것을 찾아서.. 이전 1 다음
