Dynamic Programming, Recursive Function, BFS, DFS : 12/2(목) ~ 12/5(일)

12/2(목) ~ 12/5(일) 동안의 기록

혼자서 문제푼 것 + 코테 강의 들어본 것

1. 

배열정렬 

https://coding-factory.tistory.com/549

내림차순 Collections.reverseOrder()

int 배열을 Integer 배열로

https://zetawiki.com/wiki/%EC%9E%90%EB%B0%94_int_%EB%B0%B0%EC%97%B4%EC%9D%84_Integer_%EB%B0%B0%EC%97%B4%EB%A1%9C_%EB%B3%80%ED%99%98

Integer b[] = Arrays.stream(a).boxed().toArray(Integer[]::new);

 

2. 

정수 평균 구할 때, double 형으로 계산

-> 정수 계산이 가능하도록 변환하여 푼다. 

Math.abs() 절댓값 구하기 

 

3. 

선택 정렬

1. 주어진 범위에서 최소 값의 위치 찾기

2. 최소 값을 해당 범위의 가장 앞 숫자와 자리 바꾸기

3. 이후, 나머지 범위에 대해 위의 과정 반복

 

선택 정렬로 배열 정렬하기

 

4. 

printf

%.1f 의 형식으로 소수점 자리수를 지정

 

12/4 (토)

재귀함수 & 동적 프로그래밍(Dynamic Programming)

재귀함수 참고강의 (해당 파트 다 들음)

https://www.youtube.com/watch?v=JyaK14AhGm4&list=PLVoihNyHW4xkm_KJ8_N8X7F6EQP4uSRyR&index=32 

동적프로그래밍 참고강의 (해당 파트 다 들음)

https://www.youtube.com/watch?v=FmXZG7D8nS4&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=21 

 

Dynamic Programming : 큰 문제를 작은 문제로 나누어 풀어서 큰 문제를 해결

하나의 문제를 단 한번만 푼다.

분할정복(Divide and Conquer)과 동적 프로그래밍의 차이점) DP는 작은 부분 문제의 답이 항상 같음

Top Down VS Bottom Up

memoization (Top Down)

DP 문제는 문제 내에서 규칙성을 찾아서 점화식을 세우는 것이 중요하다.

https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182

1. 

피보나치 수

수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다. 

(위키백과 검색)

 

2. 

점화식 DP

 

3.

전에 못풀었던 문제 다시 시도해봄.

Arrays.sort() comparator

https://cwondev.tistory.com/15

https://hannamnote.tistory.com/82

 

substring(startIndex, endIndex)

문자열에서 [기준값.compareTo(비교대상)]

compare VS compareTo

https://lookingfor.tistory.com/entry/%EC%9E%90%EB%B0%94-%EB%AC%B8%EC%9E%90%EC%97%B4-%EB%B9%84%EA%B5%90-%ED%95%A8%EC%88%98-compare-compareTo

 

4. 

H인덱스 구하는 법

연구자의 전체 논문을 피인용 순으로 정렬한 후 : 내림차순 정렬

논문의 순번과 피인용 횟수를 비교하여

피인용 횟수가 논문의 순번보다 작아지기 시작하는 직전의 순번이 연구자의 h인덱스

: 반복문 돌려서 citation[i] <= i 일 때, return i (반복문 index가 0부터 시작할 경우)

https://khuelibrary.tistory.com/107

https://en.wikipedia.org/wiki/H-index

h-index - Wikipedia

위키백과 보는게 정확 

i 는 N 의 원소 따라서 논문 수보다 각 논문 인용 수가 더 많을 경우 전체 논문 수 return

인덱스 번호와 인용 수가 같을 때 현재 인덱스 번호 return

 

이분탐색

원하는 탐색 범위를 두 부분으로 분할해서 찾는 방식

정렬되어있어야함.

 

-> 오늘은 재귀함수와 동적 프로그래밍 강의를 듣고 이것저것(딱히 동적 프로그래밍 문제는 아님) 문제풀어봄. 내일은 스택/큐 강의 듣고 관련 문제를 풀어볼 예정

 

코몬 강의 1,2강은 들었다. 거기까지는 모든 문제에 대해 문제풀이 강의가 있어서 좋았는데, 이후는 없어서 강의자료보고 알아서 공부해야됨. 그래서 일단 나중에 할 예정 

 

일요일에 못해서 월요일 아침에 합니다

큐, 스택 (이미 알고 있으니 설명 생략)

BFS(Breath First Search, 넓이 우선 탐색) : 큐 활용

DFS(Depth First Search, 깊이 우선 탐색) : 스택 활용, 재귀함수 이용할 수도 있다

재귀함수 자체가 컴퓨터의 내부 구조인 스택 프레임에 차곡차곡 쌓이는 형태

dfs & bfs 문제풀이 강의를 볼 예정 

https://www.youtube.com/watch?v=7C9RgOcvkvo