22년 11월 26일_단단한 나, 이것이 코딩테스트다, 프로그래머스 0lv

목요일[내일 어떡하지]

 

1. 이것이

2. 프로그래머스 

3. git

 

1>

오버플로 : 특정한 자료구조가 수용할 수 있는 데이터 의 크기를 이미 가득 찬 상태에서 삽입연산을 수행할 경우 발생

언더플로 : 특정한 자료구조에 데이터가 전혀 들어 있지 않은상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태

 

스택 - 선입 후출 (박스쌓기에 비유)

(+pop()은 가장 뒤쪽에서 데이터를 꺼내옴)

 

큐 - 선입 선출 (대기줄에 비유)

구현을 위해 라이브러리 import

from collections import deque

queue = deque()

(+popleft()사용)

queue.reverse() 역순으로 바꿈

 

--재귀함수 

자기 자신을 다시 호출하는 함수

재귀함수는 return을 만나면 종료된다.

 

재귀함수는 스택 자료구조를 이용한다.

 

팩토리얼 예제

def factorial_iterative(n):
	result =1
    for i in range(1, n+1):
    	result += i
    return result
# 재귀적으로 구현
def factorial_recusiven(n):
	if n <= 1:
    	return 1
    return n* factorial(n-1)

 

재귀함수의 n * factorial(n-1)의 경우는 

n! = n * (n-1)를 코드 그대로 작성

 

토픽>

꿀팁

문제를 잘 못들었을 경우 조금 기다렸다가 [part 4의 경우]

다른 사람이 대답하는 걸 듣고 umm actually 로 시작

 

--탐색 알고리즘 DFS/BFS

 

DFS((Depth-First Search)

깊이 우선 탐색

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 

 

그래프는 노드와 간선으로 표현되며 노드의 정점이라고도 말한다.

 

그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말함

 

인접행렬 2차원 배열로 그래프의 연결관계를 표현하는 방식

인접리스트 리스트로 그래프의 연결 관계를 표현하는 방식

 

# 인접 리스트 방식 예제
 
 fraph =[[] for _ in range(3)]
 
 # 노드 0에 연결된 노드 정보 저장(노드, 거리)
 graph[0].append((1,7))
 graph[0].append((2,5))
 
 # 노드 1에 연결된 노드 정보 저장(노드, 거리)
 graph[1].append((0,7))
 
 # 노드 2에 연결된 노드 정보 저장(노드, 거리)
 graph[2].append((0,5))
 
 print(graph)

// [[(1,7),(2,5)],[(0,7)],[(0,5)]]

 

인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어있느지 에 대한 정보를 얻는속도가 느리다.인접 리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문이다.

또 다른 예시로 한 그래프에서 노드 1과 노드7이 연결되어 있는 상화을 생각해보자. 인접 행렬 방식에서는 graph[1]7]만확인하면된다. 반면에 인접리스트 방식에서는 노드 1에대한 인접 리스트를 앞에서 부터 확인해야 한다.

 

 

 

2>

문자열안에 문자열

def solution(str1, str2):
    answer = 0
    if str2 in str1:
        return 1
    else :
        return 2

자릿수 더하기

def solution(n):
    answer = 0
    a = list(str(n))
    
    for i in a:
        i = int(i)
        answer += i
    
    return answer

 

순서쌍의 개수

def solution(n):
    answer = 0
    for i in range(n+1):
        for j in range(n+1):
            if i*j == n:
                answer += 1
    return answer

def solution(n):
    answer = 0
    for i in range(2, n+1):
        if n % i == 0 :
            answer += 1
    return answer+1

3>

 

