2023.12.15(금) TIL

quinones·2023년 12월 18일

코딩 테스트를 준비하며 매일매일 programmers에서 문제를 풀고있다.

보통 코딩테스트에서 가장 많이 나오는 종류의 알고리즘들을 정리해봤다.

1. DFS/BFS

깊이우선탐색/너비우선탐색 알고리즘이다. 어떻게 풀어도 결과값은 둘다 같다.
DFS는 보통 재귀함수를 이용해서 풀고, BFS는 que를 사용해서 풀어주면된다.

연습 문제
타겟넘버
https://school.programmers.co.kr/learn/courses/30/lessons/43165
네트워크
https://school.programmers.co.kr/learn/courses/30/lessons/43162
단어 변환
https://school.programmers.co.kr/learn/courses/30/lessons/43163
여행경로
https://school.programmers.co.kr/learn/courses/30/lessons/43164

2. 문자열+기타 알고리즘

문자열에 관해서는 관련된 함수를 알아두면 편하다.

equals - 두String이 같은지 판단하는 함수
length - String의 길이를 반환하는 함수
toUpperCase - 대문자로 변환하는 함수
toLowerCase - 소문자로 변환하는 함수
indexOf - 문자열 내에 다른 문자열이 존재하는지 판단, 해당인덱스를 가져오기
substring - "Hello".substring(1,3) -> "el"
replace - "Hello".replace("l", "") -> "He o"
trim - 앞뒤 공백제거
compareTo - 두 문자열의 아스키 순서를 알려줌 - 알파벳 순서 알려줌.
ex) "b".compareTo("a") -> (+)
charAt - 원하는부분을 꺼내옴. -> "Hello".charAt(2) = "l"

연습문제
신고 결과 받기(이건 Hash알아야지 가능)
https://school.programmers.co.kr/learn/courses/30/lessons/92334

-- > 결론은 다른 알고리즘들이랑 섞여서 나오니 전부 알아야 한다.

단순구현

단순 구현 문제이다.

연습문제
다음에 올 숫자
https://school.programmers.co.kr/learn/courses/30/lessons/120924
콜라 문제
https://school.programmers.co.kr/learn/courses/30/lessons/132267
숫자 카드 나누기 https://school.programmers.co.kr/learn/courses/30/lessons/135807

완전탐색

브루트포스 알고리즘 이라고도 불린다. 무식하게 처음부터 끝까지 모든 경우의 수를 찾아줘야 하는 알고리즘 이다.

연습문제
모의고사
https://school.programmers.co.kr/learn/courses/30/lessons/42840
소수찾기
https://school.programmers.co.kr/learn/courses/30/lessons/42839

해시

key:Value로 구분된다.
전화번호부로 예를 들어보면 이름을 검색하면 그사람의 전화번호가 나온다.
여기서 이름-Key 전화번호-Value라고 생각해주면 편하다.

연습문제
완주하지 못한 선수 (선수이름:String 완주결과:boolean)
https://school.programmers.co.kr/learn/courses/30/lessons/42576
신고 결과 받기(신고반은사람:String, ArrayList)
https://school.programmers.co.kr/learn/courses/30/lessons/92334
의상(String키, int벨류)
https://school.programmers.co.kr/learn/courses/30/lessons/42578

다이나믹프로그래밍(DP)

완전탐색, DFS, BFS처럼 수많은 경우의 수를 따져봐야하는데 경우의 수가 너무 많아 속도가 너무 느려질때 수행시간을 개선시키기 위한 알고리즘이다.

목적 - 메모리를 사용해서 중복 연산을 줄이고 중복연산을 줄여서 수행속도를 개선한다.
여기서 메모리를 사용한다-또하나의 배열 혹은 자료구조를 만든다
중복연산을 줄인다-연산한 결과를 배열에 담는다

연습문제
정수 삼각형
https://school.programmers.co.kr/learn/courses/30/lessons/43105

재귀함수

-반복문.

큐,스택

자료구조.
큐-FIFO(First In First Out)
스택 - FILO(First In Last Out)
형태이다.

그리디

미래를 고려하지 않고 오직 현재 시점에서 가장 좋은 선택을 하는 알고리즘.
현재 선택이 미래에 영향을 주지 않는다 라는 조건이 필요함.
ex)

서울에서 대전을 거쳐 부산을 가는데 최단거리로 가고싶다.
서울에서 대전을 가는데 3가지 길이 있고, 이 선택이 대전에서 부산을 가는데 영향을 끼치지 않기 때문에 최단거리만 구해주면 된다.