Algorithm

2.3 FLOORS AND CEILINGS

2.3 FLOORS AND CEILINGS Suppose x ∈ IR+.The floor of x, denoted x , is defined to be the largest integer that is no larger than x.The ceiling of x, denoted x, is defined to be the smallest integer that is no smaller than x. 24 Prove by induction on $n \geq 0$ that $$\left \lfloor \frac{n}{2} \right \rfloor = \begin{cases}n/2 &\text{if n is even} \\(n-1)/2 & \text{if n is odd}\end{cases}$$ 24-1. ..

2.2 INEQUALITIES

2.2 INEQUALITIES 18 Prove by induction on $n \geq 1$ that if $x > -1$, then $(1+x)^n \geq 1 + nx$ 18-1. Basis Condition n = 1일 때 성립하는가? $$ \begin{aligned} (1+x)^1 &\geq 1 + 1x \\ &\geq 1 + x \\ \end{aligned} $$ 이므로 성립한다. 18-2. Induction (귀납 가정) n = k일 때 성립한다고 가정하자. $$ \begin{aligned} (1+x)^k \geq 1 + kx \end{aligned} $$ 가 성립한다고 하자. 18-3. Induction Proof (가정을 이용한 증명) n = k + 1일 때를 증명해보자 $$ \begin..

2.1 SUMMATIONS

2.1 SUMMATIONS 1. Prove by induction on $n >= 0$ that $$\sum_{i=1}^n i = n(n+1)/2$$ 1-1. Basis Condition n = 1일 때 성립하는가? $$\sum_{i=1}^1 i = 1(1+1)/2 = 1$$ 이므로 성립한다. 1-2. Induction (귀납 가정) n = k일 때 성립한다고 가정하자. $$\sum_{i=1}^k i = k(k+1)/2$$ 가 성립한다고 하자. 1-3. Induction Proof (가정을 이용한 증명) n = k + 1일 때를 증명해보자 $$\sum_{i=1}^{k+1} i = (k+1)(k+2)/2$$ 가 성립함을 증명해야 한다. 이는 1~k 까지의 합 + (k+1) 이므로.. $$(k+1) + \s..

[Java] 다익스트라(Dijkstra) 알고리즘

개요 다익스트라 알고리즘은 최단경로를 찾기 위한 알고리즘이다. 주의할 점은 음수 가중치를 갖는 간선을 가지면 안된다. 음수가 되는 사이클을 돌면 가중치가 음의 무한까지 발산하기 때문 설명 인접 노드라고 해서 최단경로가 아니라는 점에 주목하자. 위와 같은 형태의 그래프에서 0->3 까지 바로 갈 수 있지만, 0->1->2->3 경로로 가는 거리가 가장 짧기 때문에 최단경로는 후자가 된다. 다익스트라 알고리즘은 경로를 기준으로 하는 우선순위 큐를 이용한다. 우선순위 큐에는 정점의 번호와 지금까지 찾은 해당 정점까지의 최단거리를 쌍으로 갖는다. 최단거리 쌍(시작점으로 부터거리, 정점의 번호) 각 정점까지 최단거리를 저장하는 배열 dist[]를 정의한다. 해당 정점으로 부터 갈 수 있는 모든 노드를 검사한다. ..

8/12 (목) 자바 코딩 스터디

2618 경찰차9251 LCS10164 격자상의 경로2839 설탕 배달1010 다리 놓기 1010번 다리 놓기 강 서쪽에서 동쪽으로 다리를 잇는 프로그램 다리끼리는 서로 겹쳐질 수 없다. 결국에는 강 동쪽의 구역(M) 중 강 서쪽의 구역(N)만큼을 순서 상관 없이 뽑는 경우의 수 를 출력하는 프로그램이다. 첫 번째는 간단 수학식으로 해결해 보았다. 1. 다이나믹 프로그래밍 C(3, 2) = c(2, 1) + c(2, 2) = C(1, 0)+C(1, 1) + C(1, 1)+C(1, 2) C(M, N) = C(M-1, N-1) + C(M-1, N) nCr = n-1Cn-1 + n-1Cn; public static int buildBridge2(int n, int r) { if (n == r) { return..

8/5 (목) 자바 코딩 스터디

1259 팰린드롬수 1476 날짜 계산 2108 통계학 1138 한 줄로 서기 16236 아기 상어 1259 팰린드롬수 같으면 yes 틀리면 no 출력 1. 양 끝을 검사. 절반만 비교하기. 다르면 반복문 종료 no 출력 반복문이 끝나면 yes 출력 2. StringBuffer reverse() 이용 뒤집은 문자열과 같은 지 체크 1476 날짜 계산 if E, S, M 각 날짜가 넘어가면 1로 바꿔주기 or -1 한 값을 나머지 연산 취하기 3. hashMap 쉽게 갱신하기? 4. 빈자리 리스트 만들기 0 1 2 3 2 1 1 0 입력일 때 2 지우기 0 1 3 1138 한 줄로 서기 Entry treemap.entrySet() => key,map 을 동시에 볼 수 있는 방법? getKey(); getV..

7/29(목) 자바 코딩 스터디

https://github.com/qpdh/JavaCodingTestStudy 1977 완전제곱수 1475 방 번호 1292 쉽게 푸는 문제 13460 구슬 탈출 2 2573 빙산

7/22 (목) 자바 코딩 스터디

5576 콘테스트 1026 보물 2822 점수 계산 2693 N번째 큰 수 1181 단어 정렬 2437 저울 int 형 Array.sort(coll ~ 안되 ㅁIntegers ArrayList 오름차순 정렬 Collections.sort(); Collections.sort(arrayList,Collections.reverseOder()); Array.sort(); 객체의 정렬? Comparator 입출력을 한 번에 할 필요가 없음 return -1? 1? 1이면 o1 이 뒤로 감 o2 가 앞으로 감 -1 o1 다음으로 o2가 감 1 o2 다음으로 o1이 감 Set.toArray() -> Set을 배열로 만듦 String[] word = new Strig[set.size()]; set.toArray(wor..

7/8(목) 자바 코딩 스터디

문자열 https://github.com/qpdh/JavaCodingTestStudy https://www.acmicpc.net/problem/9086 https://www.acmicpc.net/problem/7567 https://www.acmicpc.net/problem/7785 https://www.acmicpc.net/problem/5052 https://www.acmicpc.net/problem/3033 빠른 입출력 static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.o..

3. 연결리스트

개요 장점 논리적인 순서와 물리적인 순서가 일치하지 않아도 됨 크기를 유연하게 변경 가능 메모리를 좀 더 효율적으로 사용 가능 용어 노드들의 연결된 집합으로 표현 노드 : 단위로 구성 데이터 필드 : 원소 링크필드 : 주소 노드가 하나도 없는 공백 연결 리스트는 포인터 변수에 NULL 저장 삽입연산 삽입할 노드를 준비한다. 새 노드의 데이터 필드에 값을 저장한다. 새 노드의 링크값을 지정한다. 리스트의 앞 노드에 새 노드를 연결한다. 0. 연결리스트 구조체 생성 // 정수형 data를 갖는 노드 구조체 생성 typedef struct LinkedList{ int data; struct LinkedList * link; }LinkedList;1. 리스트 처음 노드로 삽입하는 알고리즘 // 리스트 처음 노드..