✔ GCD(n, k) = 1 [백준 11689] 문제 분석하기 문제를 만족하는 자연수의 개수가 오일러 피 함수의 정의이므로 오일러 피 함수를 구현 손으로 풀어보기 서로소의 개수를 표현하는 변수 result와 현재 소인수 구성을 표시하는 변수 n을 선언 2 ~ N의 제곱근까지 탐색하면서 소인수일 때 result = result - (result / 소인수) 연산으로 result 값을 업데이트 n에서 이 소인수는 나누기 연산으로 삭제함 예) 현재 소인수가 2일 때, 2⁷ * 11 * 13을 11 * 13으로 변경 반복문 종료 후 현재 n이 1보다 크면 n이 마지막 소인수이므로 result = result - (result / n) 연산으로 result 값을 마지막으로 업데이트한 후 출력 예) n = 15 N..
✔ 제곱 ㄴㄴ 수 [백준 1016] 문제 분석하기 에라토스테네스의 체 알고리즘 방식으로 제곱수 판별 로직에 사용 손으로 풀어보기 2의 제곱수인 4부터 max값까지 제곱수를 찾음 이때 데이터를 순차적으로 탐색하는 것이 아니라 에라토스테네스의 체 방식으로 제곱수의 배수 형태로 탐색 탐색한 배열에서 제곱수로 확인되지 개수를 센 후 출력 예) min = 1, max = 10 제곱수 pow start_index j Check 배열 i = 2, pow = 4 1 1 1 *4 - 1 = 3 Check[3] = 4 [false, false, false, true, false, false, false, false, false, false] 2 2 *4 - 1 = 7 Check[7] = 8 [false, false, fa..
✔ 소수&팰린드롬 [백준 1747] 문제 분석하기 에라토스테네스의 체를 이용해 최대 범위에 해당하는 모든 소수를 구해 놓은 후 이 소수들의 집합에서 N보다 크거나 같으면서 팰린드롬 수인 것을 찾아냄 손으로 풀어보기 2 ~ 10000000 사이에 존재하는 모든 소수를 구함 그 중 N보다 크거나 같은 소수에서 팰린드롬 수인지를 판별 소수의 값을 char 배열 형태로 변환한 후 양끝의 투 포인터를 비교하면 쉽게 팰린드롬 수인지 판별 가능 최초로 팰린드롬 수가 나오면 프로그램을 종료 슈도코드 작성하기 N(어떤 수) A(소수 배열) for(2 ~ 10000001) { A 배열 초기화 } for(A 배열 길이의 제곱근까지 반복하기) { 소수가 아니면 넘어감 for(소수의 배수 값을 10000001까지 탐색하기) {..
✔ 거의 소수 [백준 1456] 문제 분석하기 최대 범위에 해당하는 모든 소수를 구해 놓고, 이 소수들이 입력된 A와 B 사이에 존재하는지 판단해 문제를 해결 이를 위해 에라토스테네스의 체를 이용해 빠르게 소수를 먼저 구하도록 함 손으로 풀어보기 2 ~ 10000000 사이에 존재하는 모든 소수를 구함 각각의 소수에 관해 소수를 N 제곱한 값이 B보다 커질 때까지 반복문을 수행 소수를 N 제곱한 값이 A보다 크거나 같으면 거의 소수로 판단해 카운트 N 제곱한 값을 구하는 도중 값의 범위가 long형을 초과하는 경우가 발생할 수 있으므로 N^k과 B 값이 아니라 N과 B/N^(k-1)을 비교하는 형식을 사용 예) A = 1, B = 1000 모든 소수 2, 3, 5, 7, 11, 13, 17, 19, 23..
✔ 잃어버린 괄호 [백준 1541] 문제 분석하기 가장 작은 최솟값을 만들기 위해서는 가능한 큰 수를 빼야 하므로 더하기에 해당하는 부분에 괄호를 쳐서 먼저 모두 계산한 후 빼기를 실행하도록 함 손으로 풀어보기 더하기 연산을 실행 가장 앞에 있는 값에서 더하기 연산으로 나온 결괏값들을 모두 뺌 예) 100 - 40 + 50 + 74 - 30 + 29 - 45 + 43 + 11 100 - (40 + 50 + 74) - (30 + 29) - (45 + 43 + 11) 100 - 164 - 59 - 99 = -222 슈도코드 작성하기 answer(정답 변수) 들어온 데이터를 "-" 기호를 기준으로 split 수행하기 for(나눠진 데이터 개수만큼 반복하기) { 결괏값 = mySum() 함수 수행하기 if(가장..
✔ 회의실 배정 [백준 1931] 문제 분석하기 현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는데 유리하므로 종료 시간이 빠른 순서대로 정렬해 겹치지 않는 회의실을 적절하게 선택 손으로 풀어보기 회의 정보와 관련된 데이터를 저장한 후 종료 시간 순으로 정렬 단, 종료 시간이 같을 때는 시작 시간을 기준으로 다시 한 번 정렬 예) (1, 2), (2, 2)의 경우 (1,2)를 먼저 실행해야 (2, 2)까지 실행 가능함 순차적으로 탐색하다가 시간이 겹치지 않는 회의가 나오면 선택 예) 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 의 경우 정렬을 하면 [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, ..
✔ 수 묶기 [백준 1744] 문제 분석하기 가능한 큰 수들끼리 묶어야 결괏값이 커지며, 음수끼리 곱하면 양수로 변하는 성질을 고려해 문제에 접근 손으로 풀어보기 수의 집합을 1보다 큰 수, 1, 0, 음수 이렇게 4가지 유형으로 나눠 저장 1보다 큰 수의 집합을 내림차순 정렬해 최댓값부터 차례대로 곱한 후에 더함 원소의 개수가 홀수일 때 마지막 남은 수는 그대로 더함 음수의 집합을 오름차순 정렬해 최솟값부터 차례대로 곱한 후에 더함 원소의 개수가 홀수일 때 수열에 0이 있다면 1개 남은 음수를 0과 곱해 0을 만들고, 수열에 0이 없다면 그대로 더함 위에서 구한 값을 모두 더하고, 그 값에 숫자 1의 개수를 더함 슈도코드 작성하기 N(카드 묶음 개수) plusPq(양수 우선순위 큐) minusPq(음수..
✔ 카드 정렬하기 [백준 1715] 문제 분석하기 먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 미치게 되므로 카드 묶음의 개수가 작은 순서대로 먼저 합치는 것이 전체 비교 횟수를 줄일 수 있는 방법 그러므로 현재 데이터 중 가장 작은 카드의 개수를 가진 묶음 2개를 뽑아 합친 후 새로운 카드 묶음을 다시 데이터에 넣고 정렬하는 것을 반복해야 하므로 우선순위 큐를 이용 손으로 풀어보기 현재 카드의 개수가 가장 작은 묶음 2개를 선택해 합침 합친 카드 묶음을 다시 전체 카드 묶음 속에 넣음 카드 묶음이 1개만 남을 때까지 반복함 슈도코드 작성하기 N(카드 묶음 개수) pq(우선순위 큐) for(N만큼 반복하기) { 우선순위 큐에 데이터 저장하기 } while(우선순위 큐 크기가 1이 될 때까지) {..
