프로그래밍 (31) 썸네일형 리스트형 [BOJ][DP] 1932. 숫자삼각형 https://www.acmicpc.net/problem/1932 DP 문제다. 문제에서 우리가 잡아내야 할 포인트는 1. 이제까지 선택된 수의 합이 최대가 되는 경로.2. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼/오 중 하나를 선택. 점화식을 세우기 위해서 일단 이해를 해보자. 문제에서는 수들을 삼각형의 형태로 나타내었지만, 어렵게 생각할 필요가 없다.위에서부터 차례대로 배열에 넣어주면 아래와 같다. 그럼 여기서 어떻게 어떠한 값에 대한 왼/오 대각선 값을 가리킬 수 있을까? 보다시피 한 값의 인덱스 +2 = L, +3 = R 이 되는것을 알 수있다. 얼추 이해가 오기 시작하는가?그렇다면 이제 여태까지 이해한 것을 바탕으로 점화식을 세워보자.(arr은 입력받았던 값을 저장해둔 배열이다.).. 그래프, DFS, BFS 그래프정점(Vertex)와 간선(edge)의 집합으로 객체들을 연결 시킨 것. 복잡한 사건들, 객체들 사이의 관계를 나타낼 때 사용된다. 방향이 없이 간선만 연결되 있는 그래프는 무방향 그래프.화살표로 정점간의 방향을 나타내어 연결한 그래프를 방향 그래프라고 한다. 이제 모든 정점이 다 연결 되있는 상태를 완전 그래프라고 한다. 완전 그래프에도 역시 방향, 무방향 그래프가 존재한다.여기서 간선의 수가 차이가 나는데,방향의 경우 N(N-1). 여기서 N은 정점의 수다.무방향의 경우 N(N-1) / 2. 그래프에서 정점의 연결상태를 나타내는 표현법이 있다. 인접 행렬과 인접 리스트가 있다. 인접 행렬은 자신과 연결되있는 정점을 행렬로 표현한 것이다. 연결이 되있는 정점은 1, 안 되있다면 0으로 표현한다.특.. 트리 (Tree) 전위, 중위, 후위, 레벨 순회 트리(Tree)그래프의 일종으로 여러 노드가 한 노드를 가리킬 수 없는 구조.서로 다른 두 노드를 잇는 길이 하나뿐인 그래프. 간단한 부연 설명을 해보자면.. 루트노드 : 트리의 시작 노드 간선 : 노드와 노드를 잇는 선 차수 : 해당 트리의 최대 자식노드의 수 리프노드 : 아무런 자식이 없는 노드. 자식노드 : 위로 간선이 연결되어 부모를 가진 노드. 부모노드 : 아래로 간선이 연결되어 자식을 가진 노드. 형제노드 : 같은 부모를 가진 노드 조상노드 : 해당 노드의 부모 + 부모의 부모 + ... 대손을 거쳐 올라간다.높이 : 간선의 수 서브트리 : 자식노드가 루트노드가 되어 새로 생성된 트리. 트리의 벤다이어그램은 대충 이렇다. 이제 이진 트리부터 한 번 살펴보자. 아주 기본적인 이진 트리. 이진 트.. 퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort) -하나의 요소를 고른 후(Pivot) 기준값보다 작은 요소는 앞에 위치 시키고, 큰 요소는 뒤에 위치시키는 정렬- 다른 말이 필요없다. 무려 퀵 정렬이다. 이름(Quick)에서도 알 수 있듯여러 정렬 알고리즘 중에서 가장 빠르다.평균 시간 복잡도는 O(n) 최악 시간복잡도는 O(n^2)이다. "그렇다면 퀵만 쓰면 되는 것을, 왜 여러 정렬을 쓰는거죠?" 물론, 퀵이 빠르다만, 프로그래밍이라는 것은 Case By Case.상황에 맞춰서 적절한 알고리즘을 사용해야 하는 것이다. 퀵 정렬은 재귀적 구조이므로, 재귀의 이해가 문제없다면금방 이해를 할 수 있으리라 생각한다. 대강 알고리즘의 원리는 이렇다.1. 기준값(Pivot)을 정한다.(Pivot을 정하는 기준은 자기 마음이다)2.. 삽입정렬 (Insertion Sort) 삽입 정렬(Insertion Sort) -이미 정렬 돼있는 배열에 추가 요소를 적절한 위치(?)에 삽입(Insertion) 하여 정렬하는 방식- 평균 시간복잡도, 최악 시간복잡도 모두 O(n^2)인 느린 알고리즘..다만 구현이 용이하며 인플레이스(in-place) 알고리즘이라 한다. 여기서 "적절한 위치"라는 말은,오름차순이냐 내림차순이냐에 따라 비교하는 조건이 달라질 것인데,그 조건에 맞게 비교하고 교환을 하라는 뜻이다. 또한 "이미 정렬 돼있는 배열"이라는 말은 첫 Loop때 배열의 첫 번째 요소와 두 번째 요소는 무조건 정렬을 시키고이후 Loop 부터는 그 정렬된 배열과 비교하며 교환을 하는 방식이라서 그렇다. -Sample Source- 선택정렬 (Selection Sort) 선택 정렬(Selection Sort) -배열의 요소 중 최댓값 or 최솟값을 골라서(Selection),배열의 가장 끝의 요소와 교환 하는 정렬 - 총 n개의 데이터가 있다면, 교환 횟수는 많아야 n-1번 비교 횟수는 n(n-1) / 2번, 시간 복잡도는 O(n^2)이다.비교 횟수가 버블 정렬과 같다는 특징이 있다. -Sample Source- 버블 정렬 (Bubble Sort) 버블 정렬 (Bubble Sort) -서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 맨 뒤로 보내며 정렬하는 방식- 최악의 경우 시간복잡도는 O(n^2),최선의 경우 시간복잡도는 O(n),평균 시간복잡도는 O(n^2)이다. (시간 복잡도의 개념을 알고 싶다면 위키보다는 이 블로그를 추천한다.) 평균이 O(n^2)인 느린 알고리즘이지만, 병렬 처리에 적합하며 코드가 간단하다. 왜 느리냐 하면은, 모든 요소에 대해 비교하고, 해당 되는 요소에 교환을 하기 때문. 데이터들을 교환 시킬 때 거품이 수면 위로 올라오는 것 같다 하여버블 정렬이라고 한다.(실제로 버블정렬 애니메이션을 보면 그렇게 보이는 것 같다) -Sample Source- 이전 1 2 3 4 다음
