본문 바로가기

알고리즘 문제풀이 입문: 코딩테스트 대비51

이진트리 레벨탐색 (BFS : Breadth-First Search) 설명아래 그림과 같은 이진트리를 레벨탐색 연습하세요.  레벨 탐색 순회 출력 : 1 2 3 4 5 6 7  문제 해결 레벨 탐색은 말 그대로 레벨 별로 탐색하는 것이다.루트에서 한 번만에 갈 수 있는 애들을 모두 방문하고, 두 번만에 갈 수 있는 애들을 방문하고 ... 이런 식의 과정이다. BFS의 핵심은 큐를 이용하는 것이다. (Queue => FIFO 구조)이전에 이진트리를 구성했던 방법대로 위 문제 사진과 같이 이진트리를 만들어준다static Node root;public static void main(String[] args) { root = new Node(1); root.lt = new Node(2); root.rt = new Node(3); root.lt.lt = new.. 2024. 5. 7.
부분집합 구하기 (DFS) 설명자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 입력첫 번째 줄에 자연수 N(1 출력첫 번째 줄부터 각 줄에 하나씩 부분집합을 아래와 출력예제와 같은 순서로 출력한다.단 공집합은 출력하지 않습니다. 예시 입력 1 3 예시 출력 11 2 31 21 312 323 문제 해결 부분집합을 출력하는 문제이다.1 2 3 이 있으면 1을 2를 3을 부분집합에 넣을 수도 있고, 안 넣을 수도 있다.=> 각각 경우의 수가 2가지 (즉 2의 n제곱)예제 입력 3은 2의 3제곱 8개인데 공집합을 제외하니 7개의 부분집합이 나온다. static int[] ch; 사용 여부를 체크할 체크 배열을 N+1 크기로 선언해준다. DFS(1)이 호출되고, 첫 번째 숫자(1)를.. 2024. 4. 30.
이진트리 순회 (DFS : Depth-First Search) 설명아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요. 전위순회 출력 : 1 2 4 5 3 6 7 (부모 -> 왼쪽 -> 오른쪽)중위순회 출력 : 4 2 5 1 6 3 7 (왼쪽 -> 부모 -> 오른쪽)후위순회 출력 : 4 5 2 6 7 3 1 (왼쪽 -> 오른쪽 -> 부모) 후위순회를 잘 알아놔야 함 => 병합정렬? 중위순회는 스택 그려가면서 하기 꼭 => 강의 다시 듣고 그려보기 직접 문제 해결 class Node { int data; Node lt,rt; public Node(int val) { data = val; lt = rt = null; }}Node: 각 노드를 나타내는 클래스int data : 노드의 값을 저장Node lt : 노드.. 2024. 4. 29.
피보나치 재귀 (메모이제이션) 설명1) 피보나치 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다.2) 입력은 피보나치 수열의 총 항의 수이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다. 입력첫 줄에 총 항수 N(3 출력첫 줄에 피보나치 수열을 출력합니다. 예시 입력 1 10 예시 출력 11 1 2 3 5 8 13 21 34 55   문제 해결 피보나치 수열은 1번째와 2번째항이 1이며, 그 이후의 각 항은 바로 앞 두 항의 합으로 구성된 수열이다.1, 1, 2, 3, 5, 8, 13 ... 이런식으로 구성 된다. n이 1과 2일 경우 1을 리턴하고그 이후부터 FIBO(n-2) + FIBO(n-1) 를 반환하는 재귀함수로 풀어보았다. 하지만 피보나치 수열은 n이 커질수록 동일.. 2024. 4. 29.
팩토리얼 설명자연수 N이 입력되면 N!을 구하는 프로그램을 작성하세요. 입력첫 번째 줄에 자연수 N(1 출력첫 번째 줄에 N팩토리얼 값을 출력합니다. 예시 입력 1 5 예시 출력 1120 문제 해결 팩토리얼은 N에 대해 N ×( N −1 )×( N −2 ) ×...×1과 같이 계산되는 것을 말한다. 팩토리얼은 N = 1일 때 1을 반환한다.그리고 그 이후부터 팩토리얼의 정의에 따라, n이 1보다 크면 n에 (n−1)!의 결과를 곱하여 반환하는 과정을 반복하면 된다. 최종 코드 import java.util.Scanner;public class P03_팩토리얼 { public static void main(String[] args) { Scanner in = new Scanner(System.in.. 2024. 4. 29.
재귀함수를 이용한 이진수 출력 설명10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용해서 출력해야 합니다. 입력첫 번째 줄에 10진수 N(1 출력첫 번째 줄에 이진수를 출력하세요. 예시 입력 1 11 예시 출력 11011 문제 해결 DFS(n) 함수가 호출되며, n을 2로 나누는 재귀 호출을 계속 하며 2진수로 변환하는 과정이다. n이 0이 될때까지 재귀함수를 수행하면 되는데, n이 0이면 함수는 반환된다. 나머지가 나온 순서는 1101이지만 1011로 출력해야하므로 앞 문제에서 설명한 스택프레임 이용해서 풀어보자. System.out.println();의 호출이 DFS(n/2) 보다 이후에 있기에 아래와 같이 동작함.           DFS(11) 호출 → 11 % 2 = 1 (출력되지 않.. 2024. 4. 29.
반응형

티스토리툴바