거창한 시작

www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 알고리즘 종류 - 투 포인터 - 에라토스테네스의 체 사고 과정 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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include #include #include using namespace std; in..

www.acmicpc.net/problem/16935 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 알고리즘 종류 - 구현 사고 과정 - 주어진 6개의 명령에 따라 배열을 돌리면 된다. 0. n은 가로의 개수, m은 세로의 개수이다. 1. 상하반전 : row값이 i이면, 상하반전으로 놓일 곳은 n-1-i 이다. 2. 좌우반전 : column값이 j이면, 좌우반전으로 놓일 곳은 m-1-j이다. 3. 시계방향 90도 회전 : (i, j)..

알고리즘 종류 - 구현 사고 과정 - 색이 같은 영역에서 회전을 시킨다. 1. 각 영역마다 (가로 길이 - 1) * 2 + (세로 길이 -1) * 2를 하면 1바퀴를 돌게 된다. 즉, 이 값으로 회전 횟수 r을 나눈 나머지가 유의미하게 회전할 횟수이다. 2. 유의미한 회전 횟수를 구한 후, 회전 횟수 만큼 각 변을 회전시킨다. 3. 하나의 영역이 완료되면, 내부 영역으로 옮기고 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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 5..

알고리즘 종류 - 회전 사고 과정 1. 회전 횟수만큼 while을 반복한다. 2. 4개의 꼭지점을 찾고, 꼭지점이 사각형을 이룰 때까지 while을 반복한다. 3. 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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 #include #include using namespa..

이분 탐색 - 정렬된 배열에서 중간에 위치한 값과 목표 값을 비교해서 목표 값의 위치를 찾는 알고리즘 - 목표 값이 있는 지 확인하는 알고리즘 동작 1. 배열의 맨 왼쪽과 맨 오른쪽을 가리킬 index 변수 두 개 left와 right를 선언합니다. 2. left와 right의 중간 위치인 mid를 구하고 mid 위치에 있는 값과 목표 값을 비교합니다. 2-1. 목표 값과 mid에 위치한 값이 같으면, 탐색을 멈춥니다. 2-2. 목표 값보다 mid에 위치한 값이 작으면, left = mid + 1 해줍니다. 2-3. 목표 값보다 mid에 위치한 값이 크면, right = mid + 1 해줍니다. 3. 탐색이 끝날 때까지 2번을 반복합니다. 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..

알고리즘 종류 - 탐욕 - 정렬 사고 과정 - 아무 생각이 없다... - 방법을 찾아보자 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..

Two pointers - 배열 A에서 2개의 포인터를 이용해서 문제를 해결하는 알고리즘 동작 - 포인터를 어떻게 움직이느냐에 따라 조금 다릅니다. 여기서는 시작점에서 2개의 포인터를 오른쪽으로 이동시키는 알고리즘을 설명하겠습니다. 1. 2개의 포인터(left, right)는 배열의 첫 부분을 가리킨다. 2. 두 포인터가 가리키는 값의 합이 목표치 X보다 작으면, right 포인터를 오른쪽으로 한 칸 옮깁니다. 3. 두 포인터가 가리키는 값의 합이 목표치 X보다 크면, left 포인터를 오른쪽으로 한 칸 옮깁니다. 4. right 포인터가 배열의 끝에 갈 때까지 또는 문제의 특정 목표에 도달하면 동작을 끝냅니다. - two pointers에 대한 좋은 강의가 있어서 참고했습니다. 구현 - www.acmi..