패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 코딩테스트 강의 한 달 후기

한 달 동안 '패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 코딩테스트' 강의를 듣고, 알고리즘 유형을 공부하고, 문제를 풀어보았다. 

수강 전에는 알고리즘은 마냥 막막하고 어렵게만 느껴졌는데, 하나씩 원리를 배우고 적용하는 과정에서 이해만 제대로 한다면 적용은 금방 할 수 있음을 깨달았다.

그동안 공부했던 것들을 다시 한번 정리해 보는 시간을 가지려 한다.

 

다시 정리할 목차는 아래와 같다.

 

1. 문자열

2. 시간 복잡도

3. 배열

4. 완전 탐색

5. SQL

 

---

[문자열]

1) Java.lang.String

- Java.lang 패키지로 제공되는 Java 문자열 클래스 

- 별도의 import 없이 사용 가능
- 문자열 작업에 유용한 메소드 제공

- 한 번 인스턴스가 생성되면 수정할 수 없음 (immutable object)

 

 2) String 클래스

https://docs.oracle.com/javase/8/docs/api/java/lang/String.html

String (Java Platform SE 8 )

 

3) 문제 풀기

https://www.acmicpc.net/problem/13223

13223번: 소금 폭탄

 

---

[시간 복잡도]

1) 시간복잡도: 입력 크기와 알고리즘간의 관계

- 알고리즘의 복잡도를 나타내는 지표 중 하나
- 입력 크기에 대해 프로그램의 동작시간을 가늠해 볼 수 있는 수단
- Big-O / Big-Omega / Big-Theta 와 같은 표기법으로 나타낼 수 있다.

- 강의에서 다루는 것은 Big-O
- 정의된 입력 데이터 중 가장 최악의 상황을 포함한 시간의 상한선

 

2) Big - O 표기법

- 입력값에 따른 알고리즘의 사용량을 예측하는 방법

- O(1) : 항상 같은 시간이 걸리는 알고리즘

- O(n) : 입력한 시간에 비례

- O(n^2) : for문 하나당 O(n)의 시간복잡도

- O(log n) : 이진탐색. 연산을 한번 거칠 때마다 확인해야 하는 절차가 반씩 줄어듦.

- 상수는 버린다.

 

  

---

[배열]

1) 배열 : 순서(index)를 가진 데이터의 집합

2) 배열의 특징

- 가장 기본적인 자료구조

- 생성과 동시에 크기가 고정됨

- 전체 원소가 메모리 상에 일렬로 고정됨

 

3) 배열 함수 (int 배열이라는 가정 하에)

- get(int idx) : idx 번째 원소 출력

- change(int idx, int changeval) : idx 원소를 changeval로 변경

- append(int val) : 가장 뒤에 원소 삽입 

- insert(int idx, int val) : idx 번째 원소의 앞에 val 삽입

- erase(int idx) : idx 번째 원소 삭제

 

4) 문제 풀기

http://icpc.me/1236

1236번: 성 지키기

http://icpc.me/10431

10431번: 줄세우기

http://icpc.me/10989

10989번: 수 정렬하기 3

http://icpc.me/3273

3273번: 두 수의 합

 

---

[완전탐색 - 시뮬레이션]

 

1) 완전 탐색 : 문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법.

그중에서도*백트래킹(Back-Tracking)을 통해야 하는 상황을 해결하기.

* 백트래킹이란 현재 상태에서 가능한 모든 경로를 탐색하다가 원하는 값과 불일치하는 부분이 발생하면 , 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는 알고리즘이다.

 

2) 코테에 나오는 완전 탐색 종류

N개 중  1) 중복을 허용해서 2) 중복없이 M개를  A) 순서 있게 나열하기 B) 고르기

 

2) 완전 탐색은 함수 정의가 50%

 

// 재귀 함수
// 만약 M개를 전부 고름 => 조건에 맞는 탐색을 한 가지 성공한 것!
// 아직 M개를 고르지 않음 => k번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다. 
static void rec_func(int k){}

