Daily Log

* 문제 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번 라인까지 기억되고 넘어감, 재귀가..