Daily Log

- 32번 복습하기 - 분할정복? https://kugistory.net/76 분할정복법 (Divide and Conquer) 알고리즘 영역에서 분할정복법(Divide-and-Conquer)은 말 그대로 주어진 문제를 분할하여 해결하는 방법을 말한다. 즉, 한 번에 해결하기 어려운 문제를 작은 단위의 부문제들(subproblems)로 쪼개어 해결하는 방.. kugistory.net https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html [알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io *문제 병합정렬로 주어진..

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

- 스택의 가장 위에 있는 함수가 실행되는 함수다. - D(0)이 실행되면 해당 함수는 x==0이므로 종료됨 - 그러고 맨위의 D(0)이 스택에서 빠짐 - 그다음 스택 최상위 순으로 D(1) - line9까지 하고 넘어왔기 때문에 나머지 line10 마저하고, 함수를 다했으면 스택에서 빠진다. - 재귀는 스택이 비는 순간 main 함수로 옴!!! // 57번 - 재귀함수 이진수 출력 #define _CRT_SECURE_NO_WARNINGS #include using namespace std; void recur(int x) { if (x == 0) return; else { recur(x/2); printf("%d", x%2); } } int main() { int n; scanf("%d", &n); r..

*문제 자연수 N이 주어지면 재귀함수를 이용해서 아래와 같이 출력하시오. 스택을 이용하는 재귀함수 입력 3 출력 1 2 3 *코드구현 // 56번 - 재귀함수 (기본) #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; //반환하는 건 아니고 출력함수라서 void void recur(int x) { if (x == 0) return; //종료지점 else { recur(x - 1); printf("%d ", x); } } int main() { int n; scanf("%d", &n); recur(n); } * 주의! //recur과 printf의 순서를 바꾸면 //1 2 3 => 3 2 1 됨 /..

*문제 입력 3 2 1 3 출력 PPOOPO 결과 A도시에 입력된 결과가 오름차순 (ex.1 2 3) 순으로 B도시에 도착하게 함 *생각 - 스택을 써야하 함 - 조건문 어떻게 달아야 하나, 스택에 넣고, 순서대로 빼는 조건문? *문제 풀이 - 주의! 모든 기차는 교차로에 들어갔다가 B도시에 가야한다. 0) B도시에 순서대로 1 2 3 4 배열을 만들어서 놓는다. 1) 3을 스택에 push한다. 2) push를 했으면 이걸 char 배열에도 P를 넣어야함 나중에 P를 출력해야하니깐 3) stack의 제일 위에 있는 ex.3과 j가 가리키는 부분이 같은지 봐야함. 같지 않으면 넘어감 4) 그 다음 1을 읽어서 스택에 push.. char P 5) 1과 j가 가리키는 곳이 1로 모두 같음. =>pop 하고 ..

* 문제 10진수 N이 입력되면 K진수로 변환하여 출력하는 프로그램을 작성하세요. 스택 자료구조 이용하기 - 입력: 10진수와 몇진수로 할지 (2, 5, 8, 16) 중 택 1 11 2 - 출력: 1011 - 입력: 31 16 - 출력: 1F * 생각 - 스택을 굳이 이용하는 이유는? - 10진수를 다른 진수로 바꾸는 식은? *풀이(스택) 1) 스택이라는 일차원 배열을 만듬 2) top = -1로 초기화 3) push(2); - top은 항상 ++먼저 증가하고 대입하기 때문에 맨 위에 있는 자료를 가리킨다. *K진수 출력 풀이(스택이용) - 입력 11 2 이면 11을 2로 나눈 나머지를 스택에 push한다. - 나눈 몫에서 다시 2로 나눠서 나머지값을 push - 나눈 몫에서 다시 2로 나눠서 나머지 값..

* 문제 - 어떤 수를 소인수분해 했을 때 그 소인수가 2 또는 3 또는 5로만 이루어진 수를 Ugly Number - Ugly Number를 차례대로 적어보면 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, .......입니다. 숫자 1은 Ugly Number의 첫 번째 수 - 자연수 N이 주어지면 Ugly Number를 차례로 적을 때 N번째 Ugly Number를 구하는 프로그램 작성 입력 10 출력 12 * 생각 - N이 입력되면 1부터 무한루프까지 각각 소인수분해해서 2, 3, 5 로만 떨어지면 count++하고, count가 15 즉, N이 되면 while문을 빠져나와서 해당 X수를 적는다. => 시간이 너무 오래걸림...time limited! - 소인수 분해하는 과정?? *..