public static void main(String[] args){
	input();
    //1번째 원소부터 M번쨰 원소를 조건에 맞게 고르는 모든 방법을 탐색해줘
    rec_func(1);
    System.out.println(sb.toString());

}

 

3) 완전 탐색 문제를 접근할 때는,

- 고를 수 있는 값의 종류 파악하기

- 중복을 허용하는지

- 순서가 중요한 지

 

4) 연습문제 :

[BOJ 15651] https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

[BOJ 15649] https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

[BOJ 15652] https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

[BOJ 15650] https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

---

[SQL 챕터]

1) 분기문

1. simple case expression 

SELECT 
            (CASE [컬럼명] WHEN [비교값1] THEN [반환값1]
                         WHEN [비교값2] THEN [반환값2]
                                          .
                                          .
              ELSE [WHEN절 이외의 조건일때 반환될 값]
              END) AS [별칭 컬럼명]
FROM [테이블명]

 

2. searched case expression

SELECT 
            (CASE WHEN [조건문1] THEN [반환값1]
                  WHEN [조건문2] THEN [반환값2]
                   					 .
                                     .
              ELSE [WHEN절 이외의 조건일때 반환될 값]
              END) AS [별칭 컬럼명]
FROM [테이블명]

 

2) 집합연산 : 두 개 이상의 SELECT 쿼리 결과를 하나로 합쳐 줌.

- 합쳐주는 SELECT 구문의 반환 칼럼의 갯수와 순서가 모두 동일해야 함. 

- 또한 각 컬럼의 데이터 형식이 같아야 함

 

1. UNION : 중복되는 결과 제거

SELECT [컬럼1]
      ,[컬럼2]
      ,[컬럼3]
  FROM [테이블명1]
 UNION
SELECT [컬럼1]
      ,[컬럼2]
      ,[컬럼3]
  FROM [테이블명2]

 

2. UNION ALL : 중복되는 결과 포함

SELECT [컬럼1]
      ,[컬럼2]
      ,[컬럼3]
  FROM [테이블명1]
 UNION ALL
SELECT [컬럼1]
      ,[컬럼2]
      ,[컬럼3]
  FROM [테이블명2]

 

3) 순위 집계

 

1. RANK : 동일한 값에 대해서는 동일한 순위값을 부여하고, 동일한 순위값 개수만큼 등수를 건너뛰고 다음 순위를 부여 

SELECT RANK() OVER(PARTITION BY [그룹할 컬럼들] ORDER BY [순위를 매길 때 사용할 컬럼들])
  FROM [테이블명1]
예) 1등(100점), 2등(90점), 3등(85점), 3등(85점), 5등(80점) ....

 

2. DENSE_RANK : 동일한 값에 대해서는 동일한 순위값을 부여하는 대신, 등수를 건너뛰지 않고 다음 순위를 부여

SELECT DENSE_RANK() OVER(PARTITION BY [그룹할 컬럼들] ORDER BY [순위를 매길 때 사용할 컬럼들])
  FROM [테이블명1]
예) 1등(100점), 2등(90점), 3등(85점), 3등(85점), 4등(80점) ....

 

3. ROW_NUMBER : 동일한 값에 대해서도 고유한 순위값을 부여

SELECT ROW_NUMBER() OVER(PARTITION BY [그룹할 컬럼들] ORDER BY [순위를 매길 때 사용할 컬럼들])
  FROM [테이블명1]
예) 1등(100점), 2등(90점), 3등(85점), 4등(85점), 5등(80점) ....

 

4) JOIN

 

1. INNER JOIN : 교집합

 

 

2. OUTER JOIN

-- LEFT OUTER JOIN : LEFT에 중점

SELECT *
  FROM [테이블1] AS A
  LEFT OUTER JOIN [테이블2] AS B
    ON A.KEY = B.KEY

 

 

 

-- RIGHT OUTER JOIN : RIGHT에 중점

