공부하는 스누피

(참고) www.geeksforgeeks.org/window-sliding-technique/ Window Sliding Technique - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org 슬라이딩 윈도우 기법 슬라이딩 윈도우 기법은 시간 복잡도를 줄이기 위해 중첩된 반복문을 어떻게 단일 반복문으로 바꿀 수 있는지..

퀵 정렬이란? Quick sort는 Divide and Conquer 알고리즘으로, 평균적으로 매우 빠른 수행 속도를 보여준다. 시간복잡도가 O(NlogN)으로 Merge sort와 동일하지만, 배열을 균등하지 않게 분할하고 추가적인 메모리 공간을 필요로 하지 않는다. 빠르고 메모리도 덜 차지하지만 pivot을 잘못 설정했을 경우, 최악의 경우에는 시간복잡도가 O(N^2)으로 다른 비효율적인 정렬 알고리즘보다 나은 것이 없다. 그래서 pivot의 위치에 큰 영향을 받지 않는 배열에 적합하다. pivot은 배열을 분할하는 기준점으로, pivot으로 나눠진 두 배열의 원소를 순서대로 꺼내 비교하면서 정렬한다. 원리 배열을 정렬하려면 먼저 3가지 변수를 설정해 두어야 한다. left: 배열 맨 왼쪽 인덱스. ..

합병 정렬이란? 합병 정렬(Merge sort)는 정렬 알고리즘으로, 주어진 배열을 두 개의 배열로 계속 분할한 뒤, 분할한 배열을 합치면서 정렬한다. 배열을 분할하는 과정에서 시간 복잡도 O(logN), 합치는 과정에서 O(N)을 가지므로 총 O(NlogN)의 시간 복잡도를 가진다. Quick sort, Heap sort처럼 시간 복잡도가 O(NlogN)이지만, 정렬을 위한 배열을 하나 더 생성하기 때문에 메모리를 더 많이 차지한다는 단점이 있다. 원리 배열 [4, 3, 2, 1]이 있고, 오름 차순으로 정렬한다고 해 보자. Merge sort는 분할을 먼저 수행하는데, 더 이상 나눠지지 않을 때까지 배열을 나눈다. 0: [4, 3, 2, 1] 1: [4, 3] [2, 1] 2: [4] [3] [2] ..

https://programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 생각과정 - 딕셔너리를 만들어 새로운 문자 패턴을 저장한다. - 주어진 문자열을 순회하면서 현재 입력된 문자가 딕셔너리에 있는지 확인하고, 없으면 추가한다. - 현재 입력된 문자의 다음 문자가 딕셔너리에 있는지 확인하고, 없으면 추가한다. 이때 현재 입력 문자에 다음 문자를 더한 패턴도 딕셔너리에 추가하고 다음 반복으로 바로 넘어간다. ex) 현재:A 다음:B일때, B가 딕셔너리에 없..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 생각과정 - n이 1일 경우 0, 2일 경우 1, 3일 경우 1번의 연산으로 1을 만들 수 있다. - 일차원 배열을 만들어 인덱스값에 대한 최소 연산 횟수를 저장한다. - 4부터 n까지 순회하면서 최솟값을 구한다. (Bottom-Up 방식) - 먼저 3이나 2로 나누어 떨어지는지 확인한다. 나누어 떨어진다면, n/3 또는 n/2의 값에서 1을 더한 값을 배열에 저장한다. 앞에서 n/3의 최솟값을 구해 놓았으니 1을 더하기만 하면 된다. - 1을 빼는 연산은 2나 3으로 나누어 떨어지지 않을 때 수행하거나, 앞의..

https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 �� programmers.co.kr 생각과정 - pre-processing: 장르에 노래 배열을 담는 딕셔너리, 장르에 총 재생횟수를 담는 딕셔너리를 만든다. - 장르에 속한 노래별로 정렬한다. 재생횟수가 같으면 노래 ID로 정렬한다. - 장르끼리 정렬한다. - 정렬된 순으로 장르별 Top2를 추가한다. 구현 import operator def solution(genres, plays): ..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 생각과정 - 피보나치를 재귀 함수로 구현했을 때, 리턴값이 0 또는 1이 되는 횟수를 각각 출력해야 한다. - 시간 절약을 위해 Bottom-up DP를 선택. - n 값이 0일 때, 0 개수는 1, 1 개수는 0이다. - n 값이 1일 때, 0 개수는 0, 1 개수는 1로 출력된다. - 피보나치 함수는 n이 실행되면 n-1, n-2 함수를 각각 실행시키기 때문에 n 값이 2일 때 0과 1의 개수는 각각 n-1번째 값과 n-2번째 값을 더한 것과 같다. - 초기값 0, 1은 메모 배열에서 미리..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 생각과정 - 팀원이 추가될 때마다 기존 팀원들과 추가된 팀원 상호간 더해지는 능력치를 추가 - 팀 구성이 완료되면 능력치 차이 최솟값 구하기 (dfs) 구현 package baekjoon; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class b14889 { public int minA = Integer.MAX_..