Daily Log

개념 이해 자료구조란? [Data Structures] 자료구조란? 나쁜 프로그래머는 코드를 걱정한다. 좋은 프로그래머는 자료구조와 그 관계에 대해 걱정한다. medium.com 자료구조 트리선회 [Data Structures] 트리선회 (DFS & BFS) 자료구조 중, 트리의 각 노드를 한 번 씩 방문하는 것을 트리 순회(Tree traversal)라고 한다. 아래와 같은 트리 구조에서 방문했던 노드를 재방문 하지 않고 효율적으로 전체 순회를 하기 위해서는 medium.com - DFS 알고리즘은 트리로 이해하는 것이 가장 쉬움 - 트리에서 Depth를 내려갔다가 다시 올라가고 for문과 섞여 있어서 이해하기 쉬움 - 재귀함수 호출을 depth(깊이로) 경우의 수를 Breadth(너비)로 생각해보아라..

* 문제 가중치 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 최소비용을 출력하는 프로그램을 작성하세요. (!)목적지까지 가는 최소 비용은 보통 "다익스트라 알고리즘" 사용함 인접행렬 활용 // 67번 - 최소비용 DFS 인접행렬 (가중치 방향그래프) #define _CRT_SECURE_NO_WARNINGS #include int n, a, b, c, map[30][30], ch[30], cost = 999999999; //cost는 minimum value void DFS(int v, int sum) { if (v == n) { if (sum < cost) cost = sum; } else { for (int i = 1; i 0 && ch[i] == 0) { ch[i] = 1; DFS(i, s..

64번은 인접행렬로 풀었지만 66번에서는 인접 리스트로 경로를 찾아보자. 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요. ▣ 입력설명 첫째 줄에는 정점의 수 N(1

64번 - 경로탐색 DFS(노드, 간선) * 문제 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 첫째줄: 정점의 수 N(1

* 문제 N개의 원소로 구성된 자연수 집합이 주어짐 집합의 원소와 +, - 연산을 사용하여 특정수인 M을 만드는 경우가 몇가지 있는지 출력하시오. 각 원소는 연산에 한번만 사용한다. - 입력예제 4 12 2 4 6 8 => 원소 4개로 + -를 조합하여 12를 만드는 경우의 수는 몇가지? 경우가 없다면 -1 출력 * 문제 풀이 2를 보면 +2 -2 X 와 같은 3가지 경우 적용가능 4도 마찬가지 +4 -4 X 와 같은 3가지 경우 적용 가능 -2 +6 +8 = 12 은 어떻게 나오나? 깊이 탐색으로 모든 경우의 수 탐색해서 가능 => 완전탐색 - 레벨 5되고 종료! * 코드 구현 //61번 - 특정 수 만들기 #define _CRT_SECURE_NO_WARNINGS #include #include int..

* 문제 N개의 원소로 구성된 자연수 집합이 주어짐 이 집합을 두개의 부분집합으로 나눔 ex. 1 3 5 6 7 10 을 1 3 5 7 과 6, 10 으로 그리고 두 부분집합의 합이 같은 경우가 존재하는지 확인 부분집합의 합이 같은 경우가 있다면 YES 출력 아니면 NO 출력 단, 입력에서 원소는 중복되지 않는다. * 풀이 - 재귀함수를 돌리면서 부분집합을 구함 - 남아있는 원소들 즉, 사용하지 않은 부분집합도 만들어짐 - total에다가 입력받은 원소를 다 더함 - 재귀로 부분집합을 만들어서 합을 만듬 sum - 남아 있는 원소들의 합은 total - sum 이 같으면 두 부분집합이 같은 것임 - 두 부분집합의 합은 같아야 하기 때문에 한쪽의 부분집합의 합이 절반이상이면 항상 NO됨 (다른 한쪽이 작아..

문제: 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 재귀를 이용한 완전탐색을 하며, 이진트리 전위순회 방식으로 출력하시오. 단 공집합은 출력X 입력 3 출력 1 2 3 1 2 1 3 1 2 3 2 3 *풀이 : 전위순회: 루트가 가장먼저 순회되는 것 => 왼쪽자식 => 오른쪽자식 - LEVEL 1 2 3 4로 두기 => L로 컨트롤하기 - ch 배열은 0으로 초기화 - 왼쪽으로 자식함수 넘어갈때는 체크 1, 오른쪽은 체크 0하면서 호출한다. - ch의 인덱스번호를 원소값으로 보자. - if(L == n+1) 종료지점, 여기서 ch배열을 찍어준다. 1 2 3 - D(3)으로 다시갔다가 D(4)로 갈때 ch[L] = 0을 넣는다 L은 이때 3임 -..

- 이진트리 : 기본구성이 부모노드, 왼쪽 자식노드, 오른쪽 자식노드, 3개가 기본구성 - 가정: 부모노드에서 *2하면 왼쪽자식 부모노드에서 *2+1하면 오른쪽 자식 - 재귀함수로 탐색할 것임 - 깊이우선탐색이 무엇인가? : 출발된 노드에서 연결된 노드중에 아무거나 하나를 선택해서 방문하는 것임 그러다 더이상 갈곳이 없다면, 되돌아가서 가지 않았던 노드로 가는 것 전위순회: 부모노드 먼저 출력 -> 왼쪽 -> 오른쪽 자식 출력 중위순회: 부모노드를 중간에 출력하면 중위 순회. 루트노드를 언제 출력하나가 기준임. 왼쪽 자신 먼저 출력->부모노드->오른쪽자식 출력 후위순회 출력: 왼쪽 출력->오른쪽 출력-> 부모출력 코드 구현 - 57번에서 배운 재귀/스택과 유사! - 9번 라인까지 기억되고 넘어감, 재귀가..

- C++의 벡터는 동적 배열구조 클래스 - 자동으로 배열의 크기 조절과 추가 삭제 가능 - 모든 자료형에 대해 배열처럼 저장 가능 But 한번에 한 타입만 저장 가능 - 자바 벡터처럼 배열 크기 추가할 때, 기존 배열 크기의 100% 늘어남 vector integer_vector; vector double_vector; vector char_vector; - 벡터의 기본 함수 //iterator 반복자 begin() //beginning iterator 반환 end() //end iterato 반환 //추가 및 삭제 push_back(element) //벡터 제일 끝에 원소 추가 pop_back() //벡터 제일 끝 원소 삭제 //조회 [i] //i번째 원소 반환 at(i) //i번째 원소 반환 fro..