c++

이진트리란 자식 노드의 수가 0 ~ 2개인 트리를 말한다. 이를 재귀적으로 표현할 수 있는데, 단일 노드이거나 해당 노드의 자식 노드가 모두 이진 트리라면 해당 노드를 이진트리라고 부른다. 완전이진트리란 이진트리를 채워나갈 때 마지막 노드가 왼쪽부터 차례대로 채워진 트리의 형태이다. 위 그림에서 볼 수 있듯이, internal 노드의 수는 3, external 노드의 수는 3, 높이 h는 2이다. external 노드가 왼쪽부터 차례대로 채워졌으므로 위의 트리는 완전이진트리가 된다. 만약 왼쪽부터 채우다가 오른쪽 끝까지, 즉 external 노드의 수가 2^h개라면 이를 포화이진트리라고 부른다. internal 노드의 수는 3, external 노드의 수는 4, 높이 h는 2이다. external 노드가..

N개의 동전을 가지고 K원을 만드는 경우의 수를 구하는 방법 N = 3, K = 10이며, 1원, 2원, 5원을 무한히 가지고있을때 동전을 사용하여 10원을 만드는 경우의 수를 구하는 문제이다. 단, 중복되는 경우는 제외해야한다 예를 들어, 3원을 만들 때 1원 + 2원 == 2원 + 1원인 경우를 의미한다. 처음에는 2차원 배열을 통해 구현했다 dp[N][K] 에서 N은 각 동전까지 사용했을 때 얻을 수 있는 K원의 경우의 수를 의미한다. dp[0][0] = 1 0원을 만드는 경우의 수는 아무 동전도 사용하지 않을 때라고 생각하면 1가지이다. 또한, 1원까지 사용했을 때 만들 수 있는 K원의 개수 역시 1가지이다. 이를 표로 정리하면 아래와 같다. N | K (i | j) 0 1 2 3 4 5 6 7 ..

집합 N N = { 2, 3, 4 } N의 부분집합을 S라고 할 때, S의 모든 원소의 곱의 합을 구하는 방법 S = { 2 }, { 3 }, { 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 }, { 2, 3, 4 } 1. 원소 개수가 1개인 경우 -> 2 + 3 + 4 = 9 2. 원소 개수가 2개인 경우 -> 2 * 3 + 2 * 4 + 3 * 4 = 26 3. 원소 개수가 3개인 경우 -> 2 * 3 * 4 = 24 모두 더하면 59가 된다 이를 간단히 구해보자 원소 2, 3, 4를 각각 X, Y, Z라고 하면 모든 원소의 곱의 합은 X + Y + Z + XY + XZ + YZ + XYZ가 된다 (곱하기 기호 생략) 즉, ( X + 1 ) * ( Y + 1 ) * ( Z + 1 ) - ..

위와 같은 그림을 얻기 위한 코드를 짜보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include using namespace std; int main() { for (int i = 0; i

처음 이 개념을 접한 것은 20년도 9월쯤이다. 처음 접하고 이해를 못해서 지금까지 방치하다가 2년도 더 지난 오늘 각잡고 하는 Linked List 공부해봤는데, 실제로는 생각보다 더 단순했다. 처음 배울때는 구조체를 일절 사용하지 않고 class 두 개로 구현했는데, 열심히 구글링을 해보니깐 이 방식이 더 많았다. 일단 개념은 어느정도 알고 있었으므로 코드 보면서 따라 치며 혼자 이해하려고 노력했다. 가장 중요시했던 문제는 Insert 하는 방법이랑 Delete 하는 방법이어서 이 두 부분을 여러 블로그 돌아다니며 열심히 찾아보고 나름대로 생각하고 그림 그려가면서 구현한 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..