IT 취업을 위한 알고리즘 문제풀이
1.+) 미로탐색(2차원 배열 DFS)
7\*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면위의 지도에서
2.+) 이진트리 깊이우선탐색 DFS(Depth First Search)
하나하나 선택해가면서 계속 아래로 내려가고, 내려갈 곳이 없어지면 되돌아가면서 가지 않았던 노드에 모두 방문하는 것이다.넓게 탐색하기 전에 깊게 탐색하는 방법이다.전위 순회오른쪽이나 왼쪽 자식의 노드로 가기 전에 자신이 할 일을 하는 것이다.중위 순회왼쪽 자식 노드를
3.+) 부분집합 (DFS 완전탐색)
자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요.첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.첫 번째 줄부터 각각의 부분집합을 출력합니다. 부분집합을 출력하는 순서는 출력예제에서 출력한 순서와
4.+) stack 구조와 사용법, 재귀함수
stack을 이용하는 재귀함수(recursion) stack의 맨 상단에 있는 함수가 지금 실행되고 있는 함수다. void recur(int x) { if(x==0) return; else{ recur(x-1); printf("%d ", x); } } 3을 적으면
5.60. 합이 같은 부분집합(DFS : 아마존 인터뷰)
N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.예를 들어 {1, 3, 5, 6, 7, 10}
6.61. 특정 수 만들기(DFS : MS 인터뷰)
N개의 원소로 구성된 자연수 집합이 주어지면, 집합의 원소와 ‘+’, ‘-’ 연산을 사용하여 특정 수인 M을 만드는 경우가 몇 가지 있는지 출력하는 프로그램을 작성하세요. 각 원소는 연산에 한 번만 사용합니다.예를 들어 {2, 4, 6, 8}이 입력되고, M=12이면2