회고록(21) - 코딩테스트 준비

1. 데일리 일기

어제 선참시 내용을 일기에 안썼다. 그래서 오늘은 그 선참시에 관해 이야기 하고 싶다. 선배가 말해준 것중 기억에 남는게 몇개 있다. (1) 학습 방법 (2) 결국엔 끈기이다.

이 중 나에게 좀 적용했으면 좋을 것 같다는 내용을 적고싶다.

학습 방법

• 기본적으로 여유 시간이 있을때 복습 및 간단한 예습을 진행하자. 특히 복습은 필수다.
• 가장 이상적인 방법은 (1) 예습 - (2) 정규 교육시간 - (3) 복습
  • (1) 예습 : 학습할 내용의 큰 그림을 파악하여, 주어진 정규 교육시간에 어떻게 끝내볼지 생각해본다.
  • (2) 정규 시간 : 최대한 이해하려고 노력한다. 단 많은 시간을 투자해도 이해가 되지 않을때는 일단 넘어가고 나중에 복습한다.
  • (3) 복습 : 다시 큰 그림을 좀 더 세부적으로 파악해보고, 이해가 안됐던 부분을 디테일하게 작게 쪼개서 이해해본다.

끈기

• 결국엔 성장적 마인드셋을 가지고, 끈기있게 계속 알고리즘 문제들, 프로젝트에 덤비면 1등은 아니더라도 무사히 수료는 할수 있다. 중요한건 꺾이지 않는 마음이다..

요즘 점점 알고리즘을 풀면서 자신감도 떨어지고 있는데, 결국 끈기를 가지고 계속 부딪히면 성장해서 익숙해 질 것이라고 믿자. 결과보다는 과정을 즐기는 사람이 되보자. 섣부르게 결과를 판단하는 내 나쁜 습관이 얼른 사라졌으면 좋겠다.

2. 오늘 배운 내용

알고리즘

정의

문제상황을 해결하기위한 최선의 선택을 말한다.

접근법

1. 문제를 구체적으로 이해한다.!
2. 문제를 해결하기 위한 전략을 세운다.
   • 의사코드, 그림등을 이용한다.
3. 컴퓨터 언어로 해당 전략을 구현한다.
   • 구현후에는 코드의 최적화를 시도해본다.

의사코드

정의

문제해결위한 논리를 내가 이해할 수 있는 방식으로 적어놓는 코드를 말한다.

• 한글로만 표현할수도 있지만, 컴퓨터언어와 섞어서 쓰면 더 가독성있게 코드를 작성할 수 있다.
• 컴퓨터는 사람과 다르게 상상해서 처리하지 않으므로, 세부적으로 명령들을 하나하나 수도코드로 작성하는 습관을 들여야한다.
  • 구체적인 의사코드가 적힌 코드가 오히려 디버깅에 용이하고, 시간도 단축시켜준다.

시간복잡도

정의

입력값의 증가에 따라 실행횟수(걸리는 시간)이 얼마나 증가했는지를 나타내기 위해 시간복잡도를 사용한다.

그러므로 효율적인 알고리즘을 구현했다는 의미는 입력값이 커짐에따라 증가하는 시간의 비율을 최소화한 알고리즘이라고 말할 수 있다.

특징

1. 주로 Big O 표기법을 사용한다.
   • 최악의 경우를 막아야 대응이 가능하기 때문이다.
2. O(1)
   • 가장 작은 시간복잡도를 나타낸다.
   • 입력값이 증가해도 시간 변화가 존재하지않는다.
   • 예시 : 배열의 인덱스를 통해 값을 빼오는 경우
3. O(N)
   • 입력값이 증가하는 만큼 같은 비율로 시간이 증가하는 시간복잡도 이다.
   • O(2N), O(3N) 등은 거대하게 증가하는 N값에 비해 큰 영향을 못주므로 계수는 생략해준다.
   • 예시 : 일반적인 for문이 이에 해당한다.
4. O(logN)
   • 입력값이 증가하는 것보다 적은 비율로 시간이 증가하는 시간 복잡도 이다.
   • 예시 : Binary Search Tree 의 경우, 1~50중의 값에서 원하는 값을 찾는다고 가정해보자. 입력값이 증가할 수록 Binary Tree가 완성되면서 원하는 값이 존재할 경우의 수가 절반으로 떨어진다.
5. O(n^2)
   • 입력값이 증가하는 만큼 제곱의 비율로 시간이 증가하는 시간복잡도 이다
   • 예시 : 입력값을 범위로 가지는 이중 for문을 생각해보면 쉽다.