SELECT *
  FROM [테이블1] AS A
  RIGHT OUTER JOIN [테이블2] AS B
    ON A.KEY = B.KEY

 

 

-- FULL OUTER JOIN : 전체 데이터 

 

5) 집계 함수

집계함수	설명
MAX(컬럼명)	명시된 컬럼 내 값들 중 최대값을 반환한다.
MIN(컬럼명)	명시된 컬럼 내 값들 중 최소값을 반환한다.
COUNT(컬럼명)	명시된 컬럼 내 값의 전체 행 수를 반환한다. (NULL 값 제외)
SUM(컬럼명)	명시된 컬럼의 데이터 타입이 숫자일 경우, 해당 컬럼 내 모든 데이터의 합을 반환한다. (NULL 값 제외)
AVG(컬럼명)	명시된 컬럼의 데이터 타입이 숫자일 경우, 해당 컬럼 내 모든 데이터의 평균을 반환한다. (NULL 값 제외)

SELECT MAX(t1) FROM table

 

6) 문자열 함수

문자열 함수	설명
SUBSTRING(string, int, int)	첫 번째 명시한 문자열의 부분 문자열을 잘라온다
LTRIM(string), LTRIM(string, string) / RTRIM(string), RTRIM(string, string)	명시한 문자열의 좌측/우측 공백을 제거한다. 특정 문자를 제거한다.
LPAD(string, n, string), / RPAD(string, n, string)	첫 번째 명시한 문자열의 길이가 n이 되도록 좌측/우측부터 세 번째 명시한 문자열로 채운 표현식을반환한다.
REPLACE(string, string_pattern, string_replacement)	첫 번째 명시한 문자열 중 string_pattern에 해당하는 문자열을 string_replacement 문자열로 변환한다.
LENGTH(string)	명시한 문자열의 길이를 구하여 반환한다.

* SUBSTRING(string, int, int)

--query
SELECT SUBSTRING('문법 공부는 재밌다',1,2)

--result
문법

 

* LTRIM(string)

--query
SELECT LTRIM(' 문법 공부는 재밌어')

--result
문법 공부는 재밌어

 

 

* RTRIM(string, string)

--query
SELECT RTRIM('문법 공부는 재밌어','어')

--result
문법 공부는 재밌

 

 

* LPAD(string, n, string)

--query
SELECT LPAD('문법 공부는 재밌어', 15, '$')

--result
$$$$$문법 공부는 재밌어

 

 

7) 날짜 함수

날짜 함수	설명
NOW()	현재의 날짜 및 시간을 출력
AGE(timestamp, timestamp) / AGE(timestamp)	두 날짜 사이의 시간 차이를 계산 / 현재 날짜와 첫 번째 명시한 날짜 사이의 시간 차이를 계산
DATE_PART(text, timestamp)	두 번째 명시한 timestamp에서 첫 번째 명시한 날짜 키워드 인자에 해당하는 값을 추출
DATE_TRUNC(text, timestamp)	두 번째 명시된 timestamp에서 첫 번째 명시한 날짜 키워드 인자에 해당하는 값 이하의 날짜데이터를  default 처리하고 반환

* DATE_PART(text, timestamp)

--query
SELECT DATE_PART('day', timestamp'2020-06-15')

--result
15

 

 

* DATE_TRUNC(text, timestamp) 

--query
SELECT DATE_TRUNC('month', timestamp'2020-05-16 00:53:12')

--result
2020-05-01 00:00:00

---

 

* 각 리뷰 포스팅 url :

• 강의 1주 차 리뷰 : https://junya-developer-study.tistory.com/21
• 강의 2주 차 리뷰 : https://junya-developer-study.tistory.com/25
• 강의 3주 차 리뷰 : https://junya-developer-study.tistory.com/29
• 강의 4주 차 리뷰 : https://junya-developer-study.tistory.com/31

 

* 패스트캠퍼스 강의 링크 :  https://fastcampus.co.kr/dev_online_codingtest

핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 초격차 패키지 Online. | 패스트캠퍼

 

 

"본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다."