전체 글

1. 문제 링크https://www.acmicpc.net/problem/25548 2. 들어가기 전에25547번 신기한 숫자 문제의 풀이를 정리하던 중, 25548번 문제가 시리즈로 존재한다는 사실을 알게 되었다.https://www.acmicpc.net/problem/25547 3. 풀이 방법(1) 정의문제에서 이미 $f(A, B)$ 가 정의되어 있고, 이 글에서는 설명을 위해 $F(k)$ 와 $S(k)$ 를 추가로 정의할 것이다.우선 $F(k) = (k$의 약수의 개수$)$ 로 정의하자.그리고 $S(k) = F(1) + F(2) + \cdots + F(k) = \sum\limits_{i = 1}^k F(i)$ 로 정의하자. (2) 25547번 풀이에서 밝혀진 사실25547번 신기한 숫자의 풀이에서, ..

1. 문제 링크https://www.acmicpc.net/problem/27963 2. 풀이 방법합금을 이루는 두 금속의 혼합 전 밀도를 각각 $d_1$, $d_2$, 혼합 전 질량을 각각 $m_1$, $m_2$, 혼합 전 부피를 $V_1$, $V_2$라고 하자. 그리고 혼합 후 밀도를 $d$, 혼합 후 질량을 $m$, 혼합 후 부피를 $V$라고 하자. 그러면 혼합 후 질량은 혼합 전 질량의 합이므로 $m = m_1 + m_2$ 이고, 혼합 후 부피도 혼합 전 부피의 합이므로 $V = V_1 + V_2$ 이다. 또한 $밀도 = \cfrac{질량}{부피}$ 이므로, $d_1 = \cfrac{m_1}{V_1}$ , $d_2 = \cfrac{m_2}{V_2}$ , $d = \cfrac{m}{V}$ 이 성립한다..

1. 문제 링크https://www.acmicpc.net/problem/33516 2. 접근 방법문자열에서 skeep 이라는 연속한 부분 문자열을 s 를 제외한 소문자 알파벳으로 바꿀 수 있다는 조건이 큰 힌트가 되었다.skeep 부분 문자열이 만들어지면 이를 와일드카드 문자 *로 바꿔서 다른 skeep 문자열을 만드는 데 사용할 수 있다는 의미이기 때문이다. 따라서 문자열에서 s 가 등장할 경우 스택에 넣어주고, k , e , p 가 등장할 경우 이전의 문자들을 확인하여 패턴과 일치하면 스택에 넣어주었고, 패턴과 일치하지 않는 문자가 등장할 경우 스택을 모두 비워주었다.또한 스택의 top이 p 인 경우에는 skeep 을 스택에서 제거한 후 와일드카드 문자 * 를 넣어주었다. 이때 skeep 문자열을 *..

1. 이상 현상 (Anomaly)이상 현상은 데이터베이스를 설계할 때 잘못 설계하여 데이터를 삽입, 삭제, 수정할 때 논리적으로 생기는 오류이다.정규화를 거치지 않은 데이터베이스에서 발생할 수 있는 현상이다. (1) 삽입 이상 (Insertion Anomaly)데이터를 삽입할 때 의도하지 않은 값까지 추가해야 해당 데이터를 테이블에 삽입할 수 있는 현상이다. 예를 들어 {student_id, course_id, department, grade} 를 저장하는 테이블이 있다고 가정하자.해당 테이블의 기본 키(PK)가 {student_id, course_id} 인 경우, 아무 강의도 수강하지 않은 학생은 course_id 가 없는 현상이 발생한다.그러나 course_id 는 기본 키이기 때문에 null 로 추..

1. 트랜잭션 (Transaction)트랜잭션(Transaction)의 사전적 의미는 거래이다. 컴퓨터 과학 분야에서의 트랜잭션은 더 이상 분할이 불가능한 업무 처리의 단위를 의미한다.즉, 트랜잭션은 한꺼번에 수행되어야 하는 일련의 연산 모음을 의미한다. (1) 간단한 예시를 통한 트랜잭션 설명예를 들어, A가 B에게 송금하는 상황을 가정하자. A가 B에게 송금하는 행위는 크게 출금과 입금 두 개의 과정으로 이루어진다.우선 A의 계좌에서 송금할 금액만큼 차감한 다음, B의 계좌에 송금한 금액만큼 입금되어야 한다. 이때 출금만 되고 입금이 안되는 경우가 발생하면 안되므로, 트랜잭션이 필요하다.즉, 출금과 입금 두 과정은 동시에 성공하거나, 그렇지 않다면 동시에 실패해야 한다.이렇게 두 과정을 (atomic..

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$가 존재한다...