거창한 시작

알고리즘 종류 - 탐욕 - 정렬 사고 과정 - 아무 생각이 없다... - 방법을 찾아보자 1. 추들을 오름차순으로 정렬한다. 2. 추에서 무게가 1인 추가 없으면 무게 1을 만들 수 없다. 3. 추의 무게를 오름차순으로 누적할 때, sum(누적합)+1보다 다음 추의 무게가 크다면 sum+1 무게를 만들 수 없다. 이 블로그의 도움을 받았습니다. 깔끔한 설명이 있습니다. 3-1. sum의 의미: 1부터 sum까지 무게를 만들 수 있다는 의미이다. 아래 그림을 보자. sum이 4일 때, (4 = 2+1+1), (3 = 2 + 1)로 만들 수 있다. sum이 13일 때, (12 = 6+3+2+1), (11 = 6+3+2), (10 = 6+3+1), ... 만들 수 있다. 3-2. sum + 1 < 입력 값의 ..

알고리즘 종류 - MST 사고 과정 1. 섬에 번호를 표시합니다. 2. 각 섬의 격자에서 연결 가능한 다리를 모두 구합니다. 2-1. 이중 for문으로 땅에서 4방향으로 뻗어서 다른 섬에 닿으면 연결된 섬과 거리를 저장합니다. 3, Kruskal 알고리즘을 사용합니다. 3-1. 다리가 저장된 벡터를 거리 오름차순으로 정렬합니다. 3-2. 하나 씩 꺼내서 최소 연결 다리를 만듭니다. 4. 모든 섬이 연결되었는지 확인합니다. 4-1. Union-Find 알고리즘에서 Find을 이용해서 부모가 모두 동일하면 섬이 모두 연결되었습니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 3..

알고리즘 종류 - 이분탐색 사고 과정 - 입력된 값을 저장된 배열의 원소들과 비교해서 배열에 넣기 1. 입력 값 받기 2. 입력 값이 배열에서 가장 큰 값보다 크면 배열 끝에 그냥 넣기 3. 입력 값이 배열에서 가장 큰 값보다 작거나 같으면 배열 내부의 원소들과 비교 3-1. 이분 탐색을 이용해서 입력 값보다 큰 값이 처음으로 나타나는 위치를 찾는다. 3-2. 위치에 입력 값을 대체해서 넣어 준다. 4. 배열은 가장 증가하는 원소들만 보여있기 때문에 배열의 크기가 가장 증가하는 부분 수열이다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 ..

알고리즘 종류 - Two pointers 사고 과정 - 기본적인 투 포인터 알고리즘 사용 1. 합보다 크거나 같으면 길이 갱신하고 왼쪽 포인터 옮기기 2. 합보다 작으면 오른쪽 포인터 옮기기 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include using namespace std; int n, s; int arr[100001]; int main(void){ cin >> n >> s; for(int i=0; i> arr[i]; } int left=0, right=0; int sum = arr[0]; int answer = 987654321..

알고리즘 종류 - 구현 - 브루트포스 사고 과정 1. 순열조합으로 타자의 순서 정하기 2. 각 조합에 따라 점수 구하기 조건 1. 3 아웃이면 이닝 종료 조건 2. 타순은 한 이닝이 끝나면, 다음 이닝에서 계속 이어짐 조건 3. 안타면 모든 선수 1칸 이동, 2루타면 모든 선수 2칸 이동, ... 3. 각 조합의 모든 이닝이 끝나면 다른 조합의 결과와 점수 비교하여 최고 점수 저장 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 6..

알고리즘 종류 - 최단거리 - Dijkstra 사고 과정 - 방법 1 1. Dijkstra를 n번하여 구하는 방법 2. i 번째 정점에서 모든 정점으로 가는 최단 거리 구하기 3. n 번째까지 구한 뒤, 최단 거리가 저장된 배열에서 최대 이동 거리 구하기 - 방법 2 1. 모든 정점 => x 정점 => 모든 정점 으로 구하는 방법 2. x 정점 => 모든 정점으로 가는 최단 거리는 입력된 그래프 그대로 사용하여 Dijkstra 사용 3. 모든 정점 => x 정점으로 가는 최단 거리는 입력된 그래프의 방향을 거꾸로 하여 Dijkstra 사용 구현(C++) - 방법 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ..

알고리즘 종류 - 문자열 - 스택 사고 과정 1. 문자를 넣을 배열(stack)을 생성합니다. 2. stack에 입력된 문자열의 문자를 하나씩 넣습니다. 3. 넣은 문자와 문자열 폭탄의 꼬리와 비교합니다. 4. 비교하여 같은 문자면, index를 뒤로 옮기면서 문자열 폭탄과 같은지 확인합니다. 5. 2~4 과정을 반복합니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include #include using namespace std; char stack[1000..

알고리즘 종류 - 문자열 - DP 사고 과정 - LCS 알고리즘이다. - 문자열 A와 문자열 B의 문자를 하나씩 비교하면서 같은 문자이면 숫자를 센다. - 시각화된 자료는 이 블로그를 참고했다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #include using namespace std; // 같은 문자 개수 세기 int dp[1001][1001]; int main(void){ string str1; string str2; cin >> str1 >> str2; // 각각의 문자를 비교하기 for(int i=1; i

알고리즘 종류 - 정렬 사고 과정 - 음수와 양수일 때를 나눈다. - 음수의 경우, 1보다 작은 수는 무조건 곱하면 총합이 커진다. 둘 다 음수인 경우, 곱하면 양수가 된다. 하나는 음수 하나는 0일 경우에는 음수 값이 사라지기 때문에 총합이 커진다. - 양수의 경우, 1보다 큰 수는 무조건 곱하면 총합이 커진다. 둘 다 양수일 경우, 곱하면 더 커진다. 하나가 1보다 큰 양수이고 나머지 하나가 1일 경우, 총합이 1작아진다. 2 * 1 = 2이고, 2 + 1 = 3이기 때문이다. 마찬가지로 하나가 0일 경우에 2 + 0 = 2, 2 * 0 = 0 임을 알 수 있다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..

알고리즘 종류 - 정렬 - 트라이 사고 과정 1. 입력 값을 문자열로 받아서 vector에 저장 2. 저장한 string 값을 정렬 ( sort()로 정렬하면, 비교 문자열 끼리 문자열 내의 문자를 비교하면서 정렬해준다 ) 3. i번째 문자열이 i+1번째에 포함되는지 확인하여 포함되면 'NO', 아니면 'YES'를 출력한다. (i와 i+1번째만 비교해도 되는 이유는, 문자열 정렬을 하고 나면 'abc', 'abca', 'abcab', 'abcabc' 처럼 정렬되기 때문에 i와 i+1번째 문자열만 비교해도 알 수 있다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 3..