Joon's Blog Joon's Blog

문제분석 처음에 해석 잘하셔야 돼요!!... 저는 이해를 잘 못해서 연속된 두 개의 수로 풀고 기차게 틀렸었습니다... 그러니까 이 문제는 연속된 여러 개의 숫자를 더했을 때 나올 수 있는 가장 큰 수를 찾는 문제죠. 만약에 이 문제가 DP 문제인 것을 파악하지 못했다면 3중 for문으로 해결할 수도 있어요. 시작점, 끝점, 중단점 이런 식으로 나눠서요. ...더보기 cin >> n; for (int st = 1; st s[i]; } d[1] = s[1]; for (int i = 2; i

문제분석 내용이 어렵지 않아서 추가적인 설명은 굳이 필요 없을 것 같아서 패스할게요~ 저만 그럴 수도 있지만... 처음에 이 문제를 보고 생각한 게 배열의 행을 2로 잡고 해야 되나? 도형을 뭐로 표현하지? 라고 생각했었는데 그럴 필요가 없더군요... DP 문제 점화식만 파악하면 되는 문제입니다. 우선 눈으로만 봐도 알 수 있는 경우의 수를 정의해봅시다! D[n] = 가로길이가 n 인 직사각형을 채우는 경우의 수 A = 가로길이가 2 인 직사각형 B = 가로길이가 1 인 직사각형 이라고 했을 때, D[0] = 0 D[1] = 1 D[2] = 2 3가지 경우는 확실해집니다. 이제 D[3] 에 대해서 봅시다. 상황을 두 가지로 나누어 볼 수 있습니다. D[3] 의 처음 블록을 A 로 시작하는 경우 이 경우 ..

문제 분석 문제는 RGB 거리에 R,G,B 의 색으로 집을 칠하는 최소비용을 구하는 것이다. 이때, 이웃하는 집의 색은 달라야 한다. 예를 들어 G 의 인덱스가 i 라고 할 때 i + 1 과 i - 1 이 이웃하는 집이다. 우선 최소비용과 색을 포함할 수 있는 배열을 선언하자. d[i][0] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 빨간색 d[i][1] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 초록색 d[i][2] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 파란색 이제 배열이 선언됐으니 점화식을 끌어내 보자. 우선 경우의 수가 하나밖에 없는 초깃값들을 초기화 하자. d[0][0] = s[0][0] , d[0][1] = s[0][1] , d[0][2] = s[..

문제 분석 각 계단을 오를 때 계단에 적혀있는 숫자의 합이 가장 큰 경우를 구하는 문제다. 조건은 다음과 같습니다. ...더보기 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 자, 지금부터 s[i] = 계단의 적힌 숫자 d[i][j] = 현재까지 j 개의 계단을 연속해서 밟고, i 번째 계단에 올라섰을 때의 점수 합의 최댓값이라고 합시다. (단, i 번째 계단은 반드시 밟는다.) 이상태에서 주어진 계단에 대해서 한번 값을 찾아봅시다. 첫 번째 계단에서는 이러한 값이 도출됩니다. d[..

문제분석 문제는 이렇습니다. 임의의 숫자를 3가지의 연산을 이용하여 1을 만들고자 할때, 연산횟수의 최솟값은 ?! 1. X가 3으로 나누어 떨어지는 경우, 3으로 나눈다. 2. X가 2로 나누어 떨어지는 경우, 2로 나눈다. 3. X 에 1을 뺀다. 예를 들어, 12이라는 숫자가 주어졌고 같이 1로 만들어 봅시다. 첫번째 12 > 4 > 2 > 1 총 3회 두번째 12 > 6 > 3 > 1 총 3회 이런식으로 3가지의 연산을 사용하면 다양한 경우의 수가 등장합니다. 그러면 이 경우의 수를 모두 따져봅시다. d[i] = i 를 1로 만드는 최소 연산 횟수 라고 정의합시다. 1. x가 3으로 나누어 떨어지면, 3으로 나눈다. d[12] = d[12/3] + 1 ...더보기 현재, 12는 3으로 나누어 떨어지..

개념 Hash Function : 해시 함수는 임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어주는 함수이다. 이 때 함수를 구현하는 방법에 따라서 해당 서로 다른 임의의 문자열이 같은 고정 문자열로 되기도 하며 이러한 부분을 충돌이라고 한다.(H(s1) = H(s2)) 아래 사진의 경우에는 좌측에 파란 색들이 key이며 각 key값들이 해시 함수의 결과를 오른쪽 우측에 숫자로 바뀌었음을 보여준다. 나중에 해시 테이블에서는 이 key을 해시한 결과를 배열의 인덱스로 사용한다. 해시 함수를 H()라고 했을 때 H(Jonh Smith) = 02 해시 충돌(Hash Collision) 서로 다른 문자열을 해시한 결과가 동일한 경우 해시 함수를 H()라고 했을 때 서로 다른 문자열 s1과 s2에 대해서 H(s..

개념 이진검색트리를 확장한 것으로 두개 이상의 key 를 사용합니다. 다른 말로 다차원 검색트리로 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기합니다. 현재 그림은 두개의 key 를 갖고있는 KD 트리이다. 왼쪽 key 를 x, 오른쪽 key 를 y 라고 생각 한다면 깊이 1 위치에 A 에서는 처음에 x 를 기준으로 작으면 왼쪽 크면 오른쪽으로 분리한다. 그리고 깊이 2 위치에 B,C 에서는 y 의 값을 기준으로 깊이 3 에서는 x의 값을 기준으로 삽입을 한다. 삭제 1. 자식이 없는 경우 : 노드만 제거 2. 자식이 하나뿐인 경우 : 자식이 둘인 경우와 같이 해결 : 왼쪽 자식만 있는경우, 왼쪽 서브트리 중 노드 r에서의 분기에 사용한 필드 값이 가장 큰 노드를 찾아서 이동 3. ..

기본개념 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 쉽게 말해서 키를 다수 보유하고 있는 트리라고 할 수 있다. B-트리의 조건 모든 단말노드는 동일한 높이를 가진다. 각 내부노드의 자식노드는 M/2 이상 M 이하이다. (M은 2보다 큰 정수로서 트리노드의 최대 자식 수) 루트의 자식 수는 두개 이상이다. ...더보기 우리는 트리의 높이를 최소화 하기 위해 자가균형트리를 배웠다. (레드블랙트리, AVL 트리) B트리는 키의 갯수를 증가시켜 트리의 좌우를 넓히는 방법으로 높이를 낮췄다고 생각하면 도움이 될것이다. 탐색 B트리는 이진트리와 마찬가지로 중위순..