🌸알고리즘
문제 해결을 위한 최선의 선택
최선의 선택을 찾는 방법?
- 문제에 대한 이해
- 전략 수립(슈도코드)
- 코드 구현
🍘의사 코드
프로그래밍 언어가 아닌 일상어로 코드를 흉내 내어 알고리즘을 써놓은 것
구현시 지표가 되며 디버깅에 용이, 소통 시에도 도움이 됨
자신만의 원칙을 가지고 일관성 있고 다른 사람도 이해할 수 있는 수도코드를 작성하도록 하자
🍙시간 복잡도
'시간 복잡도를 고려한다'란 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화 하겠다는 뜻
Big-O 표기법
Big-O(빅-오) : 이 정도 시간까지 걸릴 수 있다(최악을 가정)
Big-Ω(빅-오메가) : 평균을 가정
Big-θ(빅-세타): 최선을 가정
최악의 경우도 고려하여 대비하는 것이 바람직
O(1)
constant complexity
입력 값이 증가해도 시간이 증가하지 않는다
크기에 관계 없이 즉시 출력값을 반환한다
O(n)
linear complexity
입력 값이 증가하면 시간이 같은 비율로 증가한다
O(log n)
logarithmic complexity
O(1) 다음으로 빠르다
ex) 이진탐색(Binary Search)
O(n^2)
quadratic complexity
입력 값이 증가하면 시간이 n제곱의 비율로 증가
O(2^n)
exponential complexity
가장 느린 복잡도
ex) 피보나치 수열
입력 데이터가 크다면 시간 복잡도를 고려할것
입력 데이터가 작다면 시간 복잡도가 크더라도 해결하는 것에 집중할 것
- 1억을 기준으로 넘지 않도록 하자
O(n)/O(log n) n : 1,000,000
O(n2) n : 10,000 = 100,000,000
O(n3) n : 500 = 125,000,000
🥪탐욕 알고리즘
매 순간 최적이라 생각되는 해답을 찾아 최종 해답에 도달하는 문제 해결 방식
앞의 선택이 이후의 선택에 영향 주지 않을 때 적용하는 것이 바람직
🥘구현 - 시뮬레이션
조건을 하나도 빠트리지 않고, 마치 시뮬레이션을 하듯 구현 하는 것
중요한 것은 정확성과 속도
🥗브루트 포스 알고리즘
시행착오 방법론, 모든 값을 대입해 해답을 찾아냄
공간복잡도와 시간복잡도를 고려하지 않고 최악의 시나리오를 취하더라도 해결하
려는 방법
문제가 복잡해 질수록 비효율적인 알고리즘이 될 수 있다
다른 방법이 없을때나 문제에 대한 각 솔루션을 확인해야 할 때 사용
ex)
순차(선형) 검색(arr[0]~arr[arr.length-1]),
문열 매칭(문자열 패턴을 포함하는지를 검색),
선택 정렬(현재 요소보다 더 작거나 큰 요소를 교환하며 정렬)
🥐이진 탐색 알고리즘
시간복잡도는 O(logn)로, 빠른 편
규모가 클 수록 효과적
but 항상 효율이 좋은 것은 아님
양이 적고 데이터가 앞쪽에 위치시 선형 검색이 빠를 수 도 있다
배열에만 구현 가능하며 정렬되어 있어야 함
ex) 사전 검색, 도서관 도서 검색, 대규모 시스템 리소스 파악
- BST : 자료구조, BSA: 해결방법
🌸실습문제
Greedy 짐나르기
내가 푼 방법
public class Solution {
public int movingStuff(int[] stuff, int limit) {
// TODO: stuff는 상자에 들어갈 값을 가진 배열, limit는 2개 박스의 총 상한
List<Integer> stuffcopy = new ArrayList<>();
for (int num : stuff) {
stuffcopy.add(num);
}
//stuff를 stuffcopy로 리스트화
int countBox = 0;
stuffcopy.sort(Comparator.reverseOrder());
//내림차순 정렬
while (!stuffcopy.isEmpty()) {//리스트에 내용물이 있으면
int boxA = stuffcopy.get(0); //첫번째 배열을 A로 넣음
int remain = limit - boxA; //B가 들어갈 수 있는 공간 remain 계산
if (stuffcopy.size() == 1) {// 남은게 A하나에 들어갈꺼 뿐이면
stuffcopy.remove(0);
countBox++;//카운트 후 종료
return countBox;
}
boolean findBox = false;
int boxB = 0; // 초기값 설정
for (int i = 1; i < stuffcopy.size(); i++) { //boxB 찾기
if (stuffcopy.get(i) <= remain) {
boxB = i;
findBox = true;
break; // boxB를 찾으면 찾음 표시하고 반복문 종료, 없을경우 그냥 종료
}
}
if (findBox) {stuffcopy.remove(boxB);} // 찾음 표시면 boxB 제거
stuffcopy.remove(0);//boxA 제거
countBox++;
}
return countBox;
}
}reference에는 배열을 내림차순으로 정렬 한 다음 왼쪽과 오른쪽을 순회하며 가장 무거운것과 가벼운것의 합을 상한값과 비교하여 count했다
확실히 이러면 순회시간도 줄고하나 남았을 때와 2개일떄 무게가 초과 했을때의 조건문을 합치게 되어 조건문도 덜 쓰게 된다. 좋은 코드란 이런거겠지
Greedy 편의점 알바
이번 문제는 코플릿과 내 해답이 거의 유사했다
다만 코플릿에서는 나눌때는 double로 형변환을 제대로 해 주고 있었다
기본적이지만 자주 놓치는 부분이다. 잊지 않도록 하자
보드게임 구현
public Integer boardGame(int[][] board, String operation) {
int W = 0; // 가로
int L = 0; // 세로
int sum = 0;
String[] move = operation.split(""); // 1부터 움직이기
for (int i = 0; i < move.length; i++) {
if (move[i].equals("R")) {
W++;
} else if (move[i].equals("L")) {
W--;
} else if (move[i].equals("U")) {
L--;
} else if (move[i].equals("D")) {
L++;
}
if (L + 1 > board.length || L < 0 || W + 1 > board[0].length || W < 0) {
return null;
}
sum += board[L][W];
}
return sum;
}코플릿에선 HashMap 내에 int[]를 넣어 X,Y좌표를 가진 객체로 구현해 사용하고 있었다
전체적인 코드는 내가 더 간결했지만 정확성 면에선 더 유리해 보였다
(Advanced) 금고를 털어라
풀다가 너무 어려워서 해설을 봤다
해설도 어렵다
결국 핵심은 bag[j] += bag[j - type[i]]
type이 바뀔 때 마다 type이 만들수 있는 경우의 수를 합산해 증가시킴
taget+1 크기의 배열을 만들어서 마지막 인덱스 값(taget)은
결과적으로 경우의 수가 가장 많이 누적된 목표에 대한 최종 합산값이 됨
