[코테공부 5/23] 프로그래머스 시작

01. 문제분석 연습하기

1. 문제를 쪼개서 분석하기 (동작 단위로)

2. 제약사항 파악하고 테스트 케이스 추가하기

3. 입력값 분석하기 (시간복잡도)

4. 핵심키워드 파악하기

   "최적의 해" 너비우선 탐색
   "정렬된 상태의 데이터" 이진탐색, 파라메트릭 탐색
   "최단경로" 다익스트라, 벨만포드, 플로이드워셜

   정리
   스택 (쌍이 맞는지, 최근)
   큐 (순서대로, ~대로 동작하는 경우, 스케줄링, 최소시간)
   깊이우선탐색 (모든경로)
   너비우선탐색 (최적, 레벨순회, 최소단계, 네트워크 전파)
   백트래킹 (조합, 순열, 부분집합)
   최단경로 (최단경로, 최소시간, 최소비용, 트래픽, 음의 순환, 단일출발점 경로)

5. 데이터의 흐름이나 구성을 파악하기

02. 의사코드 설계 연습하기

프로그래밍 언어로 작성X
자연어로 작성
일정한 형식은 없음

1. 세부 구현이 아닌 동작 중심으로 작성하기
2. 문제해결 순서로 작성하기(분기점 파악)
3. 충분히 테스트하기

03. 알고리즘의 효율 분석

시간복잡도?

1. 정의: 알고리즘의 성능을 나타내는 지표, 입력 크기에 대한 연산 횟수의 상한
2. 측정방법: 연산횟수
3. 최대연산횟수
   • O(N!): 10회
   • O(2(n승)): 20-25회
   • O(N(3승)): 200-300회
   • O(N(2승)): 3000-5000회
   • O(NlogN): 100만
   • O(N): 1000-2000만
   • O(logN): 10억

04. 노하우

1. 조기반환: return 2번 이상 사용
2. 보호구문: 예외처리 코드 추가하는 기법 -> 없으면 그냥 None return
3. 합성함수: 2개 이상의 함수 사용, 람다식 활용

출처 : 코딩테스트 합격자되기 - 파이썬편