25/02/24 (월)
다시 월요일입니다.
주말동안 열심히 쉬었으니 다시 달려보겠습니다.
SQLD 시험이 2주도 안남아서 틈틈히 공부하면서 수업을 들어야겠네요.
주말에 전신 웨이트를 해서 오늘 주짓수 잘 할수있을지 걱정입니다..
1. 강의
1) 넥스트 퍼뮤테이션
- 순열 및 조합을 생성할 때 재귀적으로 구현하지 않고 각 인덱스 값을 비교하여 모든 경우의 인덱스 값을 뽑아내는 방법
- 가장 작은 값으로 정렬한 뒤, 한 자리씩 swap하면서 오름차순으로 다음 순열 생성
package basic.Ch25_NextPermutation;
import java.util.Arrays;
// NP : 일부 추출 X, 전체 순열만 빠르게!
// 항상 가장 작은 수부터 출발해서 가장 큰수를 만드는 과정
// while 포함 np() swap() 이용
public class BasicPermNP {
// 기본 순열
static int[] src = {3, 1, 5, 4, 2};
public static void main(String[] args) {
// 가장 작은 수로 대상을 정렬
Arrays.sort(src); // 순열의 경우의 수 중 하나
// 시작은 1 2 3 4 5
while(true) {
// 완성된 순열로 처리 코드
System.out.println(Arrays.toString(src));
if( ! np( src ) ) break; // 가장 큰 수( 5 4 3 2 1 )이면 종료
}
}
static boolean np(int[] array) {
// 3
// 맨 뒤에서 출발
int i = array.length - 1;
// 뒤보다 앞이 크거나 같으면( 내림차순으로 정렬되어 있으면 ) 계속 가다가 그렇지 않으면 멈춘다.
// 5 <-- 4 <-- 2 까지는 계속
// 1 X 5 <-- 4 <-- 2
while( i > 0 && array[i-1] >= array[i] ) --i;
// 맨 앞까지 왔으면 종료
if( i == 0 ) return false;
// 현재 src[i-1] 이 src[i] 보다 작은 상태
// src[i] 이후 항목 (src[i] 보다 작은) 과 src[i-1]과 비교 필요
// 맨 뒤에서 출발
int j = array.length - 1;
// i 이전 항목 중 src[i-1] 보다 작은 것은 무시하고, 큰 것이 있으면 멈춤
// 만약 큰 것이 있으면 그것과 없으면 src[i] 와 교환
while( array[i-1] >= array[j]) --j;
swap( array, i-1, j );
// i 부터 맨 뒤까지 reverse
int k = array.length - 1;
while( i < k ) {
swap(array, i++, k--);
}
return true;
}
static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}package basic.Ch25_NextPermutation;
import java.util.Arrays;
// 조합인데 NP 를 이용, 전체 중 일부를 뽑는 조합에 적용 가능
public class BasicCombNP {
static int[] src = {1, 2, 3, 4, 5};
static int[] tgt = new int[3]; // __ __ __ <= 현재 자리를 채우기 위해, src 의 맨 앞에서부터 수를 선택/비선택 해가면서 tgt 개수를 채운다.
static int[] index = new int[src.length];
public static void main(String[] args) {
// 00000
// 00111 ------> 11100
// tgt 의 1 만큰 index 배열의 뒤부터 채운다.
for (int i = src.length - tgt.length; i < src.length; i++) {
index[i] = 1;
}
System.out.println(Arrays.toString(index));
while(true) {
// 조합이 완성된 후 수행 코드
int tgtIdx = 0;
for (int i = 0; i < index.length; i++) {
if( index[i] == 1 ) { // i 가 선택된 항목의 index
tgt[tgtIdx++] = src[i];
}
}
System.out.println(Arrays.toString(index) + " : " + Arrays.toString(tgt));
if( ! np(index) ) break;
}
}
static boolean np(int[] array) {
// 3
// 맨 뒤에서 출발
int i = array.length - 1;
// 뒤보다 앞이 크거나 같으면( 내림차순으로 정렬되어 있으면 ) 계속 가다가 그렇지 않으면 멈춘다.
// 5 <-- 4 <-- 2 까지는 계속
// 1 X 5 <-- 4 <-- 2
while( i > 0 && array[i-1] >= array[i] ) --i;
// 맨 앞까지 왔으면 종료
if( i == 0 ) return false;
// 현재 src[i-1] 이 src[i] 보다 작은 상태
// src[i] 이후 항목 (src[i] 보다 작은) 과 src[i-1]과 비교 필요
// 맨 뒤에서 출발
int j = array.length - 1;
// i 이전 항목 중 src[i-1] 보다 작은 것은 무시하고, 큰 것이 있으면 멈춤
// 만약 큰 것이 있으면 그것과 없으면 src[i] 와 교환
while( array[i-1] >= array[j]) --j;
swap( array, i-1, j );
// i 부터 맨 뒤까지 reverse
int k = array.length - 1;
while( i < k ) {
swap(array, i++, k--);
}
return true;
}
static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
2. 실습
1) 백준
https://www.acmicpc.net/problem/17135 (오답)
2) 프로그래머스
택배 상자 꺼내기 : https://school.programmers.co.kr/learn/courses/30/lessons/389478 (정답)
서버 증설 횟수 : https://school.programmers.co.kr/learn/courses/30/lessons/389479 (정답)
완전 범죄 : https://school.programmers.co.kr/learn/courses/30/lessons/389480
봉인된 주문 : https://school.programmers.co.kr/learn/courses/30/lessons/389481
3) G3_17135_캐슬 디펜스
package basic.Ch24_문제풀기3;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
// 조합 + 시물레이션
// 궁사의 x 위치를 3개 조합으로 뽑고
// 적들 중에 D 거리안에 해당하는 적만 대상으로 가장 가까운 적을 골라 제거, 적 이동( 아래 1칸 ) 처리
// 자료구조
// 2차원 배열에 적을 두고 이동...부담..
// 적을 ArrayList 에 담고 제거...이동...
public class G3_17135_캐슬디펜스_풀이 {
static int N, M, D, max;
static int[] archer = new int[3]; // 조합의 tgt 에 해당
static List<Enemy> enemyCopy = new ArrayList<>(); // 복사원본
static List<Enemy> enemy = new ArrayList<>(); // 작업본
static PriorityQueue<Enemy> pqueue = new PriorityQueue<>( (e1, e2) -> e1.d == e2.d ? e1.x - e2.x : e1.d - e2.d); // 가장 가까운 거리의 Enemy 찾는 용도
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
// 입력을 받으면서 적만 enemyCopy 에 넣는다.
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
int n = Integer.parseInt(st.nextToken());
if( n == 1 ) enemyCopy.add(new Enemy(i, j)); // 좌표만 이용
}
}
// 궁사 3명의 위치(x) 를 조합으로 선택
comb(0, 0);
System.out.println(max);
}
// 시물레이션 진행
static void check() {
// 원본 자료구조 => 작업 자료구조 복사
// enemyCopy clone ( 담긴 객체가 동일한 객체 ) X
enemy.clear();
for (Enemy e : enemyCopy) {
enemy.add(new Enemy(e.y, e.x)); // enemy.add(e) : 얕은 복사 (객체 공유) X
}
// 현재 궁사의 조합에서 적을 최대로 죽여야 한다.
int dead = 0;
while(true) {
// 3명의 궁사가 한 번씩 D 거리안의 적에게 화살 쏜다.
for (int i = 0; i < 3; i++) {
// 가장 가까운 거리의 적 계산
pqueue.clear();
int ac = archer[i]; // 현재 궁사의 x 좌표
int size = enemy.size();
// 모든 적들 중에 현재 궁사와의 거리가 D 이하인 적만 pqueue 에 담는다.
for (int j = 0; j < size; j++) {
Enemy e = enemy.get(j);
// 현재 궁사의 위치와 꺼낸 e 적의 위치에서 맨하탄 거리
e.d = Math.abs(ac - e.x) + Math.abs(N - e.y);
if( e.d > D ) continue; // 현재 궁사와의 거리가 유효거리인 D 밖일 경우 무시
pqueue.offer(e);
}
// pqueue 가 empty 하지 않으면 적 1개를 꺼내고 죽었다 표시
if( ! pqueue.isEmpty() ) {
pqueue.poll().dead = true;
}
}
// 죽은 적 정리 ( ArrayList 에서 삭제 ), 이동 ( 한칸 아래로 )
// Collection 에서 삭제 시 뒤부터 처리, 또는 Iterator 사용
for (int i = enemy.size()-1; i >= 0; i--) {
Enemy e = enemy.get(i);
if( e.dead ) { // 죽은 적군
enemy.remove(i);
dead++;
}else if( e.y == N - 1) { // 죽지 않았지만 마지막 행이면 삭제
enemy.remove(i);
}else {
e.y++;
}
}
// 모든 적이 다 사라지면 while 종료
if( enemy.size() == 0 ) break;
} // while
max = Math.max(max, dead);
}
static void comb(int srcIdx, int tgtIdx) {
// 기저조건
if( tgtIdx == 3 ) {
check(); // 시물레이션 진행
return;
}
// srcIdx
if( srcIdx == M ) return;
archer[tgtIdx] = srcIdx; // 현재 tgtIdx 자리에 srcIdx 선택
comb(srcIdx + 1, tgtIdx + 1);// 선택 O
comb(srcIdx + 1, tgtIdx );// 선택 X
}
static class Enemy{
int y, x, d; // d: 현재 따지는 궁수와의 거리 <= 객체 생성 시점이 아닌 궁수의 위치가 결정되면 d 를 계산
boolean dead;
Enemy(int y, int x){
this.y = y; this.x = x;
}
}
}
3. 시험 대비 공부
1) 시간 복잡도 표현 (Big-O)
입력 크기 n에 대해 알고리즘이 수행하는 연산 횟수
| O(1) | 배열 접근 arr[i] |
| O(log n) | 이진 탐색 (Binary Search) |
| O(n) | for문 |
| O(n log n) | Merge Sort, Quick Sort (평균) |
| O(n^2) | 이중 for문 |
| O(2^n) | 완전 탐색 (부분집합, DFS) |
| O(n!) | 순열 생성(완전 탐색) |
2) 순열, 조합, 부분집합
순열(Permutation)
- 서로 다른 n개 중 r개를 뽑아 나열
- nPr = n! / (n-r)!
조합(Combination)
- 서로 다른 n개 중 r개를 뽑는 수
- nCr = n! / r! (n-r)!
부분집합(Subset)
- 2^n개의 부분집합 존재
//순열
void permutation(int[] arr, boolean[] visited, int depth, int r) {
if (depth == r) {
System.out.println(Arrays.toString(arr));
return;
}
for (int i = 0; i < arr.length; i++) {
if (!visited[i]) {
visited[i] = true;
arr[depth] = i;
permutation(arr, visited, depth + 1, r);
visited[i] = false;
}
}
}
//조합
void combination(int[] arr, boolean[] visited, int start, int depth, int r) {
if (depth == r) {
for (int i = 0; i < arr.length; i++) {
if (visited[i]) System.out.print(arr[i] + " ");
}
System.out.println();
return;
}
for (int i = start; i < arr.length; i++) {
visited[i] = true;
combination(arr, visited, i + 1, depth + 1, r);
visited[i] = false;
}
}
//부분집합
void subset(int[] arr, boolean[] selected, int idx) {
if (idx == arr.length) {
for (int i = 0; i < arr.length; i++) {
if (selected[i]) System.out.print(arr[i] + " ");
}
System.out.println();
return;
}
selected[idx] = true;
subset(arr, selected, idx + 1);
selected[idx] = false;
subset(arr, selected, idx + 1);
}3) DFS, BFS
| 알고리즘 | 자료구조 | 특징 |
| DFS (깊이 우선 탐색) | Stack / 재귀 | 깊이 우선 탐색 |
| BFS (너비 우선 탐색) | Queue | 최단 경로 탐색에 유리 |
//DFS
void dfs(int node) {
visited[node] = true;
System.out.print(node + " ");
for (int next : graph[node]) {
if (!visited[next]) {
dfs(next);
}
}
}
//BFS
void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int next : graph[node]) {
if (!visited[next]) {
visited[next] = true;
queue.add(next);
}
}
}
}
4) Union-Find (서로소 집합)
int find(int x) {
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
void union(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) parent[rootB] = rootA;
}- Union : 두 집합 합치기
- Find : 부모 노드 찾기
- 경로 압축(최적화) 기법 적용
5) 자료구조 비교
| 자료구조 | 특징 |
| ArrayList | 동적 배열, 검색 빠름 O(1) |
| LinkedList | 삽입/삭제 빠름 O(1) |
| HashSet | 중복 허용X, 검색 빠름 O(1) |
| HashMap | Key-Value 구조, 검색 빠름 O(1) |
6) Stack, Queue, PriorityQueue
| 자료구조 | 특징 |
| Stack | LIFO (후입선출), push(), pop() |
| Queue | FIFO (선입선출), offer(), poll() |
| PriorityQueue | 최소/최대 힙 구조 |
//Stack 예제
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.pop();
//Queue 예제
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.poll();
//PriorityQueue 예제
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);
System.out.println(pq.poll()); // 1 (최소값)
7) 그래프 입력 방식
| 방식 | 특징 |
| 인접 행렬 | 2차원 배열 O(V^2) |
| 인접 리스트 | ArrayList[] O(V+E) |
| 간선 리스트 | List<int[]> (모든 간선 저장) |
//인접 행렬
int[][] graph = new int[V][V];
//인접 리스트
List<Integer>[] graph = new ArrayList[V];
for (int i = 0; i < V; i++) graph[i] = new ArrayList<>();
8) Comparator 정렬
Collections.sort(list, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return Integer.compare(a[0], b[0]); // 첫 번째 값 기준 정렬
}
});- 시간 복잡도 표현 O(n) 등등
- 순열, 조합, 부분집합을 만들 수 있어야 한다
- nPr, nCr 팩토리얼을 이용한 계산법을 알아야 한다
- dfs, bfs 구분할 줄 알아야 한다
- Union findSet(서로소 연산) 이해를 잘 해야한다
- ArrayList, LinkedList, HashSet, HashMap 구분 해야한다 (ArrayList에 해당하는지 HashMap에 해당하는지)
- Stack, Queue, PriorityQueue 사용법 구분 해야한다
- 그래프 입력에 대응하는 자료구조 이해 해야한다 (인접행렬, 인접 리스트, 간선 리스트 등)
- 정렬에 필요한 인터페이스 이해 해야한다 (comparator 등)
'LG 유플러스 유레카 > 알고리즘' 카테고리의 다른 글
| [20일 차] 알고리즘 (문제 풀기2) (0) | 2025.02.21 |
|---|---|
| [19일 차] 알고리즘 (문제 풀기) (0) | 2025.02.20 |
| [18일 차] 알고리즘 (동적 계획법) (0) | 2025.02.19 |