본문 바로가기

전체 글

 (162)
섹션 7 Recursive, Tree, Graph - 6. 부분집합 구하기(DFS) 📌 문제 설명자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성한다.단, 공집합은 출력하지 않는다.예를 들어, N=3이면 집합 {1,2,3}의 부분집합을 출력하는 것이다.📝 입력 & 출력입력첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 10)출력각 줄마다 하나의 부분집합을 출력한다.원소들은 오름차순으로 나열하고, 공집합은 출력하지 않는다.🔹 예제 입력 & 출력예제 입력3 예제 출력1 2 31 21 312 323💡 해결 방법이 문제는 모든 부분집합(Subset) 을 구하는 문제이다.DFS(깊이우선탐색)를 이용하여 다음과 같이 문제를 해결할 수 있다:각 원소를 "부분집합에 포함시킬지 말지" 결정한다.즉, 트리 구조로 보면 한 노드마다 "선택함" 또..
섹션 7 Recursive, Tree, Graph - 5. 이진트리 순회(깊이우선탐색) 📌 문제 설명이진트리(Binary Tree)가 주어졌을 때,깊이우선탐색(DFS)을 이용해 전위순회, 중위순회, 후위순회를 연습한다.아래와 같은 이진트리를 예시로 한다. 1 / \ 2 3 / \ / \ 4 5 6 7📝 입력 & 출력입력트리는 문제에 주어진 대로 직접 생성한다.(루트 노드부터 자식 노드를 차례로 연결)출력전위순회(Preorder) 결과 출력중위순회(Inorder) 결과 출력후위순회(Postorder) 결과 출력🔹 예제 입력 & 출력예제 출력전위순회 출력: 1 2 4 5 3 6 7 중위순회 출력: 4 2 5 1 6 3 7 후위순회 출력: 4 5 2 6 7 3 1💡 해결 방법이진트리 순회(Traversal)는 크게 세 가지 방..
섹션 7 Recursive, Tree, Graph - 4. 피보나치 수열 📌 문제 설명피보나치 수열을 출력하는 프로그램을 작성한다.피보나치 수열이란 앞의 두 수를 합하여 다음 수를 만드는 수열이다.(예시: 1, 1, 2, 3, 5, 8, 13, ...)📝 입력 & 출력입력첫 줄에 총 항수 N이 입력된다. (3 ≤ N ≤ 45)출력피보나치 수열의 첫 N개 항을 출력한다.🔹 예제 입력 & 출력예제 입력 10 예제 출력 1 1 2 3 5 8 13 21 34 55💡 해결 방법피보나치 수열을 구현하는 방법은 여러 가지가 있다:재귀 호출 + 메모이제이션 사용반복문(for문) 사용재귀는 코드가 간결하지만 성능이 떨어질 수 있어서,메모이제이션을 적용하거나 반복문을 사용하는 것이 더 안정적이다.💻 코드 구현 (Java)1️⃣ 재귀 + 메모이제이션 방식package partRecurs..
섹션 7 Recursive, Tree, Graph - 2. 재귀함수를 이용한 이진수 출력 📌 문제 설명10진수 N이 주어졌을 때, 재귀함수를 이용해 이 수를 이진수로 출력하는 프로그램을 작성하시오.단, Integer.toBinaryString() 같은 내장 함수는 사용하지 않는다.📝 입력 & 출력입력첫 줄에 자연수 N이 주어진다.(1 ≤ N ≤ 1,000)출력재귀를 통해 N을 2진수로 변환하여 출력한다.🔹 예제 입력 & 출력예제 입력 11 예제 출력1011💡 해결 방법10진수를 2진수로 변환하는 방식은 아래와 같다:N을 2로 나눈 몫을 재귀적으로 나누고,나머지를 출력하면 가장 앞자리부터 2진수가 출력된다.즉, N을 계속 2로 나누면서 DFS 깊이 들어가다가,가장 작은 N까지 간 다음 재귀가 빠져나오면서 역순으로 나머지들이 출력됨.💻 코드 구현 (Java)package partRecu..
섹션6. Sort - 10. 마구간 정하기(결정알고리즘) 📌 문제 설명N개의 마구간이 수직선상에 존재합니다. 각 마구간의 좌표는 모두 다릅니다.현수는 C마리의 말을 가지고 있으며, 말들은 서로 가까이 있는 것을 싫어합니다.한 마구간에 한 마리의 말만 넣을 수 있으며, 가장 가까운 두 말 사이의 거리를 최대한 크게 하고자 합니다.목표: 말을 배치했을 때 가장 가까운 두 말 사이의 거리의 최대값을 구하시오.📝 입력 & 출력입력첫 줄: 자연수 N(3≤N≤200,000)과 C(2≤C≤N)둘째 줄: N개의 마구간 좌표 (0≤xi≤1,000,000,000)출력첫 줄에 가장 가까운 두 말 사이의 최대 거리를 출력합니다.🔹 예제 입력 & 출력예제 입력 15 31 2 8 4 9 예제 출력 13 예제 해설1, 2, 4, 8, 9 중에1번 마구간에 말 배치4번 마구간에 말..
섹션6. Sort - 9. 뮤직비디오(결정알고리즘) ☕️ 자주 쓰는 Arrays.stream 정리Arrays.stream(arr).sum() → 배열의 총합Arrays.stream(arr).max().getAsInt() → 배열의 최대값Arrays.stream(arr).min().getAsInt() → 배열의 최소값Arrays.stream(arr).average().getAsDouble() → 평균값 (double 리턴)Arrays.stream(arr).distinct().toArray() → 중복 제거한 배열 반환📌 문제 설명가수 조영필의 라이브 공연을 DVD로 제작하려고 합니다. 총 N개의 곡이 있으며, M개의 DVD에 곡들을 나눠 담아야 합니다. 이때 다음 조건을 지켜야 합니다:곡의 순서는 바뀌면 안 됨곡을 나눠서 담으면 안 됨모든 DVD는 같은 ..
섹션6. Sort - 8. 이분검색 📌 문제 설명N개의 자연수가 주어지고, 이 수들을 오름차순 정렬한 뒤 이 중 특정 수 M이 몇 번째에 존재하는지 이분 탐색(Binary Search)으로 찾아야 합니다.중복된 숫자는 존재하지 않음정렬 후 이분 검색을 통해 위치를 찾음📝 입력 & 출력입력첫 줄에 자연수 N(3≤N≤1,000,000)과 찾고자 하는 수 M이 주어진다.둘째 줄에 N개의 자연수가 공백으로 구분되어 주어진다.출력오름차순 정렬 후 M이 존재하는 위치(1부터 시작하는 인덱스) 출력🔹 예제 입력 & 출력예제 입력8 3223 87 65 12 57 32 99 81 예제 출력3💡 해결 방법배열을 오름차순으로 정렬한 후 이분 탐색을 수행이분 탐색의 기본 조건:lt는 0부터 시작rt는 배열의 마지막 인덱스mid = (lt + rt) / ..
섹션6. Sort - 7. 좌표 정렬 📌 문제 설명N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하세요.정렬 기준은 다음과 같습니다:x값을 기준으로 정렬만약 x값이 같다면 y값 기준으로 정렬📝 입력 & 출력입력첫 번째 줄에 좌표의 개수 N (3 이후 N줄에 걸쳐 각각의 x, y 좌표값이 주어짐 (x, y는 양의 정수)출력정렬된 좌표를 한 줄에 하나씩 출력 (x y)🔹 예제 입력 & 출력예제 입력 152 71 31 22 53 6 예제 출력 11 21 32 52 73 6💡 해결 방법좌표를 저장할 클래스를 만들고 (Point)Comparable 인터페이스를 사용해 정렬 기준을 직접 정의Collections.sort()로 정렬💻 코드 구현 (Java)package partSort;import j..

티스토리툴바