Algorithm (57) 썸네일형 리스트형 [Algorithm] 정렬 - 삽입 정렬 (Insertion Sort) 삽입 정렬(Insertion Sort)이란? 이름 그대로, 원소가 들어갈 적당한 자리를 찾아, 삽입하여 정렬하는 방식이다. 예) 1) 배열의 두 번째 값부터 시작한다. arr[1]은 key값으로 따로 저장해놓는다. 2) key값과, 이전 값인 arr[0]값을 비교한다. 3) 이전 값(arr[0])이 key값보다 크므로, 값을 뒤로 한칸 이동시킨다. (arr[0]에 실제로 값이 없어지는 것은 아니지만, 이해를 위해 지웠습니다.) 4) 더 이상 이전으로 이동할 수 없으므로, 비교를 끝내고 저장해놨던 key값을 arr[0]에 설정한다. 5) 다음 값을 key값으로 설정한다. 6) key값과, 이전 값을 비교한다. key값이 더 크므로, 다음으로 넘어간다. 7) 다음 값을 key값으로 설정한다. 8) key값과.. [백준] 6064번: 카잉 달력 문제링크 : https://www.acmicpc.net/problem/6064 문제풀이 규칙찾는 데 좀 시간이 걸렸던 문제.. 규칙을 찾고 나면 쉬운 문제인 것 같다. N = 6, M = 7 을 입력받은 경우로 해를 나열해보면 아래와 같다. x = 3 입력값을 받았다고 가정하였을 때, 아래와 같은 규칙을 찾을 수 있다. x가 3일 때 나오는 해는 x에 N을 더해서 구할 수 있고, x가 3일 때 나오는 y값들은, 앞에서 구한 해를 M으로 나눈 나머지와 같다. 이를 이용해 y 입력값과 같은 값이 나올 때 까지 반복하여 해를 구한다. 마지막 해는 문제에서도 힌트를 줬듯이, N과 M의 최소공배수와 같다. 따라서 N과 M의 최소공배수보다 큰 경우는 유효하지 않으므로 -1을 출력한다. 소스코드 /* * 백준 606.. [Algorithm] 유클리드 호제법 유클리드 호제법이란? 두 개의 정수 a, b에 대하여 a, b의 최대공약수를 찾는 방법을 말한다. 유클리드 호제법의 원리 a가 b보다 크다고 할 때, a = bq + r이 성립한다. a, b의 최대공약수를 G라고 하면, a = GA, b = GB가 성립한다. 이를 위 식에 대입하면 GA = GBq + r이다. 여기에서 r = G(A - Bq)로, a와 b와 r의 최대공약수가 G임을 알 수 있다. 알고리즘 위 원리를 이용하여, r = 0일 때 까지 작업을 반복한다. (r = 0인 경우는 나눠 떨어지는 경우) int gcd(int a, int b) { int r = 0; while (b > 0) { r = a % b; a = b; b = r; } return a; } 출처 : https://namu.wiki.. [백준] 1475번: 방 번호 문제링크 : https://www.acmicpc.net/problem/1475 문제풀이 ① 0부터 9까지 길이가 10인 배열을 만든다. ② 입력받은 방 번호를 숫자 하나씩 차례로, 개수를 세어 배열에 넣는다. ③ 6, 9을 제외한 나머지 숫자들 중 제일 많이 나온 수를 찾는다. ④ 6, 9는 각각의 개수를 더해서 따로 계산한다. 예) 669 또는 999 가 나오는 경우 2세트가 필요하고, 6996 또는 6666이 나오는 경우에도 2세트가 필요하다. 6과 9를 더해서 합이 짝수이면 2로 나눈 만큼의 세트가 필요하고, 합이 홀수이면 2로 나눠 1을 더한 만큼의 세트가 필요한 것을 알 수 있다. ⑤ ③과 ④에서 구한 수 중 더 큰 수를 출력한다. 소스코드 /* * 백준 1475번: 방 번호 */ #includ.. [백준] 1157번: 단어 공부 문제링크 : https://www.acmicpc.net/problem/1157 문제풀이 ① A부터 Z까지 길이가 26인 배열을 만든다. ② 입력받은 문자열을 모두 대문자로 변환한다. ③ 아스키 문자표에서 A는 65에 해당한다. 따라서 입력받은 문자 하나씩 차례로 65를 빼 인덱스로 사용한다. ④ 위에서 구한 인덱스에 해당하는 값을 증가시킨다. 예) Mississipi ⑤ 위 배열을 차례로 돌면서 가장 큰 값을 가지고 있는 인덱스를 구한다. ⑥ 가장 큰 값이 중복으로 나오면 인덱스를 -1로 저장한다. ⑦ 인덱스가 -1이면 '?'를, -1이 아니면 그에 해당하는 문자를 출력한다. 소스코드 /* * 백준 1157번: 단어 공부 */ #include #include using namespace std; int .. [백준] 1924번: 2007년 문제링크 : https://www.acmicpc.net/problem/1924 문제풀이 2007년 1월 1일부터 시작해서, 입력받은 날까지의 총 일수를 계산한 후 7로 나눈 나머지가 0이면 일요일, 1이면 월요일... 6이면 토요일을 출력하였다. 소스코드 /* * 백준 1924번: 2007년 */ #include #include using namespace std; int main() { int x, y; cin >> x >> y; int month[13] = {0, }; for (int i = 1; i < 13; i++) { switch (i) { case 2: month[i] = 28; break; case 4: case 6: case 9: case 11: month[i] = 30; break; de.. [백준] 2775번: 부녀회장이 될테야 문제링크 : https://www.acmicpc.net/problem/2775 문제풀이 처음에는 이 문제의 규칙을 찾으려고 했다. 하지만 문제를 다시 보니 입력받는 수가 크지 않아서 (1 > n; cout [백준] 10250번: ACM 호텔 문제링크 : https://www.acmicpc.net/problem/10250 문제풀이 방은 엘리베이터에서 가까운 101 - 201 - 301 - 401호.. 의 순서로 배정된다. 따라서 배정되는 방 번호는 아래와 같은 규칙으로 계산할 수 있다. 입력받은 호텔의 층 수로 나눠서 계산이 가능하다. 단, 30과 같이 6으로 나눠떨어지는 수들은 나머지가 0이 되므로 저대로 계산하게 되면 0층, 6호가 나온다. 나눠떨어지는 경우에 대해서만 예외처리를 해주면 된다. 소스코드 /* * 백준 10250번: ACM 호텔 */ #include using namespace std; int main() { int T; cin >> T; cout.fill('0'); while (T--) { int H, W, N; cin >.. 이전 1 ··· 3 4 5 6 7 8 다음
