패스트 캠퍼스 한번에 끝내는 코딩 테스트 369 Java 편 초격차 패키지 최종 후기
드디어 패스트캠퍼스와의 50일간의 대장정? 의 일주를 마치고 최종 후기를 쓰게 되었다.
이 챌린지를 시작하기 전에 마침 코딩테스트를 대비해서 공부 및 강의를 알아보던 도중에 해당 챌린지가 진행되어
뒤도 보지않고 바로 신청서를 작성하여 챌린지를 진행한거 같다 ㅋㅋㅋㅋ
해당 강의를 통해서 완전한 알고리즘 마스터라는 거대한 목표를 가지고 시작하지 않았기 때문에서 그런지
큰 부담없이 강의를 들으면서 자료구조와 알고리즘이라는 개념에 대해서 알아보고 이해할 수 있는 계기가 되었던거 같다
또한 하루하루 공부를해가며 꾸준함을 얻게된 좋은 계기라고 생각한다 물론 돈이 걸렸기에 더 열정적이였을지도 모르겠다 ㅎㅎ
해당 강의를 통해 얻은 지식들을 한번 최종 후기에 펼쳐 보겠다
Part 1 자료구조 이론
- 해당 파트에서 알고리즘을 풀기 위한 자료구조의 개념을 이해하고 풀이에 적용하는 자료구조 이론을 학습 하였다.
처음에 오리엔테이션 및 수업 준비 영상을 통하여 자료구조 이론에 대하여 기본 설명 및 환경 준비를 설명해준 후
자료구조 형태들을 하나하나 설명 및 예시를 통한 풀이를 알려주었다
해당 파트에서 배열, 큐 , 스택, 링크드리스트, 해쉬, 트리, 힙 등의 자료구조를 이해하고 사용할 수 있게 되었으며
해당 자료구조들을 사용하여 알고리즘의 복잡도를 확인할 수 있는 파트였다.
해당 파트 자료 요약
1. 배열 (Array) : 같은 유형의 데이터를 여러개 넣어 관리하는 데이터구조
2. 큐 (Queue) : 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조 (FIFO)
3. 스택 (Stack) : 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터구조 (LIFO)
4. 링크드 리스트 (Linked List)
- 데이터와 다음 데이터의 주소를 저장하는 공간을 같이 저장하여 중간 데이터 삽입,삭제 시 데이터를 찾아갈 수 있다.
- 데이터 저장 단위인 Node와 이전노드와 연결 정보를 가진 포인터로 구성
4-1) 더블 링크드 리스트 (Double Linked List, 이중 연결 리스트)
- 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
5. 해쉬 테이블 (Hash Table) : Key에 데이터(Value)를 매핑할 수 있는 데이터 구조
- 해쉬 함수를 통해 배열에 키에 대한 데이터를 저장한 후, Key를 통해 바로 데이터가 저장되어 있는 주소 조회
- Key값이 중첩되어 Key값 충돌이 일어날 경우 Chaning, Linear Probing 기법을 통하여 해결
5-1) Chaning 기법
- 충돌이 일어날 경우, 링크드 리스트 자료구조를 사용하여, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜 저장
5-2) Linear Probing 기법
- 충돌이 일어날 경우, Hash Address의 다음 Address부터 맨 처음 나오는 빈공간에 저장
6.트리 (Tree)
- Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
6-1) 이진 트리 (Binary Tree) : 노드의 최대 Branch가 2 인 트리
6-2) 이진 탐색 트리 (Binary Search Tree)
: 왼쪽 노드는 현재 노드보다 작은 값, 오른쪽 노드는 현재 노드보다 큰 값을 만족하는 트리
6-3) 신장 트리 (Spanning Tree)
: 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프, 사이클이 존재하지 않는다.
7. 힙 (Heap) : 데이터에서 최대값 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리
7-1) 완전 이진 트리 (Complete binary Tree)
- 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
- 최대값 또는 최소값을 빠르게 찾기 위해서 사용되는 자료구조
Part 2 알고리즘 이론
- 해당 파트에서는 앞에서 공부한 자료구조를 토대로 알고리즘을 해결하는 방안을 학습하고 이해하는 부분이였다
처음에는 무난하다 라고 생각할정도의 파트 였는데 점점 챕터가 진행될 수록 어려워지는 느낌을 받고 한 번에 이해하기는
어려운 부분들도 많아 알고리즘이 이해도 중요하지만 반복 학습을 통하여 익숙해져야 한다는 느낌을 받은 파트이기도 하다
해당 파트에서는 기본 정렬 알고리즘, 재귀용법, 동적계획법과 분할정복, 고급 정렬 알고리즘, 그래프와 자료구조, 그래프 탐색 알고리즘
탐욕 알고리즘, 백 트래킹 등에 대한 알고리즘 유형 및 이론에 대해서 설명해주었으며 예시를 들어 풀이 해주었고 예시를 보면서 이해하니깐
기본 원리로만 이해하던 알고리즘이 한층 더 쉽게 다가오는 느낌이였다.
해당 파트 자료 요약
알고리즘
1. 정렬
1-1) 버블 정렬
- 인접한 두 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘
1-2) 선택 정렬
- 주어진 데이터 중, 최소값을 찾아서 해당 최소값을 데이터 맨 앞에 위치한 값과 교체한다
- 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다.
1-3) 삽입 정렬
- 두번째 인덱스부터 시작하며, 해당 인덱스 앞에 있는 데이터 부터 비교하여 더 작으면 해당 인덱스 앞으로 이동
1-4) 병합 정렬
- 문제를 작은 2개의 문제로 분리하고 각각을 해결한다음, 결과를 모아 문제를 해결하는 방법, 분할 정복 방법
1-5) 퀵 정렬
- 기준점(pivot)을 정한 후, 기준점 보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성,
각 왼쪽, 오른쪽은 재귀용법을 사용하여 다시 동일 함수를 호출하여 반복한다
- 함수는 왼쪽 + 기준점 + 오른쪽을 리턴
2. 재귀 호출
- 함수 안에도 동일한 함수를 호출하는 형태
3. 동적 계획법
- 입력 크기가 작은 부분 문제들을 해결한 뒤, 해당 부분의 해(풀이)를 활용해서 보다 큰 부분 문제를 해결 후 ,
최종적으로 전체 문제를 해결하는 알고리즘
- Memooziation 기법 사용 : 프로그램 실행 시 이전에 사용했던 값을 기억하여 재 사용
4. 분할 정복
- 문제를 나눌 수 없을 떄 까지 나눈후, 각각 풀면서 합병하여 문제의 답을 찾는 알고리즘
- 상위의 해답을 얻기 위해, 아래로 내려가며 하위의 해답을 구하는 방식
5. 탐욕 알고리즘
- 최적의 해에 가까운 값을 구하기 위해 사용되는 알고리즘, 매순간 최적이라고 생각되는 경우를 선택
6. 백트래킹
- 제약 조건 만족 문제에서 해를 찾기 위한 전략
- 해를 찾기 위해, 후보군에서 제약 조건을 점진적으로 체크 하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단
되는 즉시 이 후보군은 체크를 하지 않는다는 표기를 하고, 다른 후보군으로 넘어가 최적의 해를 찾는 방법
7. 탐색
7-1) 순차 탐색
- 데이터가 담겨 있는 리스트를 앞에서 부터 순차적으로 하나씩 비교하여 원하는 데이터를 찾는 알고리즘
7-2) 이진 탐색
- 탐색할 자료들을 둘로 나누어(이진) 해당 데이터가 있을만한 곳을 탐색하는 방법
8. 그래프
- 실제 세계의 현상이나 사물을 노드(정점,Vertex)와 간선(Edge)로 표현하기 위해 사용
8-1) 너비 우선 탐색
- 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드를 먼저 순회, 형제노드 우선 순회
8-2) 깊이 우선 탐색
- 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와 다른 형제들의 자식을 타고 내려가며 순회
9. 최단 경로 알고리즘
- 두 노드를 잇는 가장 짧은 경로를 찾는 알고리즘
- 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는것이 목적
9-1) 다익스트라 알고리즘
- 하나의 정점에서 다른 모든 정점에 도착하는 가장 짧은 거리를 구하는 문제
- 우선순위 큐를 사용하는 방식으로 설명, MinHeap방식을 활용하여 가장 짧은 거리를 가진 노드 정보 추출
10. 최소 신장 트리 알고리즘
- 신장 트리 중, 간선의 가중치의 합이 최소인 신장트리
10-1) 크루스칼 알고리즘
- 간선이 가장 작은 순서대로 정렬한 후, 가장 작은 순서대로 선택하나 사이클이 발생하면 탈락
- 시작 노드를 선택하지 않으며 가장 작은것을 먼저 선택한 후 작은 순서대로 계속 선택해 나아간다.
10-2) 프림 알고리즘
- 시작 노드를 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 노드를 선택하고,
해당 노드에서 다시 최소 간선으로 연결된 정점을 선택하는 방식
- 최소 신장트리를 확장해나가는 방식
Part 3 알고리즘 유형별 문제 풀이
- 해당 파트를 통해 앞서 공부했던 자료구와 알고리즘을 실제 유형에 알맞게 문제를 보면서 한층 더 깊게 이해할 수 있는 계기가 되었다
또한 알고리즘의 접근 방식을 새롭게 접근할 수 있었고 류호석 강사님의 알맞는 문제 풀이를 통하여 어떠한 유형에 어떠한 알고리즘을
사용하며 문제를 통한 알고리즘 유형을 잘 파악 할 수 잇는 계기가 되었다
- 해당 파트에서는 4,5 단계는 문제 조차 이해되지 않은 것들도 많았지만 해당 문제들을 반복하여 계속 이해하고 풀이하는 방법밖에 없다
라고 다시 한번 깨닫게 되는 계기였다.
- 알고리즘은 단순 이해보다는 반복 과 학습이 더 중요하다라고 생각하게 된 파트이다...
Part 4 SQL
- 해당 파트는 DB에서 사용되는 조회 커리에 대한 SQL 쿼리에 대한 강의 파트이다.
- 처음에는 SQL이 뭔지 간단한 설명과 함께 많이 사용되는 조회 쿼리에 대한 설명과 예시를 통한 이해를 할 수 있었다
해당 파트 자료 요약
1) 기본 검색 및 정렬
SELECT [ 컬럼명들(, 를 통해 구분) ] FROM [ 테이블명 ]
WHERE [조건들 (and,or 연산자를 통해 구분) ] ORDER BY [컬럼명들 (, 를 통해 구분)]
2) 그룹 제어
GROUP BY [컬럼명] ("," 를 통해서 구분) : 조회된 데이터를 특정 컬럼으로 그룹화하여 데이터를 추출
-> Select 컬럼들은 Group By절에서 사용된 컬럼만 사용 가능
HAVING [GROUP BY절에 해당하는 조건들] (","를 통해서 구분) : 집계 함수를 통하여 조건을 걸 수 있다.
3) 분기문
1. Simple Case,
2. Search Case 구문
4) 집합 연산
1. UNION : 두 테이블을 중복되는 결과를 모두 제거하고 보여준다.
2. UNION ALL : UNION 집합 연산에서 중복되는 결과를 모두 같이 보여준다.
5) 순위 집계 함수
1.RANK
- 동일한 값에는 동일한 순위, 다음 순위는 동일한 순위 개수만큼 건너 뛰어 등수 매김
2. DENSE_RANK
- 동일한 값에는 동일한순위, 다음 순위는 바로 그 다음 순위가 나옴
3. ROW_NUMBER
- 동일한 값에도 먼저 나온순서대로 등수 부여
6) 조인
1. INNER JOIN
- 두 테이블 간에 양쪽 모두 존재하는 데이터만 도출한다. KEY를 통하여 연결함
2. OUTER JOIN
2-1) LEFT OUTER JOIN
- 왼쪽의 테이블 기준으로 결합하며 오른쪽의 데이터가 없는경우 오른쪽 테이블은 null로 값이 결합됨
2-2) RIGHT OUTER JOIN
- 오른쪽의 테이블 기준으로 결합하고 왼쪽에 데이터가 없는 경우 왼쪽 테이블은 null로 결합됨
3. FULL OUTER JOIN
- 두 테이블 간을 비교해서 없는 데이터는 null값으로 표현하고 나머지는 다 결합하여 표현한다.
4. SLEF JOIN
- 자기 자신 테이블에서 데이터를 결합하여 추출하기 위한 JOIN, 반드시 컬럼에다가 명칭을 부여해야함
5. CROSS JOIN
- 좌측 테이블의 한 컬럼과 우측 테이블의 모든 행을 곱해서 데이터를 추출
- 좌측 테이블 행의 수 * 우측 테이블 행의 수 => 총 개수
7) 집계 함수
1. MAX 컬럼명
- 명시된 컬럼 내 값 중 최대값 반환
2. MIN 컬렴명
- 명시된 컬럼 내 값 중 최소값 반환
3. COUNT 컬렴명
- 명시된 컬럼 내 값의 전체 행 수 반환 (NULL 값 제외)
4. SUM 컬럼명
- 명시된 컬럼의 데이터 타입이 숫자일 경우, 해당 컬럼 내 모든 데이터 합 반환 (NULL 값 제외)
5. AVG 컬럼명
- 명시된 컬럼의 데이터 타입이 숫자일 경우, 해당 컬럼 내 모든 데이터 평균 반환 (NULL 값 제외)
8) 문자열 함수
1. SUBSTRING(string, int, int)
- 첫번째 명시한 문자열의 부분 문자열 잘라오기
2. LTRIM , RTRIM
- 명시한 문자열의 좌측/우측 공백을 제거
- 두번째 파라미터가 있는 경우 두번재 파라미터에 주어진 문자 제거 후 반환
3. LPAD / RPAD (string, n , string)
- 첫 번째 명시한 문자열에 길이가 n이 되도록 좌측/우측 부터 세번째 명시한 문자열로 채운 표현식 반환
4. REPLACE(string, string_pattern, string, string_replacement)
- 첫 번째 명시된 문자열중 string_pattern에 해당하는 문자열을 string_replacement 문자열로 변환
5. LENGTH(string)
- 명시된 문자열의 길이를 구하여 반환 (공백 포함)
9) 날짜 함수
1. NOW()
- 현재 날짜 및 시간 출력
2. AGE
- 파라미터가 두개일 경우 : 두 날짜 사이의 시간차이 계산
- 파라미터가 한개일 경우 : 현재시간에서 파라미터로 주어진 날짜의 시간 차이 계산
3. DATE_PART(text,timestamp)
- 두 번째 명시한 timestamp에서 첫 번째 명시한 날짜 키워드 인자 해당하는 값 추출
EX) SELECT DATE_PART("day", timestamp "2022-03-02') => 날짜인 02 추출
4. DATE_TRUNC(text.timestamp)
- timestamp 값에서 첫 번째 명시한 날짜 키워드 인자에 해당하는 값 이하의 날짜데이터를 Default 처리하고 반환
EX) SELECT DATE_TRUNC("month", timestamp "2022-03-02 00:35:18)
=> month(달) 제외 기본값 2022-03-02 00:00:00
10) 그 외 자주 사용되는 함수
1. TO_CHAR(timestamp,text)
- 첫 번째로 명시된 timestamp 값을 두번째 인자의 포맷 문자열로 변환 후 반환
2. COALESCE(value, ex1,ex2 ...)
- 첫 번째로 명시된 인자가 null일경우 두번째 인자를 반환, 두번째 인자가 null일 경우 세번째 인자를 반환, 순차적 반환
- null값일 경우 지정한 값으로 반환되어 처리된 후 조회
3. CAST(source_type as target_type)
- 첫번째 명시된 source_type을 두번째 인자로 명시된 target_type으로 변환하여 반환
EX) SELECT CAST("2021-03-28" as timestamp) => text인 2021-03-28을 timestamp형식으로 변환하여 반환함
4. ROUND(v numberic, s int)
- 첫 번째 명시된 v값을 소수점 s자리까지 반올림 하고 s자리 미만은 버림
Part 5 실전 알고리즘 문제풀이
- 해당 파트는 part3과 같지만 다른 유형의 접근 방법을 알 수 있는 알고리즘 문제풀이 파트였다
위에 파트는 류호석 강사님이 만든 예제를 통한 알고리즘 풀이였다면 해당 파트는 나동빈 강사님이 알고리즘 문제를 통한 유형 파악
및 알고리즘 풀이로 또 다른 색다른 유형의 알고리즘들을 파악 할 수 있는 계기였다.
- 해당 파트에서는 문제가 정말 많아 내 생각에는 해당 파트를 다 완성하고 이해할 수 있다면 거의 웬만한 코딩 테스트에는 합격을 하지
않을까 생각하지만 또 생각해보면 엄청 많은 유형의 알고리즘을 파악하고 해결할 수 있는 능력을 키워야 한다고 생각이 든 파트이기도 하다
해당 챌린지를 진행하면서 공부를 한다는것에 대한 의미도 좋았지만 습관이라는것을 기른거 같아 뿌듯하다
챌린지가 끝난 잠시의 자유를 가진 후에 또 자기 개발에 정진하는 모습을 지켜나아가야겠다
고생했다!
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
패스트캠퍼스 [직장인 실무교육]
프로그래밍, 영상편집, UX/UI, 마케팅, 데이터 분석, 엑셀강의, The RED, 국비지원, 기업교육, 서비스 제공.
fastcampus.co.kr
'알고리즘 챌린지' 카테고리의 다른 글
| 패스트캠퍼스 챌린지 50일차 (0) | 2022.03.14 |
|---|---|
| 패스트캠퍼스 챌린지 49일차 (0) | 2022.03.13 |
| 패스트캠퍼스 챌린지 48일차 (0) | 2022.03.12 |
| 패스트캠퍼스 챌린지 47일차 (0) | 2022.03.11 |
| 패스트캠퍼스 챌린지 46일차 (0) | 2022.03.10 |