`Bubble Sort`, `Selection Sort`, `Insertion Sort`, `Merge Sort`, `Heap Sort`, `Quick Sort` 를 소개한다.
### Bubble Sort
n 개의 원소를 가진 배열을 정렬할 때, In-place sort 로 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다. 가장 큰 값을 배열의 맨 끝에다 이동시키면서 정렬하고자 하는 원소의 개수 만큼을 두 번 반복하게 된다.
| Space Complexity | Time Complexity |
| :--------------: | :-------------: |
|       O(1)       |     O(n^2)      |
#### [code](https://github.com/JaeYeopHan/algorithm_basic_java/blob/master/src/test/java/sort/BubbleSort.java)
</br>
### Selection Sort
n 개의 원소를 가진 배열을 정렬할 때, 계속해서 바꾸는 것이 아니라 비교하고 있는 값의 index 를 저장해둔다. 그리고 최종적으로 한 번만 바꿔준다. 하지만 여러 번 비교를 하는 것은 마찬가지이다.
| Space Complexity | Time Complexity |
| :--------------: | :-------------: |
|       O(1)       |     O(n^2)      |
#### [code](https://github.com/JaeYeopHan/algorithm_basic_java/blob/master/src/test/java/sort/SelectionSort.java)
</br>
### Insertion Sort
n 개의 원소를 가진 배열을 정렬할 때, i 번째를 정렬할 순서라고 가정하면, 0 부터 i-1 까지의 원소들은 정렬되어있다는 가정하에, i 번째 원소와 i-1 번째 원소부터 0 번째 원소까지 비교하면서 i 번째 원소가 비교하는 원소보다 클 경우 서로의 위치를 바꾸고, 작을 경우 위치를 바꾸지 않고 다음 순서의 원소와 비교하면서 정렬해준다. 이 과정을 정렬하려는 배열의 마지막 원소까지 반복해준다.
| Space Complexity | Time Complexity |
| :--------------: | :-------------: |
|       O(1)       |     O(n^2)      |
#### [code](https://github.com/JaeYeopHan/algorithm_basic_java/blob/master/src/test/java/sort/InsertionSort.java)
</br>
### Merge Sort
기본적인 개념으로는 n 개의 원소를 가진 배열을 정렬할 때, 정렬하고자 하는 배열의 크기를 작은 단위로 나누어 정렬하고자 하는 배열의 크기를 줄이는 원리를 사용한다. `Divide and conquer`라는, "분할하여 정복한다"의 원리인 것이다. 말 그대로 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하는 방법이다. 단 분할(divide)해서 정복했으니 정복(conquer)한 후에는 **결합(combine)** 의 과정을 거쳐야 한다.
`Merge Sort`는 더이상 나누어지지 않을 때 까지 **반 씩(1/2)** 분할하다가 더 이상 나누어지지 않은 경우(원소가 하나인 배열일 때)에는 자기 자신, 즉 원소 하나를 반환한다. 원소가 하나인 경우에는 정렬할 필요가 없기 때문이다. 이 때 반환한 값끼리 **`combine`될 때, 비교가 이뤄지며,** 비교 결과를 기반으로 정렬되어 **임시 배열에 저장된다.** 그리고 이 임시 배열에 저장된 순서를 합쳐진 값으로 반환한다. 실제 정렬은 나눈 것을 병합하는 과정에서 이뤄지는 것이다.
결국 하나씩 남을 때까지 분할하는 것이면, 바로 하나씩 분할해버리면 되지 않을까? 재귀적으로 정렬하는 원리인 것이다. 재귀적 구현을 위해 1/2 씩 분할한다.
| Space Complexity | Time Complexity |
| :--------------: | :-------------: |
|       O(n)       |    O(nlogn)     |
</br>
### Heap Sort
`binary heap` 자료구조를 활용할 Sorting 방법에는 두 가지 방법이 존재한다. 하나는 정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 원리로 Sorting 을 하게 되는 방법이고, 나머지 하나는 기존의 배열을 `heapify`(heap 으로 만들어주는 과정)을 거쳐 꺼내는 원리로 정렬하는 방법이다. `heap`에 데이터를 저장하는 시간 복잡도는 `O(log n)`이고, 삭제 시간 복잡도 또한 `O(log n)`이 된다. 때문에 힙 자료구조를 사용하여 Sorting 을 하는데 time complexity 는 `O(log n)`이 된다. 이 정렬을 하려는 대상이 n 개라면 time complexity 는 `O(nlogn)`이 된다.
`Heap`자료구조에 대한 설명은 [DataStructure - Binary Heap](https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#binary-heap)부분을 참고하면 된다.
| Space Complexity | Time Complexity |
| :--------------: | :-------------: |
|       O(1)       |    O(nlogn)     |
</br>
### Quick Sort
Sorting 기법 중 가장 빠르다고 해서 quick 이라는 이름이 붙여졌다. **하지만 Worst Case 에서는 시간복잡도가 O(n^2)가 나올 수도 있다.** 하지만 `constant factor`가 작아서 속도가 빠르다.
`Quick Sort` 역시 `Divide and Conquer` 전략을 사용하여 Sorting 이 이루어진다. Divide 과정에서 `pivot`이라는 개념이 사용된다. 입력된 배열에 대해 오름차순으로 정렬한다고 하면 이 pivot 을 기준으로 좌측은 pivot 으로 설정된 값보다 작은 값이 위치하고, 우측은 큰 값이 위치하도록 `partition`된다. 이렇게 나뉜 좌, 우측 각각의 배열을 다시 재귀적으로 Quick Sort 를 시키면 또 partition 과정이 적용된다.이 때 한 가지 주의할 점은 partition 과정에서 pivot 으로 설정된 값은 다음 재귀과정에 포함시키지 않아야 한다. 이미 partition 과정에서 정렬된 자신의 위치를 찾았기 때문이다.
#### Quick Sort's worst case
그렇다면 어떤 경우가 Worst Case 일까? Quick Sort 로 오름차순 정렬을 한다고 하자. 그렇다면 Worst Case 는 partition 과정에서 pivot value 가 항상 배열 내에서 가장 작은 값 또는 가장 큰 값으로 설정되었을 때이다. 매 partition 마다 `unbalanced partition`이 이뤄지고 이렇게 partition 이 되면 비교 횟수는 원소 n 개에 대해서 n 번, (n-1)번, (n-2)번 … 이 되므로 시간 복잡도는 **O(n^2)** 이 된다.
#### Balanced-partitioning
자연스럽게 Best-Case 는 두 개의 sub-problems 의 크기가 동일한 경우가 된다. 즉 partition 과정에서 반반씩 나뉘게 되는 경우인 것이다. 그렇다면 Partition 과정에서 pivot 을 어떻게 정할 것인가가 중요해진다. 어떻게 정하면 정확히 반반의 partition 이 아니더라도 balanced-partitioning 즉, 균형 잡힌 분할을 할 수 있을까? 배열의 맨 뒤 또는 맨 앞에 있는 원소로 설정하는가? Random 으로 설정하는 것은 어떨까? 특정 위치의 원소를 pivot 으로 설정하지 않고 배열 내의 원소 중 임의의 원소를 pivot 으로 설정하면 입력에 관계없이 일정한 수준의 성능을 얻을 수 있다. 또 악의적인 입력에 대해 성능 저하를 막을 수 있다.

출처 : https://github.com/JaeYeopHan/Interview_Question_for_Beginner/commit/bb9676bbb704af8059d4de41ab6d42681174be3b

Divide and Conquer 관련 내용 추가. DP, DnC, Greedy 특징별 비교 내용 추가 (#178) · JaeYeopHan/Interview_Question_

 

컨디션이 좋지 못하다..

 

// yesterday wished to today list.

. 물어보기(잡기)_✔️

. 토스 강의 듣기_https://www.hackers.co.kr/?c=s_lec/lec_speak/lec_Speaking_OPIc_movies&keywd=haceng_submain_lnb_lec_Speaking_OPIc_movies&logger_kw=haceng_submain_lnb_lec_Speaking_OPIc_movies#;_✔️

. 이것이 진도 나가기_✔️

. 프로그래머스 풀기 (알고리즘)_✔️

. https://github.com/JaeYeopHan/Interview_Question_for_Beginner  읽기

 

tomorrow wish list

. 토스 강의 듣기_https://class.champstudy.com/HLec/hcms_lecture.php

. 프로그래머스 풀기 (알고리즘)