6. O(2^n) , O(N!)
   • 입력값이 증가할때 마다 엄청나게 시간 복잡도가 늘어나는 비효율적인 알고리즘을 나타낸다.
   • 예시 : 재귀를 통해 만든 피보나치 수열코딩테스트에서의 시간복잡도

• 테스트에서 주어지는 N이 크다면, 효율적인 시간복잡도를 고려해서 풀어야할 문제 유형일 확률이 높다.

탐욕 알고리즘

정의

순간순간의 최선의 선택이 최종적으로 효율적인 선택(해답에 도달)이 되는 알고리즘을 말한다.

적용 순서

1. 선택 절차 : 현재 상태의 최적을 선택을 한다.
2. 적절성 검사 : 선택된 해답이 문제의 조건을 만족하는지 검사해본다.
3. 해답 검사 : 원래의 문제가 해결 되었는지 검사해보고, 그렇지 않다면 다시 1번으로 돌아간다.

조건

탐욕 알고리즘은 아래의 특정조건에서만 사용할수 있는 알고리즘이다.

1. 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않아야한다.(ex) 반례 : 마시멜로 실험)
   • 현재의 경우에 대한 선택과 미래의 경우에 대한 선택이 독립적이여야한다.
2. 최적 부분 구조 : 문제에 대한 최종 해결 방법이 부분 문제에 대한 최적 문제 해결 방법으로 도출되어야한다.

구현, 시뮬레이션

정의

여러 구체적인 조건(문제)들이 있을때, 이러한 조건(문제)들을 파악하고 얼마나 빠르고 정확하게 구현할수 있는지를 묻는 알고리즘 문제 유형이다.

예시 : 브루트포스 문제, 시뮬레이션 문제(문제의 수많은 요구사항대로 코드를 옮기는 문제)

완전 탐색 알고리즘 (Brute-Force Algorithm)

정의

문제 해결에 대한 해답을 얻을 때까지 시간과 컴퓨터 자원을 이용해 무차별적으로 대입하는 방법을 말합니다.

특징

• 공간복잡도와 시간복잡도를 고려하지 않은 알고리즘으로 최적의 솔류션이라고 볼수 없다. 일단 어떻게든 솔루션을 찾기 위해 사용되는 알고리즘이다.
• 문제의 복잡도에 매우 민감하다. 복잡해질수록 기하급수적으로 많은 자원(시간, 컴퓨팅자원)을 필요로 한다.

언제 사용할까?

• 프로세스를 실행시킬만한 적합한 알고리즘이 없을때
• 최적의 솔루션을 찾는데 시간이 걸리기때문에, 일단 브루트 포스로 문제 해결을 해놓고 넘어가는 경우

어디서 활용될까?

• 선택 정렬
• 문자열 매칭 알고리즘
• 동적 프로그래밍등

이진 탐색 알고리즘(Binary Search Algorithm)

탐색 알고리즘

구글에 검색해서 원하는 결과를 얻기 위해서는 탐색알고리즘을 이용할 수 있다.

탐색 알고리즘의 종류

1. Linear Search Algorithm
2. Binary Search Algorithm
3. Hash Search Algorithm

정의

정렬된 데이터를 데이터의 크기의 절반으로 줄여가면서 원하는 값을 탐색해가는 알고리즘이다.

동작 방식

1. 정렬된 배열의 가운데 인덱스 값을 찾는다.
2. 원하는 값인지 비교한다
3. 아니라면 값 비교를 통해, 원하는 값이 존재하는 절반의 배열을 가져온다.
4. 다시 가운데 인덱스를 찾고 비교한다.(반복)

특징

• 시간복잡도가 O(logN)으로 매우 큰 데이터일수록 효율적이다.
• 데이터가 정렬되있지 않으면 효율적으로 동작하지 않는다.
• 인덱스를 사용하는 자료구조에서만 구현할수 있다는 단점이 있다.

어디서 사용될까?

• 도서관의 자료검색에서 자료를 검색할때
• 대규모 시스템에 대해서 시스템 부하가 발생할때, 필요한 CPU양을 탐색하여 구하는데 사용된다.

BST와의 차이점

BST 는 말그대로 트리인 자료구조이고, BSA는 알고리즘이므로 문제해결을 위한 방법이다.

3. 새로 알게 된 내용 & 이해가 안가는 내용

더 공부하면 좋은 키워드에 

분할정복 알고리즘, Dynamic Programming이 있었다. 이 둘은 노션에 따로 정리가 필요한 것 같다.