재귀 - 하노이 탑
'Flat' 하게
같은 꼴(모양, 동작) 형태로 일반화
현재 할 수 있는 일 -> 나머지
hanoi(N, 시작, 임시, 목적)
그 다음 재귀를 부를 때 기억하고 싶은 걸 넘겨주자.
// Bj 11729
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Bj11729 {
static StringBuilder s = new StringBuilder();
static int hanoi(int n,int start,int tmp, int end){
if(n==1){
s.append(start+" "+end+"\n");
return 1;
}
return hanoi(n-1,start,end,tmp)+hanoi(1,start,tmp,end)+hanoi(n-1,tmp,start,end);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int move = hanoi(N,1,2,3);
System.out.println(move);
System.out.println(s);
}
}
// 출력을 나중에 해주어야 함으로 StringBuilder를 전역으로 설정해 한 번에 출력.
// 시작, 종료, 임시 매개변수를 추가해 위치 이동을 출력해줌.
// BufferedReader -> new InputStreamReader -> readLine() -> StringToknizer -> StringBuilder
-----
Bj 1914번 - 하노이의 탑 +
BigInteger bi = new BigInteger("1048576"); // 2의 20승
if(N>20){
for(int i=0;i<N-20;i++){
bi = bi.multiply(new BigInteger("2"));
}
String ans = bi.toString();
System.out.println(ans.substring(0,ans.length()-1) + (Integer.parseInt(ans.substring(ans.length()-1))-1));
}
// 2^100을 출력 위해 BigIneger 사용.
// string에서 1을 빼주기 위해. 맨 뒷자리 따로 출력.
baby-gin
정렬 후.
list에 넣으면서 triple 확인.
list 돌면서 run 확인. ?
-----
완전검색, Exhaustive Search
완전 검색 방법은 모든 경우의 수를 나열해보고 확인
Brute-force -> 컴퓨터의 force
상대적으로 빠른 시간에 문제 해결(알고리즘 설계) 할 수 있음.
우선 크기를 계산해보고 해 볼 만하면 try 후,
성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직.
n! -> 수행시간 하늘로 승천.. 10!->360만, 11!->4000만
1억 연산 -> 대략 1초.
I/O, 객체생성 소멸까지 생각하면..순열
순열, permutation
서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
'nPr'
nPr = n*(n-1)*(n-2) * ... * (n-r+1)
nPn = n! -> factorial
다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련 있다.
ex) TSP, traveling Salesman Problem
-----
반복문으로 순열
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(j!=i){
for(int k=0;k<3;k++){
if(k!=i && k!=j){
// i, j, k 출력.
}
}
}
}
}
// 기존 뽑힌 수 중복체크.
// 중복되지 않은 수 선택.
// 뽑는 개수가 달라지면 반복문으로 짜기 어렵..
-----
재귀로 순열.
perm(idx) // idx : 현재까지 뽑은 순열 수의 개수
numbers[] : 순열 저장 배열
isSelected[] : 인덱스의 해당하는 숫자가 사용 중인지 저장하는 배열
if(idx ==3)
//출력 후 리턴.
else{
for(int i=1;i<=3;i++){
if(isSelected[i] == true) // 배열에 접근은 상수 1 시간복잡도.
continue;
numbers[idx] = i;
isSelected[i] = true;
perm(idx+1)
isSelected[i] = false;
}
}
알고리즘 풀이
백준 N과 M 시리즈 (2) ~ (12) 풀이.
- 중복허용 - isUsed() 체크 부분 주석처리.
- 오름차순 -> 새로 넣은 값이 이전 값보다 작으면 종료.
- 입력받아서 오름차순 -> 입력 받은 값 정렬 후 돌리기.
- 중복 수 입력 시 배열하나 더 만들어서 몇 번 썼는 지 check.
-----
Bj 17478번 - 재귀함수가 뭔가요?
- 하셨지 -> 하였지.
- 첫 부분. 공통된 부분. 마지막 부분.
-----
SWEA 1208번 - Flatten, 평탄화
- min, max, minIdx, maxIdx 설정 확인.
- 이게 재귀..?
-----
SWEA 1210번 - Ladder1, 사다리타기
- 밑에서 부터 거꾸로.
- 재귀로. row, col, direction 전달.
-----
'과제' lab.ssafy.com 에 올리기.
Bj 1244번 - 스위치 켜고 끄기.
남학생은 받은 수의 배수 바꿈.
여학생은 받은 수 기준 대칭으로 숫자가 같은 곳까지 자기 포함 전S부 바꿈.
-----
'해볼까?'
SWEA 2805번 - 농작물 수확하기
-----
알고리즘 - 자료구조 - 스택, 큐, 덱
스택, Stack
- 쌓다. 더미의 의미를 지니며 물건을 쌓아 올리듯 데이터를 쌓는 자료구조.
- 특징
- 후입 선출. LIFO
- 그래프의 깊이 우선 탐색(DFS)에서 사용
- 재귀적 함수를 호출할 때 사용
- 인터럽트 처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 사용된다.
import java.util.Stack; // import
Stack<타입> stack = new Stack<>();
stack.push(요소);
stack.pop(요소);
stack.clear();
stack.peek(); // 스택의 가장 상단 값 출력
stack.size();
stack.empty();
stack.contains(요소); // 리턴 값 boolean
-----
큐, queue
- 선입선출, FIFO
- 큐의 한 쪽 끝은 front로 정하고 삭제 연산만 수행
- 다른 한 쪽 끝은 rear로 정하고 삽입 연산만 수행
- 그래프의 너비우선탐색(BFS)에서 사용
import java.util.Queue;
Queue<Type> queue = new LinkedList<>();
queue.add(요소);
queue.offer(요소); // 요소 추가, 실패 시 IllegalStateException 발생
queue.remove(); // queue의 첫번째 값을 제거
queue.poll(); // queue의 첫번째 값을 반환 및 제거(비어있음 null 반환)
queue.clear();
queue.peek(); // queue의 첫 번째 값 참조
-----
덱, deque
- double-ended queue의 줄임말.
- 데이터를 양방향으로 넣고 뺄 수 있다.
- 어느 쪽으로 입출력 받느냐에 따라 스택, 큐 등으로 활용가능
Deque<타입> deque = new ArrayDeque<>(); // 덱 선언, ArrayDeque 사용(주로 사용)
Deque<타입> deque = new LinkedList<>(); // 덱 선언, LinkedList 사용
deque.addFirst(요소); // 덱의 앞에 데이터 삽입, 용량 초과시 예외 발생
deque.offerFirst(요소) // 덱의 앞에 데이터 삽입(리턴값 : boolean)
deque.addLast(요소); // 덱의 뒷쪽에 데이터 삽입, 용량 초과시 예외 발생
deque.offerLast(요소); // 덱의 뒷쪽에 데이터 삽입(리턴값 : boolean)
deque.removeFirst(); // 덱의 앞에서 반환 및 제거, 비어있으면 예외 발생
deque.pollFirst(); // 덱의 앞에서 반환 및 제거, 비어있으면 null 리턴
deque.removeLast(); // 덱의 뒤에서 반환 및 제거, 비어있어면 예외 발생
deque.pollLast(); // 덱의 뒤에서 반환 및 제거, 비어있으면 null 리턴
deque.removeFirstOccurrence(요소); // 덱의 앞에서 요소를 찾아 삭제
deque.removeLastOccurence(요소); // 덱의 뒤에서 요소를 찾아 삭제
deque.getFirst(); // 첫 번째 엘리먼트를 확인, 비어있으면 예외
deque.peekFirst(); // 첫 번째 엘리먼트를 확인, 비어있으면 null 리턴
deque.peek();// peekFirst()와 동일
deque.getLast(); // 마지막 요소를 확인, 비어있으면 예외
deque.peekLast();// 마지막 요소를 확인, 비어있으면 null 리턴
deque.contain(요소); // 요소가 포함되어 있는지 확인
deque.size(); // Deque에 들어있는 엘리먼트의 개수
바르고의 다락방