알고리즘을 어떻게 공부해야 될까?

알고리즘을 왜 공부해야 될까?

※ 알고리즘 공부 필요성

알고리즘 공부 필요성

알고리즘을 공부하는 방법은 여러 문제를 많이 풀어보는 것입니다.

* 이 게시글은 순수 알고리즘 과목에 대한 내용보다 Problem Solving에 중점을 두었습니다.

 

목표하는 기업이나 대회에 따라 준비하는 순서가 다를 수 있습니다.

시험시간, 제한 조건(시간·공간 복잡도), 문제유형 등

DFS, BFS, 정렬, 백트래킹, DP, 분할정복, 최단거리 중점을 두어야할 내용이 다르기 때문입니다.

- 삼성: 삼성 SW 코딩 테스트 준비(A형)  

삼성 SW 코딩 테스트 준비(A형)

 

문제해결 능력과 구현력

Input / Output Data를 포함한 문제 특성을 이해하고 적절한 자료 구조를 선택해야 합니다.

※ 읽기 쉬운 코드를 작성하여 디버깅 효율성을 높여야 합니다.

    ex) 클래스 및 함수 분리 (모듈화)

    전역 변수를 많이 사용하면 프로그램의 흐름을 파악하기 어려워질 수도 있지만 

    코딩 테스트는 비교적 단순하기에 전역 변수를 활용하는 것도 나쁘지 않습니다.

 

또 다른 학습을 위한 배경지식

문자열 알고리즘 문제, 최단거리(다익스트라), 가장 가까운 두 점

- 컴퓨팅적 사고력이 필요한 경우

 

어떤 언어가 좋을까?

문제 푸는 대부분 장소에서 C / C++ / Java / Python으로 크게 구분되어집니다.

준비하는 기간, 시험 유형 및 방식에 따라 자유롭게 선택해도 무방합니다.

ex) 다른 사람과 코드리뷰를 위해서 익숙한 언어 선택

ex) 보다 간결한 언어를 사용하고자 python 선택

※ 어떤 프로그래밍 언어를 선택해야할까?  

어떤 프로그래밍 언어를 선택해야할까?

 

# 특정 문제를 너무 오래 붙잡지 말자.

문제에 대한 고민을 많이 해보는 것은 중요하지만, 2시간 이상 사용했다면

더이상 소중한 시간을 낭비하지말고, 다른 사람의 풀이를 일단 참고한 후,

추후에 다시 풀어보는 것이 효율적입니다.

 

# 같은 형태로 프로그램을 작성하자.

2차원 배열 탐색시 (가로, 세로) → (세로, 가로)로 바꿔보는 시도는

문제에 따라서 변형이 필요할 수도 있지만, 되도록이면 같은 형태로 작성하는 것이 좋습니다.

　for(int x=0; x<N; x++){
    for(int y=0; y<M; y++){
        ...
    }
}

for문을 do-while문, while문 / if문을 swich문 등으로 가독성을 위해 바꿔보는 것은 좋지만,

실수의 원인이 될 수 있기에 형태를 고정화해두는 것이 좋습니다.

문법 변화에 집중하기 보다는 함수, 클래스 등 모듈화에 대해 고민하는 것이 좋습니다.

 

# 의미 있는 변수명 사용하기

프로그래밍할 때, 가장 고민되는 부분 중 하나는 이름 짓기(Naming) 입니다.

ex) 2차원 평면 상에 한 개의 점과 원이 주어졌을 때,

      점이 원 안에 포함되는지 여부를 반환하는 함수

boolean judge(int x, int y, int cx, int cy, int cr);

boolean isInsideCircle(int x, int y, int cx, int cy, int cr);

 

직관적으로 해당 점이 원 안에 있을 때 참이 반환되는 것을 알 수 있습니다.

 

# 코드와 데이터 분리

날짜를 출력할 때 월을 숫자가 아니라 영문 이름으로 출력

String getMonthName(int month){

    if(month == 1) return "January";

    if(month == 2) return "February";

       ... 중간 생략 ...

       return "December";

}

 

코드상의 주요 Logic과 상관 없는 데이터는 가능한 한 분리

String[] monthName = {"January", "February", ... 중간 생략 ..., "December" };

+) 게임판에서 움직일 수 있는 방법 표현(상하좌우 + 대각선)

int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

int dy[8] = {1, 1, 1, 0, -1, -1, -1, 0};

　

# 최소, 최대 예외 다루기

가장 작은 입력과 가장 큰 입력에 주의하면 예상치 못한 오류를 잡을 수 있습니다.

ex) 자연수를 입력받아 소수(prime number) 판정 함수

boolean isPrime(int n){

    if(n % 2 == 0) return false;

    for(int i = 2; i<n; ++i)

        if(n % i == 0) return false;

    reuturn true;

}

소수가 아닌 가장 작은 자연수 1에 대해서 예외처리를 해주어야 합니다.

 

# 실수 표현을 주의하자.

가급적이면 실수 연산을 요령껏 피할 수 있어야 합니다. (정수형태로만 계산되도록.)

ex) 세 정수 a / b * c를 계산해야 하는게 결과가 항상 정수라는 것을 알고 있다면, 

      계산 순서 (a * c) / b 형태로 바꾸어 중간에 실수가 나오지 않도록 할 수 있습니다.

ex) 두 점 사이의 거리를 구하는 공식

제곱근을 구해서 실수형으로 비교할 바에는 양변 제곱하여 계산

d2 = d * d = (x1- x2)2 - (y1- y2)2