알고리즘 요약

부루트 포스 완전 탐색 알고리즘 

- 풀이 방법 

1. for /while 루프를 사용 

2. 재귀함수(조금 더 복잡한 문제에서 사용)

- 추천문제 

프로그래머스 소수찾기 

프로그래머스

프로그래머스 모의고사 

프로그래머스

 

DFS BFS 깊이 너비 우선탐색 알고리즘 

- 정의 

1. 드라마 볼 때 하나를 몰아본다 == dfs

2. 여러개를 하나씩 본다 == bfs 

- 대표적 문제 유형 

1. 경로탐색 유형(최단거리, 시간)

2. 네트워크 유형(연결)

3. 조합 유형(모든 조합 만들기)

- 구현방법 

1.  dfs: 재귀함수 

2. bfs: 큐, LinkedList사용 

- 추천문제 

프로그래머스

- 어떤 거 쓸까 

어려운 문제 느낌이면 bfs(시간복잡도가 상대적으로 낮음)

쉬운 문제 느낌이면 dfs(검증 쉬움, 시간초과 복불복인 점 고려)

 

해시 HASH 알고리즘 

- 개념 

key(검색어):value(검색어로 나온 결과) 형태를 갖는 자료구조 

- 장점 

모든 데이터 타입으로 접근이 가능하다 

스트링의 경우 단순 배열을 쓸 수 없다는 단점을 보완 

- 알아야하는 것 

get / put / getOrDefault 

- 해시 유형 알아보는 법 

string을 기반으로 정보를 기록하고 관리해야 할 때 

- 추천문제 

프로그래머스 완주하지 못한 선수 

프로그래머스

프로그래머스 위장 

프로그래머스

- 정리 

1. hash는 전화번호부와 같다 

2. 대부분 그 key가 string이다 

3. put/get/getOrDefault  로 다 풀린다 

 

스트링 String 알고리즘 

- 추천 문제

네카라 코딩테스트 중 1번으로 출제된 문자열 문제 

 

DP동적계획 다이나믹 프로그래밍 알고리즘(기억하기 알고리즘)

- 설명 

메모리를 사용해서 중복 연산을 줄이고 중복 연산을 줄여서 수행 속도를 개선한다 

메모리를 사용한다 = 배열 혹은 자료구조를 만든다 

중복 연산을 줄인다 = 연산한 결과를 배열에 담는다 

- dp문제인지 알아보는 법 

1. dfs/bfs로 풀 수 있지만 경우의 수가 너무 많은 문제 

2. 경우의 수에 중복계산이 많은 경우 

- 푸는 법 

1. 직접 손으로 해보면서 패턴 찾기

규칙을 갖춘 수학 식을 도출하기 -> 완탐 안되는지 확인하면 dp로 풀기 

2. 최대한 많이 풀기 

30분 안에 답 안 나오면 풀이 참고해서 구현만 해보기 

그 30분 동안은 어떻게 하면 뒤로 돌아가지 않을 수 있을까를 고민하기 

나만의 자료구조를 만들고 어떤 정보를 담아야 이전 단계로 돌아가지 않을지 고민하기 

 

출처: 개발자로 취직하기 유튜브 채널