PS-Algorithm | 코딩 테스트를 위한 알고리듬, 자료 구조

게시 2024/11/13 업데이트 2025/09/24

By mascari4615

조회 6 분읽는 시간

2024-11-13. 05:10: 글 계승, 병합.
2023-09-07-U-Algorithm: 알고리듬 과목,
2024-02-18-Data-Structure: Data Structure

머리말

코딩 테스트를 위한 알고리듬, 자료 구조.

알고리듬과 자료구조.

이는 특정 분야의 흥미로운 문제를 풀거나, 코드 최적화를 위한 것.
단순히 서로 다른 Alg-, Dat-Str를 사용하는 것만으로 성능과 결과가 크게 달라질 수 있다.

언어를 잘 사용하는 것도 물론 중요하지만,
그 내부 동작과 여러 Alg-/Dat-Str 간의 차이점을 이해하고 써야 의미가 있다.

범용적 절차 / 명령어 집합
어떤 일을 하기 위해 미리 만들어둔, 이미 만들어진 명령의 집합.
사실 모든 코드는 이런 의미에서 알고리듬.

데이터를 저장하고 조작하는 방법

초기
- 과거 기준: 실랜디
  - ~= 백준 골드2, ~= 클래스 5, 플머스 1~3
  - Bfs dfs, 위상정렬, 기초적인 자료구조 등
- 백준 Class 난이도 별로
후기
- 최근 기준: 골랜디
  - ~= 백준 플래, 플머스 >= 3, 넥토는 5도 보임
- 어떻게 푸는 지 바로 생각날 정도로, 외울 정도로, 어려운 게 있으면 더 풀고
- 프로그래머스: 42895, 기출
- 코드포스 (블루)

1:
- Q: 공부랑 실전 문제 괴리가 있음
- A: 코테 보는 곳 지원해서 경험 쌓기 or 대회
2:
- Q: 처음 보는 유형이나 잘 모르는 것
- A: 답 보기
  - 왜 이렇게 짰는지 이해가 가장 중요
  - 여러 번 돌려봐도 괜찮음
  - 잘 못 풀면 그 알고리듬 집중적으로 공부하면 돼
3:
- Q: 히든 케이스
  - 플머스/리트코드: 케이스 전부 공개
  - 실제: 히든 케이스
    - 예외 처리, 실수 -> 치명적
- A: 처음부터 설계 잘하고, 검증도 잘하기
4:
- Q: 환경
- A: HackerRank 해커랭크
  - 테스트 케이스 어디서 틀렸는지 보려고 프린트하면 안나오는데, return으로 그냥 값 넘겨주면 출력돼서 케이스 어떻게 나오는지 알 수 있다? (히든 케이스)
5:
- Q: 문제
- A: 6문제, 약 3시간 30분
  - 4.5솔 -> 위험

참고
- *: 강조
- !: 넥토 출현
- .: 넥토 출현 (불확실)
- \?: 크게 언급 없는 것 같은
분야: (바킹독)
- 못해도 11강, 그리디, 탐색 (완전 탐색/BFS/DFS), 그래프, DP, 백트래킹/시뮬레이션
- 좀 더? (크루스칼, 다익스트라/최소신장트리, 트라이)
하:
- 구현 & 자료구조:
  - C++ 자료구조-컨테이너
  - 해싱: Hash, Set, Map으로 간단히 풀 수 있는
  - 우선 순위 큐 .
  - 파싱, 스택, 힙, 트리
  - 문자열 조합/정렬 !
- 그 외 단골
  - 냅색
  - lis, lcs
  - 이분탐색 .
- 투포인터, 윈도우 슬라이드 !!.
- DFS/BFS ?.
- 시뮬레이션 (스택, 큐, 덱) ?
중
- 위상정렬
  - 노드와 엮을 수 있는 계층적 문제
- MST / 크루스칼 + 프림
- 그리디
- 백트래킹
상
- DP !!
  - 가끔 수학과 엮여서 출제
  - 거의 항상 나옴
- 트라이 / KMP
- 다익스트라
- 플로이드
모름
- 그래프 !!
  - 노드 같은거 섞인 최단경로 .
- 세그먼트 트리
- A*
X
- 라운드로빈 (스케쥴링)
- 삼항트리
22 넥토