코딩테스트 풀어왔던 문제 정리

지금까지 풀어왔던 문제들을 기록하는 공간입니다.

비슷한 문제를 모아보거나 제가 풀었던 것 중 어떤부분에서 주로 틀렸는지 기록용입니다.

 

색칠 = 다시 풀기 완료

★ = 추천 문제

 

백준(B)(https://www.acmicpc.net/)

프로그래머스(L)(https://programmers.co.kr/)

리트코드(L)(https://leetcode.com/)

---

특정 유형이 많은 알고리즘(우선순위)

- 완전탐색, 그래프(DFS/BFS), 해시테이블/문자열, 다익스트라

 

변수가 많아 많이 풀어봐야하는 알고리즘(후순위)

- 구현/시뮬레이션, 스택/큐, 우선순위큐, DP

 

유형별 출제 빈도

- 완탐

- 구현/시뮬레이션

- DFS/BFS

- 문자열/해시

- 힙/다익스트라

- DP 

---

DFS

B/실버2/연결 요소의 개수

B/실버2/dom

★ B/실버2/유기농 배추/인접 행렬 기초

★ B/실버1/단지번호 붙이기/탐색 기초

B/실버1/영역 구하기

B/골드5/적록색약

★ B/골드5/숫자고르기/인접 리스트 기초

B/골드4/알파벳

B/골드3/텀프로젝트/사이클을 찾는게 중요

 

- DFS를 써야할 때

인접리스트, 인접행렬 관련해서 나오면 대부분 해당한다.

DFS랑 BFS는 세트 느낌인데 대부분은 DFS를 먼저 생각하되,

가장 짧은 거리를 구하는 최단거리문제는 BFS가 유리하기 때문에

그런 경우는 BFS를 적용하고 나머지는 DFS부터 떠올려보자.

 

- DFS 좌표 도는 방향

애초에 좌표로 생각하지 말고 배열로만 생각해서 문제를 접근하자.

행은 i로 돌고 열은 j로 배열을 탐색하게 되는데, 여기서 dx[k]를 해주면

한칸 전 행을 돌기 때문에 12시 방향에 대한 탐색이 된다.

 

- 인접리스트, 인접행렬 크기

인접리스트는 노드 번호 그대로 주는 경우가 많아 크기 +1해주기,

인접행렬은 그대로 받기(out of index 범위 < 0, >=n)

 

- 인접리스트 만들 때 형식

ArrayList<ArrayList<Integer>> arr = new ArrayList<>();

 

 

---

BFS

B/실버2/촌수 계산

★ B/실버2/유기농 배추 / 풀이(Java)

★ B/실버1/나이트의 이동 / 풀이(Java)

★ B/실버1/미로 탐색 / 풀이(Java)

B/실버1/음식물 피하기

★ B/골드5/토마토 / 풀이(Java)

B/골드4/탈출 / 풀이(Java)

 

- 방문 체크하는 시점

q에서 꺼내면서 방문 체크를 하게되면

같은 q의 회차가 진행되면서 불필요 한 것들이

q에 들어가는 중복이 많이 발생하여

불필요한 연산, 메모리 낭비가 발생하기 때문에

q에 넣는 동시에 방문체크를 하는게 가장 좋다.(유기농 배추 풀이 참고)

---

문자열/해시

L/Easy/Two sum

L/Medium/Valid sudoku

L/Medium/Group Anagrams

 

---