AIFFEL 대전 - 파이썬 알고리즘 인터뷰

AIFFEL 대전의 퍼실끼리 파이썬 알고리즘 인터뷰의 문제들을 스터디하고 정리하였습니다.

스터디 방식

1. 각자 맡은 문제를 공부한다.
2. 풀이 코드에서 설명이 부족한 부분에 주석을 추가하여 깃헙에 공유한다.
3. 스터디에서 깃헙에 공유한 내용을 토대로 팀원들에게 설명한다.

1학기 (자료구조)

4장. 빅오, 자료형 이론

(생략)

6장. 문자열 조작

Prob 1. 유효한 팰린드롬

• Sol 1. 리스트로 변환
• Sol 2. 데크 자료형을 이용한 최적화
• Sol 3. 슬라이싱 사용
• Sol 4. C 구현(생략)

Prob 2. 문자열 뒤집기

• Sol 1. 투 포인터를 이용한 스왑
• Sol 2. 파이썬다운 방식

Prob 3. 로그 파일 재정렬

• Sol 1. 람다와 +연산자를 이용

Prob 4. 가장 흔한 단어

• Sol 1. 리스트 컴프리헨션, Counter 객체 사용

Prob 5. 그룹 애너그램

• Sol 1. 정렬하여 딕셔너리에 추가
• Sol 2. set을 이용(커스텀)

Prob 6. 가장 긴 팰린드롬 부분 문자열

• Sol 1. 중앙을 중심으로 확장하는 풀이

7장. 배열

Prob 7. 두 수의 합

• Sol 1. 브루트 포스로 계산
• Sol 2. in을 이용한 탐색
• Sol 3. 첫번째 수를 뺸 결과 키 조회
• Sol 4. 조회 구조 개선
• Sol 4. 투 포인터 이용(커스텀)

Prob 8. 빗물 트래핑

• Sol 1. 투 포인터를 최대로 이동
• Sol 2. 스택 쌓기

Prob 9. 세 수의 합

• Sol 1. 브루트 포스로 계산
• Sol 2. 투 포인터로 합 계산

Prob 10. 배열 파티션 1

• Sol 1. 오름차순 풀이
• Sol 2. 짝수 번째 값 계산
• Sol 3. 파이썬다운 방식

Prob 11. 자신을 제외한 배열의 곱

• Sol 1. 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈

Prob 12. 주식을 사고팔기 가장 좋은 시점

• sol 1. 브루트 포스로 계산
• sol 2. 저점과 현재 값과의 차이 계산
• sol 3. 커스텀

8장. 연결 리스트

Prob 13. 팰린드롬 연결 리스트

• Sol 1. 리스트 변환
• Sol 2. 데크를 이용한 최적화
• Sol 3. 고(Go)를 이용한 데크 구현(생략)
• Sol 4. 런너를 이용한 우아한 풀이

Prob 14. 두 정렬 리스트의 병합

• Sol 1. 재귀 구조와 연결

Prob 15. 역순 연결 리스트

• Sol 1. 재귀 구조로 뒤집기
• Sol 2. 반복 구조로 뒤집기

Prob 16. 두 수의 덧셈

• Sol 1. 자료형 변환
• Sol 2. 전가산기 구현

Prob 18. 홀짝 연결 리스트

• Sol 1. 반복 구조로 홀짝 노드 처리

Prob 19. 역순 연결 리스트 2

• Sol 1. 반복 구조로 노드 뒤집기

9장. 스택, 큐

Prob 20. 유효한 괄호

• Sol 1. 스택 일치 여부 판별

Prob 21. 중복 문자 제거

• Sol 1. 재귀를 이용한 분리
• Sol 2. 스택을 이용한 문자 제거

Prob 22. 일일 온도

• Sol 1. 스택 값 비교

Prob 23. 큐를 이용한 스택 구현

• Sol 1. push()할 때 큐를 이용해 재정렬

Prob 24. 스택을 이용한 큐 구현

• Sol 1. 스택 2개 사용

Prob 25. 원형 큐 디자인

• Sol 1. 배열을 이용한 풀이

10장. 데크, 우선순위 큐

Prob 26. 원형 에크 디자인

• Sol 1. 이중 연결 리스트를 이용한 데크 구현

Prob 27. k개 정렬 리스트 병합

• Sol 1. 우선순위 큐를 이용한 리스트 병합

11장. 해시 테이블

Prob 28. 해시맵 디자인

• Sol 1. 개별 체이닝 방식을 이용한 해시 테이블 구현

Prob 29. 보석과 돌

• Sol 1. 해시 테이블을 이용한 풀이
• Sol 2. defaultdict를 이용한 비교 생략
• Sol 3. Counter로 계산 생략
• Sol 4. 파이썬다운 방식

Prob 30. 중복 문자 없는 가장 긴 부분 문자열

Prob 31. 상위 K 빈도 요소

• Sol 1. Counter를 이용한 음수 순 추출
• Sol 2. 파이썬다운 방식

12장. 그래프

Prob 32. 섬의 개수

Prob 33. 전화 번호 문자 조합

• Sol 1. 모든 조합 탐색

Prob 34. 순열

• Sol 1. DFS를 활용한 순열 생성
• Sol 2. itertools 모듈 사용

Prob 35. 조합

Prob 36. 조합의 합

• Sol 1. DFS로 중복 조합 그래프 탐색

Prob 37. 부분 집합

• Sol 1. 트리의 모든 DFS 결과

Prob 38. 일정 재구성

Prob 39. 코스 스케줄