백준

1. 문제 링크https://www.acmicpc.net/problem/2532 2. 풀이 방법각 동물의 번호, 동물의 활동영역의 왼쪽 위치, 오른쪽 위치가 입력으로 들어온다.이 중에서 번호는 필요하지 않으므로, 왼쪽 위치와 오른쪽 위치를 묶어서 저장해주었다.// 헤더using pii = pair;// main 함수vector animals;for (int i = 0; i > idx >> l >> r; animals.emplace_back(l, r);} 우선 활동영역을 정렬했는데, 왼쪽 위치에 대해 내림차순이 되도록, 왼쪽 위치가 같은 경우에는 오른쪽 위치에 대해 오름차순이 되도록 정렬했다.struct cmp{ bool operator()(const pii &a, const pii &b) co..

1. 문제 링크구슬 탈출 : https://www.acmicpc.net/problem/13459구슬 탈출 2 : https://www.acmicpc.net/problem/13460구슬 탈출 3 : https://www.acmicpc.net/problem/15644구슬 탈출 4 : https://www.acmicpc.net/problem/15653 2. 풀이 방법이 문제를 처음 읽었을 때 확실한 방법과 코드가 떠오르지 않아서 다소 당황스러웠다.최근에 감을 조금 잃어버린 탓인지.. 오랜만에 감 잡기에 굉장히 좋은 문제라고 느꼈다. 우선 초기 상태에서 상하좌우 4방향으로 구슬을 굴리면서 가능한 경우를 모두 탐색해야 한다.빨간 구슬이 구멍에 빠지는 경우가 나올 때까지 모든 경우를 탐색해야 한다. 그리고 이미 탐..

1. 문제 링크https://www.acmicpc.net/problem/1307 2. 풀이 방법마방진의 크기 n이 홀수인 경우, 4의 배수인 경우, 4의 배수가 아닌 2의 배수인 경우로 나누어서 다르게 구현했다.마방진을 만드는 방법은 다른 글에 이미 잘 정리가 되어있어서, 링크로 대신한다. 먼저, n이 홀수인 경우에는 아래 글을 참고했다.https://destiny738.tistory.com/244 홀수 마방진홀수 마방진은 마방진을 만드는 것중에서 가장 간단한 형태이다. 위에서 파란원이 만들려고 하는 마방진이다.(크기 3짜리 3*3 마방진을 만든다.) 다음과 같은 과정을 따르며 마방진을 완성해간다destiny738.tistory.com 다음으로, n이 4의 배수인 경우에는 아래 글을 참고했다. (위의 글..

1. 문제 링크https://www.acmicpc.net/problem/25547 2. 사전 지식이 글을 읽기 전에, 최대공약수와 최소공배수에 대한 아래 글을 함께 읽으면 좋다.https://infikei.tistory.com/46 [Algorithm] 유클리드 호제법1. 유클리드 호제법유클리드 호제법(또는 유클리드 알고리즘, Euclidean Algorithm)은 두 양의 정수의 최대공약수를 구하는 방법 중 하나이다.여기서 호제라는 말은 서로 나눈다는 것을 의미한다. 2.infikei.tistory.com 3. 접근 방법우선 세 정수 $A$, $B$, $C$ 가 다음 두 조건을 만족한다고 가정하자.$\gcd(A, B) = \gcd(A, C)$$\mathrm{lcm}(A, B) = \mathrm{lcm}..

1. 유클리드 호제법유클리드 호제법(또는 유클리드 알고리즘, Euclidean Algorithm)은 두 양의 정수의 최대공약수를 구하는 방법 중 하나이다.여기서 호제라는 말은 서로 나눈다는 것을 의미한다. 2. 최대공약수의 정의최대공약수(GCD, Greatest Common Divisor)는 두 개 이상의 정수의 공통 약수 중 가장 큰 양의 정수이다.또한 최대공약수가 $1$인 두 정수를 서로소(coprime)라고 한다. ($0$과 어떤 정수 $a$의 최대공약수는 $a$로 정의할 수 있다. $0$은 모든 정수의 배수이기 때문이다.) 3. 최대공약수의 특징두 정수 $a$와 $b$의 최대공약수 $\gcd(a, b)$에 대해, $ax + by = \gcd(a, b)$를 만족하는 정수 $x$, $y$가 존재한다...

1. 연산자 (산술적 왼쪽 시프트, Arithmetic Left Shift)왼쪽으로 비트를 이동시키고, 이동 후 오른쪽에 생긴 빈 공간은 0 으로 채운다.비트를 한 번 이동시킬 때마다 값에 2가 곱해진다.예 : 1 → $2^3 = 8$ 2. >> 연산자 (산술적 오른쪽 시프트, Arithmetic Right Shift)오른쪽으로 비트를 이동시키고, 이동 후 왼쪽에 생긴 빈 공간은 양수의 경우 0 으로, 음수의 경우 1 로 채운다.즉, 부호 비트를 유지하면서 오른쪽으로 비트를 이동시킨다.비트를 한 번 이동시킬 때마다 값이 2로 나눠진다.예 : -8 >> 2 → $-8 \div 4 = -2$ 3. >>> 연산자 (논리적 오른쪽 시프트, Logical Right Shift)C/C++에 존재하지 않는 연산자..

1. 버블 정렬이란?서로 인접한 두 원소를 비교하고, swap 연산을 수행하면서 정렬하는 방식이다.가장 큰 값이 배열의 끝으로 이동하는 과정이 물방울이 수면으로 떠오르는 듯한 모습을 보이기 때문에 버블 정렬이라는 이름이 붙었다. 2. 버블 정렬의 동작 과정배열의 처음부터 끝까지 순회하면서 인접한 두 원소를 차례대로 선택한다.인접한 두 원소를 비교하여 정렬 순서와 맞지 않다면, 서로 자리를 교환한다.배열의 끝에 가장 큰 값이 정렬되면, 다음 반복에서는 그 값을 제외하고 정렬한다.배열이 완전히 정렬될 때까지 1~3 과정을 반복한다. 3. 버블 정렬의 구현 코드아래는 버블 정렬을 구현한 코드이다.void bubble_sort(vector &nums) { int n = nums.size(); for ..

2의 거듭제곱을 외우고 있다고 말하면 그걸 왜 외우냐는 질문이 가장 많이 들어온다.어릴 적에 심심해서 외웠던 게 시작이었던 것 같다. 어릴 적에 10제곱까지 외웠다가 20제곱까지 늘렸던 기억이 난다.대학교 와서 27제곱까지 외웠던 것 같다.뇌 용량의 한계로 더 이상 외우려고 하지 않았는데,최근에 알고리즘 공부하고 코드 짜다보니 그 유명한 2^31 - 1 = 2147483647을 자주 접하게 되었다.그래서 내친김에 32제곱까지 외워버렸다. 2^1 = 22^2 = 42^3 = 82^4 = 162^5 = 32 2^6 = 642^7 = 1282^8 = 2562^9 = 5122^10 = 1024 2^11 = 20482^12 = 40962^13 = 81922^14 = 163842^15 = 32768 2^16 = 6..