알고리즘 문제풀이
알고리즘 문제풀이
참고: https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard
1. 문자열
- Scanner next() vs nextLine()
- String nextLine() : '\n'을 포함하는 한 라인을 읽고, '\n' 버린 나머지만 리턴
- String next() : 다음 토큰을 문자열로 리턴
- 문자열 Split
- String[] splited = input.split(" ")
2. 배열
- 에라토스테네스의 체
- O(n^(1/2))로 소수 판별하기
- for문으로 i= 2~n^(1/2) 까지 돌면서 % 연산으로 소수 판별
- 배열 정렬하기
- Arrays.sort(array) : Primitive Type이라면 그냥 써도 ㄱㅊ (오름차순)
- Arrays.sort(array, Collections.reverseOrder()) : 내림차순 등의 역순 정렬하려면 Reference Type이여야함!
3. Two Pointers, Sliding Window
- 배열 중 하나의 원소부터 몇 개까지 어떻게 하라!
- 투 포인터/슬라이딩 윈도우
- lt, rt 잡기
- rt for문으로 늘려가기
- lt 늘릴 조건 만나면 while로 따라잡기
- 임시 변수/현재 답 철저히 마킹하기
for(int rt=0; rt < number; rt++) {
sum += numbers[rt];
if (sum == targetNum) answer++;
while (sum > targetNum) {
sum -= numbers[lt];
lt++;
if (sum == targetNum) answer++;
}
}
- List 정렬하기
- Collections.sort(list) : 오름차순
- Collections.sort(list, Collections.reverseOrder()) : 내림차순
- 이중 for 문으로 모든 경우의 수 따질 땐 Sliding Window를 생각해보자!
- 참고: https://www.acmicpc.net/problem/1644
- 2, 3, 5, 7 중 연속된 숫자의 합 구하기
- 2 골라서 ... 2-3, 2-3-5, 2-3-5-7
- 3 골라서 ... 3-5, 3-5-7
- 그러지 말고! Sliding window로 O(n)에 끝내자!
- 2-3-5 쭉쭉 targetNumber 만날때 까지
- targetNumber 만나면 뒤에서 부터 삭제!
4. HashMap, TreeSet
- Map 초기화시 getOrDefault()쓰기
- 정렬의 기능가진 Set이 필요하다면 TreeSet 쓰기
- Map 순회방법
Map<Integer, Integer> map = new HashMap<>();
for(Integer i : map.keySet()) {
map.get(i);
}
- Set 순회방법
- 그냥 향상된 for문 쓰면 됨
Set<Integer> set = new HashSet<>();
for(Integer i : set) {
System.out.println(i);
}
- HashMap과 HashMap 비교
- hashmap.equals(hashmap)
- 정확히 똑같은 key-value 쌍의 같은 사이즈의 Map이라면 참을 반환
5. Stack, Queue
- Stack 선언
- Stack stack = new Stack<>();
- Queue 선언
- Queue queue = new LinkedList<>();
- Character -> Integer
- Character.getNumericValue()
6. Sorting & Searching
- LinkedList에만 있는 기능
- linkedList.removeLast()
- linkedList.addFirst(item)
- List 중간에 원소 넣기
- List add(int index, E element)
- 정렬시켜 비교하는게 빠른 문제도 있어!
- 그냥 O(nlogn) 으로 정렬시키고 뚝딱 O(n)으로 비교하기
- 이분탐색 / 결정 알고리즘
- 정렬이 되어있고, 특정 범위 내에서 답이 있으리라 판단되면 이분탐색하자!
- lt, rt, mid 잡고 O(logN)으로 탐색 빠르게 진행
- ex. 조건을 만족시킬 수 있는 X를 구하는데, X의 최대값은 뭘까요?
- 우선 탐색할 구간 lt = min, rt = max, mid = 중간으로 잡기
- mid를 가지고 해당 조건이 만족 되는지를 검사
- 만족이 되는 경우, 안 되는 경우 나눠서 lt/rt를 어찌 조정할지 생각
- lt <= rt의 조건이 깨진다면 기록해둔 답을 반환!
7. Recursion, Tree, Graph (DFS/BFS 기초)
- DFS : static 변수에 저장하라 (모든 경우 탐색)
- static 배열/변수에 현재 상태등을 저장하며 재귀를 돌려라
- BFS : Layer, Size, for문, Queue (최단거리/최소횟수 탐색)
- BFS 과정에서 방문했는지 검사하는 check[] 배열은 필수야!
8. DFS/BFS 활용
- DFS : static 활용하기!
- static 배열/변수에 메모이제이션
- static flag 만들어 바로 return 때릴 준비하기
- 순열과 조합
- 순열 : 순서 상관있이 선택, 반장/부반장 선출, nPr = n!/(n-r)!
- 조합 : 순서 상관없이 선택, 대표 2명 선출, nCr = n!/(n-r)!r!
- 팩토리얼 미리 구해두고 구하는 것도 좋은 방법!
- DFS로 순열과 조합 구하기
- 순열 : for 그냥 돌고 -> for 시작부터 다시 돌고 선출!
- 조합 : for 그냥 돌고 -> for index + 1부터 돌고 선출!
- 2차원 배열로 영역 표시
- 지도와 같은 문제!
- x, y 좌표평면이랑 2차원 배열 다른거야!
- 제발 깝치지 말고 그냥 그린 다음에 시작해!
9. 그리디 알고리즘
- 정렬과 Count의 미학
- Greedy하게 정렬하고, 조건에 맞게 Count할 것!
- 누가 뽑히는지가 안 중요하고, 몇 명 뽑혔는가가 중요한 경우인지 살펴볼 것!
- 다익스트라 알고리즘
- 간선의 가중치가 모두 0 이상인 경우 사용
- PQ를 활용하면 한 점으로부터 각 점까지의 최소 간선거리 구할 수 있음
- Union & Find
- 그래프의 Root Parent를 기록해두자!
- Union의 과정에서 양쪽 다 Parent를 찾은 후에 Root를 바꿔주자!
public static int getParent(int student) {
if (student == studentParent[student]) {
return student;
} else {
return getParent(studentParent[student]);
}
}
public static void makeParentship(int student1, int student2) {
int parent1 = getParent(student1);
int parent2 = getParent(student2);
studentParent[parent1] = parent2;
}
- 최소 스패닝 트리
- 싸이클이 없는 최소 간선으로 모두를 이어준 트리
- Kruskal Algorithm : 작은 간선 순으로 정렬 -> Union & Find로 Cycle 검사하며 더하기
- Prim's Algorithm : 연결리스트로 트리 넣어두기 -> Check 배열에 방문여부 나타내기 -> 방문한 곳 기점 PQ에 최소 간선 순으로 넣어두기
- 다익스트라 알고리즘
- 다익스트라의 경우 간선의 가중치가 모두 0 이상일 때만 사용가능!
- 다익스트라 사고의 흐름
- 1번부터 갈 수 있는 점까지의 최소 거리인 dis[] 배열을 만든다.
- dis[1] = 0
- dis 배열을 돌면서 최소값을 가진 index를 찾는다
- 해당 index 에서 갈 수 있는 정점에 대해 가중치 갱신
- dis[1~6] = [0, 12, 4, Max, Max, Max];
- dis 배열을 돌면서 최소값을 가진 index를 찾는다
- 해당 index 에서 갈 수 있는 정점에 대해 가중치 갱신 (최소값 부터 양수의 간선값을 더해가니 무조건 최솟값)
- dis[1~6] = [0, 11, 4, 9, Max, Max];
- dis 배열을 돌면서 최소값을 가진 index를 찾는다
- 해당 index 에서 갈 수 있는 정점에 대해 가중치 갱신
- dis[1~6] = [0, 11, 4, 9, 14, Max];
- O(정점 * 간선)
10. DP
- 테이블로 기억하기 프로그래밍
- 하나의 기준을 가지고 테이블을 만들어두자
- ex. dy[i] = i분까지 얻을 수 있는 최대의 점수, i원을 만드는데 드는 최소의 동전 갯수
- 작은 문제들을 풀어두고 값을 저장해뒀다가 재사용하는 방식
- 문제를 범위를 작게 만들어서 그걸 해결한다.
- 앞선 문제를 레버리지 삼아 뒤에 문제를 해결한다.
- 더 좋은 방법으로 갱신하기
- DFS O(2^n) -> DP O(n^2)
- 첫번째 for는 고려해야할 조건 (ex. 동전의 갯수, 문제 풀이에 걸리는 시간)
- 조건이 유한하다면 : 두번째 for는 뒤 -> 앞
- 조건이 무한하다면 : 두번째 for는 앞 -> 뒤
- 두번째 for는 과거의 테이블 돌면서 활용하는 것!
- 두번째 for가 끝나고 뒤에 값을 채워줘야하는지 검사해볼 것
- ex. 조건이 연속된 것이 아니라면, 연속될 수 있도록 0이 아닌 다른 값으로 채워줘야 할수도!
- DP 문제 접근법
- 필요시 문제 풀이에 유리하게 정렬한다
- 조건을 간략화해서 생각해본다
- 이 블럭이 마지막 벽돌이라고 하면 높이는?
- 이게 마지막 수라고 하면 최대 부분수열의 길이는?
- 이게 유일한 동전이라면
- 2중 for문 돌면서 if 조건과 함께 값을 max/min 찾기
- 시간 여유가 있다면 sout으로 배열 값 다 찍어보기!
TIPS
- import java.util.* <- 써놓고 시작하기
- 시간 여유가 된다면 제발 System.out.println 배열 다 찍어보기!
- Integer 객체 비교는 .equals() 로 해야해!!
== 는 캐싱된거만 되는거 까먹지 말자!
- 진수 변환은 다음과 같이!
- Integer.toString(number, radix);
- String -> 숫자는 "Long"으로 변환하는게 안전할 수도!
- Integer가 오버플로우 나는 짜치는 상황 막자!
- 전역 변수 초기화는 함수 내부에서!
- BFS, DFS 배열 돌때 등호 꼭 붙였나 확인할 것!
- String.contains(string) 할 때, String keys 붙인거라면 개별적으로도 봐야할 수 있음
- 초과/미만 계산할때 0 부터라는 조건이 있으면 -1 부터 정수화 시키는거 유념
- 코드 런타임 에러나면...
- 리스트나 배열의 0, 1번째 원소 가져오는데 원소가 총 한 개 짜리는 아닌지
- 접근하려는 리스트가 Null 인건 아닌지!
- 손코딩, 경계값 테스팅 코드 짜기 전에 꼼꼼히 해보자!
- 투포인터로 누적합 하나씩 빼고 더 해갈때 헷갈리니까 이렇게 해보자
for (int i = 0, j=advSec; j< ptSec; i++, j++) {
long nowScore = adScore - secondRecord[i] + secondRecord[j];
if (maxScore < nowScore) {
adStartTime = i + 1;
maxScore = nowScore;
}
adScore = nowScore;
}
- 조합의 수를 줄일 수 있다면 줄이는게 베스트! 문제를 잘 읽고, 가능성이 없는 조합은 굳이 만들지 말자!
- 조건을 잘 읽자 조건을 잘 읽자 조건을 잘 읽자!!!!!!!!!!!!