[알고리즘] 알고리즘 공부법

[알고리즘] 알고리즘 공부법

* 이 글은 http://baactree.tistory.com/52?category=735523 를 토대로 제가 자주 읽기 위해 작성한 글 입니다. 자세한 내용은 링크로 들어가서 확인하시면 더 도움 받으실 수 있습니다.

알고리즘 실력 향상 위해서는...

1. 구현력

2. 문제해결능력

3. 배경지식

이 필요하다.

1. 구현력

* 구현력이란? 

- 본인이 생각하는 알고리즘을 그대로 구현

* 부족할 경우

- 대충 어떻게 할 줄은 알겠는데 코딩하려니 한 줄도 못짜겠다.

* 구현력 향상을 위해선?

1) 어떤 프로그램 만들고자 하는지 명확히 한다.

EX) 무엇을 입력받고, 어디에 저장하고, 어떤 과정을 거쳐 무엇인가 얻고, 최종적 결과물 이렇게 출력

2) 순서도를 먼저 적고 디테일하게 어떤 데이터 타입, 자료구조 저장할지 종이에 적어가면서 생각

3) 순서도를 명확히 그리는 연습 자주 하면 곧 머리 속으로 하게 되고, 나아가 코딩까지 동시에 생각 가능해진다.

2. 문제해결능력

* 문제해결능력이란? 내가 알고있는 알고리즘, 자료구조, 다양한 테크닉 등을 문제에 변형해 적용하는 능력 (응용력이라고 생각하면 편하다)

* 부족할 경우

- 어떻게 접근해야할지 모른다.

- 그래서 솔루션 얻어보니 내가 아는 알고리즘, 자료구조

* 해결하려면

- 양질의 문제(30분~2시간 고민하면 해결 가능한 문제)를 푸는 것

- 이전에 접근한 다양한 방법들을 잘 정리해 두는 것

- 벽을 뚫는다는 느낌으로 노력이 필요 ★★

* 컴퓨팅적 사고 능력이 부족한 경우 ★★ (배경지식은 충분히 공부해도 문제 접근이 어렵다면?)

- 이 능력 부족하면 재귀함수, 완전탐색, 백트래킹, BFS, 분할정복에 대한 이해 어려움

- 컴퓨터가 1초에 1억번의 연산을 할 수 있음 을 이해

- 따라서 어떤 시간 복잡도 까지는 가능한지 이해

- 메모리 제한이 몇 이므로 배열을 어느정도 까지는 할당할 수 있겠다 라는 생각 할줄 알아야함

- 재귀함수를 트리형태로 어떻게 진입하고 무엇을 하고 무엇을 리턴하고 종료되는지 그릴 수 있어야함

- 완전탐색에 있어서 상태공간의 정의를 할 수 있어야함

- 현재 상태에서 다음 상태로 갈 수 있는 방법이 몇가지 인지 이해

- 최종 종료 상태와 최초 진입 상태가 무엇인지 이해하고 그림으로 표현 가능해야함

--> BOJ 별찍기, n과m 시리즈, SWEA 난이도 1~2 문제

* 구현, 디버깅 시간이 오래 걸린다면

- 자주 한 구현 실수들 정리

- 대략적 순서도 그리고 자주 사용하는 부분을 함수로 템플릿화 하는 연습 필요

- 근본적으로 코드 길이가 줄어야 실수 확률도 줄어든다.

3. 배경지식

* 배경지식이란? 

- 기초적인 프로그래밍 문법 및 알고리즘, 자료구조 등을 아는 것, 

- 선형대수학과 확률 등과 같이 기본적으로 수학적 지식을 아는 것과 같은 능력.

* 부족할 경우

- 솔루션 열었더니 생판 모르는 외계어 적혀있는 상황

* 해결하려면

- 제일 공부하기 쉬운 능력

- 시중의 역량테스트 대비 강의, 책, 배경지식에 대해 설명.

* 기초 배경 지식

- 코딩 문법

- 시, 공간 복잡도 분석

- 배열, 트리, 그래프, 힙, BST, 스택, 큐 같은 기본적 자료구조

- DFS, BFS, 정렬, 백트래킹, DP, 분할정복, 최단거리 등의 기초적 알고리즘