1. 자료구조와 알고리즘이 중요한 이유

자료구조 + 알고리즘 = 프로그램

cf. 코딩테스트 광탈 방지 A to Z : JavaScript 및 다른 자료들을 공부하고 정리한 글입니다.

1.1 알고리즘 공부 방법

라매 개발자 - 백준 온라인 저지(BOJ)로 처음 알고리즘 시작해서 공부했던 방법

• 백준 강의 : 알고리즘 기초1/2부터 기초2/2까지 포함되어 있는 문제 풀기
• 재밌으면 알고리즘 중급1/3까지 풀기
• 강의도 들어도 됨

2. 알고리즘을 잘 공부하는 방법

2.1 문제를 풀 때 중요한 것

1. 항상 여러가지 풀이 방법이 있을 수 있다는 것을 기억하자
2. 항상 예외가 있을 수 있다는 것을 기억하자
3. 내가 풀어낸 답이 베스트인지 의심하자
4. 문제를 풀었다면 시행착오를 모두 기록하자
5. 다른 사람의 코드를 많이 보자. 생각하지 못했던 방법을 발견할 수 있다.
6. 쉽게 포기하지 말자. 하지만 도저히 모르겠다면 답을 보는 것도 좋은 방법이다.

2.2 그나마 재미있게 공부하는 방법

1. 시각적인 사이트의 도움을 받자
   1. VISUALGO : https://visualgo.net/en
   2. Algorithm Visualizer : https://algorithm-visualizer.org/
2. 공부하는 자료구조/알고리즘이 어디에 쓰일지 생각해보면서 공부하자.

3. 코딩테스트 유형

• 유형 1 : 분기와 반복을 사용하는 단순 절차 문제
• 유형 2 : 자료를 어떠한 구조에 담아둬야 효율적인 문제
• 유형 3 : 빠른 성능을 위해 이미 연구된 알고리즘을 사용하는 문제
• 유형 4 : 특정 사고방식으로 접근해야 하는 문제

유형 1을 제외한 나머지는 전부 입력 데이터에 대한 분석, 자료구조와 알고리즘에 대한 지식이 필요하다.

• 입력 데이터는 재료,
• 자료구조는 재료를 적절한 구조로 가공하는 것,
• 알고리즘은 레시피를 보고 조리하는 것처럼 데이터를 올바르게 처리하여 원하는 결과를 주는 행위를 의미한다.

4. 문제 분석

코딩 테스트는 코딩 능력이 아니라 문제 풀이 능력을 확인하는 것이 핵심이다.

그래서 무작정 코드 작성하기 보다 2~4시간의 문제 풀 시간을 주므로, 전체 시간의 50% 정도는 문제 분석에 시간을 쓰는 것이 좋다.

1. 문제를 쪼개서 분석하기
   • 문제를 동작 단위로 쪼개서 분석하는 것이 유리하다.
2. 제약 사항을 파악하고 테스트 케이스를 추가하기
   • 문제에는 보통 제약사항이 존재하는데,
   • 제약사항을 정리해두고 이를 고려해 테스트 케이스를 추가하는 연습을 하는 것이 좋다.
3. 입력값을 분석하기
   • 보통 알고리즘의 시간 복잡도는 입력값이 결정하는 경우가 많다.
   • 입력값 크기를 확인하면 문제를 제한시간 내 풀 수 있는 알고리즘과 그렇지 않은 알고리즘을 미리 걸러낼 수 있다.
   • e.g. 입력 데이터가 100만 개라면, O($N^2$) 알고리즘으로는 맞는 코드를 작성해도 시간 내 출력값이 나올 수 없다.
4. 핵심 키워드를 파악하기
   1. 핵심 키워드가 A라고 무조건 해당 알고리즘을 적용하라는 것은 아니지만,
      1. 핵심 키워드는 곧 특정 알고리즘을 암시하는 경우가 많고, 좀 더 빠르게 문제를 파악하기 좋다.
   2. 최적의 해라는 키워드가 있으면 너비 우선 탐색을 고려하는 것이 좋다.
      1. 왜냐하면 너비 우선 탐색 알고리즘 자체가 최적의 해를 구하는 것이기 떄문이죠.
   3. 정렬된 상태의 데이터라는 키워드가 있으면, 이진 탐색이나 파라메트릭 탐색을 고민해보는 것이 좋고,
   4. 최단 경로라는 키워드가 있다면, 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘을 고민해보는 것이 좋다.

5. 데이터 흐름이나 구성을 파악하기
   • 구현과 설계의 중요한 기준이 되는 데이터 흐름이나 구성을 파악하는 것도 중요하다.
   • 이는 문제 풀이에 사용할 자료구조와 알고리즘을 선택하고 구현 방향을 정할 떄 중요한 고려 대상이다.
   • 만약 데이터 삽입과 삭제가 빈번하게 일어날 것 같다면 힙(heap) 자료구조를 고려하는 것이 좋다.
   • 또 효율만큼 접근성도 중요하다.
     • e.g. 전화번호부에서 전화번호로 이름을 검색안하고, 이름으로 전화번호를 검색함
     • 연락처는 맵에 저장하되, 키는 이름으로 값은 전화번호로 해야 접근성이 좋다.
     • 접근성이 좋지 않으면 코드가 필요 이상으로 복잡해지는 오류가 발생할 가능성이 높다.

5. 프로그래머스

프로그래머스는 카카오, 네이버, SK 등 900여 IT 기업이 프로그래머스에서 코딩 테스트를 진행하므로, 학습 사이트와 응시 사이트가 같을 확률이 높다.