본문 바로가기
반응형

알고리즘/BAEKJOON88

BOJ 5896 : 효율적으로 소 사기 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/5896 우선순위 큐를 이용하여 문제를 풀 수 있다. 아래의 경우에 대해서 생각해보자. 1) 쿠폰을 사용할 수 없는 경우. 모든 소의 원가에 대해 가장 가격이 낮은 소부터 산다. 2) 모든 소에 대해 쿠폰을 사용할 수 있는 경우. 모든 소의 쿠폰 적용가에 대해 가장 가격이 낮은 소부터 산다. 두 경우는 쉽게 해결할 수 있다. 문제는 쿠폰의 수가 0 < K < N인 경우이다. 쿠폰을 사용하였을 때, 가격이 가장 작은 소부터 고르고, 남은 소 중에는 원가에서 가장 싼 가격만 고를 경우 아래와 같은 문제가 생길 수 있다. 먼저 돈이 7원, 쿠폰은 1장만 쓸 수 있는 경우를 보자. 소1 : 원가 - 10원, 쿠폰가 - 5원 소2 .. 2021. 5. 18.
BOJ 2503 : 숫자 야구 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2503 숫자 야구의 원리는 삼성 B형 샘플 문제 : 숫자야구게임을 참고하자. 이 문제에서는 답이 되는 answerList 배열에서 답이 될 수 없는 숫자를 지워나가는 방식으로 해결한다. 먼저 답의 후보는 100 ~ 999 중, 0이 없고, 중복된 숫자가 없는 번호이다. 따라서 숫자에 0이 포함된 경우와 중복된 번호가 있는 경우에 answerList에 1(삭제)을 표시한다. int main(void) { scanf("%d", &N); int answerList[1000 + 5] = { 0 }; for (int n = 100; n 2021. 5. 13.
BOJ 2745 : 진법 변환 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2745 B진법의 수 N을 10진법으로 변환하는 문제다. 알파벳이 포함되어 있으므로 문자열로 입력을 받는다. 그리고 각 문자에 대해 change 배열에 정수로 저장한다. for (int i = '0'; i 2021. 5. 8.
BOJ 2609 : 최대공약수와 최소공배수 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2609 두 수 A, B의 최대공약수가 G라면 A = a * G, B = b * G로 정의할 수 있다. 그러면 최소공배수는 a * b * G = A * B / G 가 된다. 최대공약수는 유클리드 호제법으로 구할 수 있다. A % B = R이라고 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. (A ≥ B) 즉, B가 0이 아닌 경우 gcd(B, A % B)를 구한다. 이 과정을 B가 0이 되는 경우에 A를 return하면 된다. 최소공배수의 경우 A * B / G의 경우 A * B 연산에 의해 overflow가 발생할 수 있다. 따라서 나누기를 먼저해서 (A / G * B) overflow를 방지한다. #include int.. 2021. 5. 5.
BOJ 1913 : 달팽이 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1913  배열의 중심 좌표에서 달팽이 모양의 배열을 만들면 된다. 먼저 배열의 중심 좌표 (sr, sc)는 N / 2 + 1이 된다.문제의 예시 7인 경우 (4, 4) 부터 배열이 시작됨을 알 수 있다.sr = sc = N / 2 + 1; N = 5인 경우 규칙을 살펴보자.먼저 처음 1 → 2의 방향은 ↑ 방향이 된다.달팽이는 ↑, →, ↓, ← 로 방향을 반복해서 바꾼다.따라서, dr, dc는 아래와 같이 정의할 수 있다./* ↑, →, ↓, ← */int dr[] = { -1, 0, 1, 0 };int dc[] = { 0, 1, 0, -1 }; 방향이 두 번 바뀔 .. 2021. 4. 30.
BOJ 2630 : 색종이 만들기 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2630 색종이의 판단은 시작 좌표 (sr, sc) 그리고 size를 이용하여 판단한다. 아래의 check 함수는 비정상적인 색종이인 경우 -1을 return하고, 정상적인 경우 MAP[sr][sc]를 return한다. MAP[sr][sc]가 0이면 WHITE 색종이, 1이면 BLUE 색종이가 된다. int check(int sr, int sc, int size) { int tmp = MAP[sr][sc]; for (int r = sr; r < sr + size; r++) for (int c = sc; c < sc + size; c++) if (MAP[r][c] != tmp) return -1; return tmp; } 가장 큰 색종이부.. 2021. 4. 25.
BOJ 1080 : 행렬 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1080 A[r][c] != B[r][c]일 때, 위에서부터 왼쪽으로 A[r][c] ~ A[r + 2][c + 2]까지 뒤집으면 된다. 즉, (r, c)에서는 한 번만 뒤집던가, 뒤집지 않으면 된다. (r, c)에서 두 번 이상 뒤집는 것은 원래대로 돌아오기만 하므로 연산의 횟수만 낭비가 된다. (r, c)를 제외한 3 x 3 좌표는 다음 자기 차례가 올 때, 뒤집을지 판단하면 된다. #include #define MAX (50 + 5) int N, M; int A[MAX][MAX]; int B[MAX][MAX]; void input() { scanf("%d %d", &N, &M); for (int r = 1; r 2021. 4. 10.
BOJ 1715 : 카드 정렬하기 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1715 카드 비교 횟수를 줄이기 위해서는 가장 작은 수의 두 카드를 비교해야한다. 그리고 카드를 합친다. (+ 횟수를 누적한다.) 그러면 다시 남은 카드(+ 합친카드 포함) 중에서 가장 작은 수의 두 카드를 비교해야한다. 따라서, 우선순위 큐를 이용한다. 가장 작은 두 카드는 두 번 pop하면 얻을 수 있고, 합친 카드를 우선순위 큐에 넣어도 우선순위 큐를 두 번 pop하면 가장 작은 두 카드를 구할 수 있다. #include int N; int heap[100100]; int hn; int pop(int* heap, int& hn) { int tmp, ret; ret = heap[1]; heap[1] = heap[hn]; heap[h.. 2021. 4. 9.
BOJ 1644 : 소수의 연속합 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1644 N이 4,000,000으로 매우 크므로, 매번 소수를 판단하는 것은 비효율적이다. 따라서, 소수의 판단은 에라토스테네스의 체를 이용한다. int N; int prime[4000000 + 50000]; int primeSet[4000000 + 50000]; int pcnt; void eratos() { prime[1] = 1; for (int i = 2; i * i 2021. 4. 2.
반응형

티스토리툴바