수원에 있는 대학 병원에 11시 30분 예약이라 새벽 6시부터 일어나서 출석을 찍고 공부를 했다. 물론 내일 배움 캠프 과정 공부를 한 건 아니고 내일배움카드 과정 중에 앱개발이라는 과정의 2주차 숙제를 전 날 일찍 잔다고 못 해서 병원에 갈 준비를 하기 전까지 그걸 붙잡고 있었다. expo go 앱에 무슨 문제인지 또 화면이 안 뜨고 튕기는 버그가 떠서 만든걸 확인도 못하고 병원에 가야하긴 했지만...
사실은 정신 없는 하루였다. 병원에 도착한 건 차가 생각보다 안 막혀서 10시 조금 넘어 도착했는데 분명 예약하고 갔는데 어떻게 된게 밀리고 밀려서 12시가 넘어서야 진료를 볼 수 있었다. 물론 그 시간 동안 테블렛으로 강의 마지막 주차 숙제를 손으로 코딩했지만 집에 와서 보니 한 문제 빼고 다 이상하게 풀었더라...
공가로 진단서를 작성해야할지도 모르겠다 싶었는데 다행히 시간내에 집에 도착해서 출석 시간은 제 때 채웠지만 너무 일찍 일어난 여파인지 나도 모르게 잠이 들어 계획한 곳까지 공부는 하지 못했다고 한다. 안 그래도 이해 안 되는 알고리즘인데 공부시간이 확 줄어든 느낌...
역시나 TIL인데 다음날 작성 중이다.
어제 저녁에는 BFS & DFS 강의를 보다가 원리는 이해 되는게 코딩이 왜 저렇게 되지 이해가 되지 않아 내가 개발자가 되어야겠다 생각을 하게 해준 현업 개발자로 있는 친구에게 물어봐서 중간에 디코를 했다. 혼자 이해하려 할 때는 눈에 안 들어와서 이해가 되지 않았는데 디코를 하니까 그냥 눈에 들어오더라. 나는 왜 꼭 누군가에게 물어보고 혼자 이해를 하는 걸까... 순간 미안해졌다.
딕셔너리 구조가 낯선 모양인지 딕셔너리만 들어가면 이런 것 같아 좀 더 익숙해져야겠다는 생각도 들었다.
알고리즘
정렬
데이터를 순서대로 나열하는 방법으로 알고리즘의 굉장한 주제
버블정렬
첫 번째를 두번째와 두번째를 세번째와 비교하는 식으로 끝까지 한 바퀴를 돌면 맨 뒤에 가장 큰 수 혹은 가장 작은 수가 들어간다. 그러면 다음에는 그 정렬된 뒷부분을 제외하고 한 바퀴를 도는 걸 반복
선택정렬
전체를 탐색해 가장 큰 값 혹은 가장 작은 값을 찾은 후 맨 앞의 값과 자리를 바꾼다. 그 다음은 정렬이 된 앞을 제외하고 같은 과정 반복
삽입정렬
순서대로 정렬을 해준다. 첫번째는 홀로 정렬이 되어 있으므로 끝이고 두 번째는 첫 번째와 비교하려 정렬을 해준다. 그 다음 세번째 역시 두번째와 비교하여 정렬하고 만약 두 번째의 자리로 이동을 하면 첫 번째와 다시 비교하여 정렬한다. 이동하지 않는다면 그 상태로 정렬된 것이다.
병합정렬
- merge
두 배열을 정렬하면서 합치는 방식- mergesort
가장 작은 문제로 분리한 후 각각 정렬하면서 합치기
자료구조
스택
Last In First Out의 형태를 지닌 자료구조로 가장 마지막에 넣은 값을 가장 먼저 꺼냄
넣은 순서를 쌓아두고 있기 때문에 진적에 했던 행동을 되돌리고 싶을 때 사용하는 기능큐
First In First Out의 형태를 지닌 자료구조로 가장 먼저 넣은 값을 가장 먼저 꺼냄
순서대로 처리해야하는 일들을 저장하고 싶을 때 사용하는 기능해쉬
컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료구조
데이터의 검색과 저장이 아주 빠르게 진행
- 해쉬 테이블(hash Table)
'키' 와 '데이터' 를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조로 딕셔너리를 해쉬 테이블리라 부르기도 한다.- 해쉬 함수(Hash Function)
임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬 값을 출력하는 함수트리
계층형 비선형 자료 구조로 표현에 초점이 맞춰져있다.
힙
데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리로 항상 가장 큰 값이나 작은 값이 최상위 레벨에 있고 그보다 작거나 큰 값이 하위 레벨에 있어야 하는 자료구조
- Max Heap
최댓값이 맨 위인 힙- Min Heap
최솟값이 맨 위인 힙그래프
연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조로 연결관계에 초점이 맞춰져 있다. 유방향그래프와 무방향그래프가 있으며 유방향 그래프에서는 방향도 중요하다.
표기는 2차원 배열, 인접리스트, 딕셔너리로 가능하며 배열과 인접리스트 & 딕셔너리 표기의 차이는 공간을 많이 쓰느냐 시간을 많이 쓰느냐의 차이이다.DFS
한 노드를 시작으로 인접한 다른 노드의 하위 레벨을 끝까지 타고 탐색하면 다시 위로 올라와 다음을 탐색하여 검색하는 방식, 재귀함수나 스택을 사용하지만 재귀함수의 경우 레벨이 많아지면 에러가 발생할 수 있어 스택을 사용하는 것이 좋다.
인접한 노드 중 방문하지 않은 모든 노드들을 저장 후 마지막에 넣은 노드들만 꺼내서 탐색 1. 루트 노드를 스택에 넣는다. 2. 현재 스택에 노드를 빼서 visited(방문했다는 기록을 위해)에 넣는다. 3. 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 추가한다. 4. 2부터 반복 5. 스택이 비면 탐색을 종료BFS
한 노드를 시작으로 인접한 모든 노드들을 우선 방문하는 방법으로 방문하지 않은 정점이 없을 때까지 탐색, 가장 처음 방문한 노드를 꺼내서 탐색하는 방식이기 때문에 큐를 사용한다.
인접한 노드 중 방문하지 않은 모든 노드들을 저장 후 가장 먼저 넣은 노드를 꺼내서 탐색 1. 루트 노드를 큐에 넣는다. 2. 현재 큐의 노를 빼서 visited에 추가한다. 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않는 노드를 큐에 추가한다. 4. 2부터 반복한다. 5. 큐가 비면 탐색을 종료한다.
Dynamic Programming(동적 계획법)
복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방법, 부분문제 반복과 최적 부분 구조를 갖고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 반복한다.
재귀함수와 같이 같은 답이 나오는 문제를 반복하는 경우 동적계획법을 사용하여 그 결과를 기록해놓고 필요하면 꺼내와 사용한다.
- 메모이제이션(Memoization)
결과를 기록- 겹치는 부분 문제(Overlapping Subproblem)
문제를 쪼갤 수 있는 구조
겹치는 부분문제가 있다면 메모이제이션을 사용하면 된다고 생각하면 됨
위의 내용 중에 특히 자료구조는 어떨 때 쓰이는지 어떤식인지는 이해했지만 정작 써보라 하면 기억이 나지 않는 아이들이라 주의가 필요할 듯 하다. 반복학습이 중요한 듯 한데 이미 코딩되어있는 걸 봐도 돌아가는 구조가 헷갈리니 조금 답답하기도 하다.
