-
ckw1140's profile image
ckw1140
December 14, 2019
주어진 수들의 XOR 연산으로 만들 수 있는 수
주어진 수들의 XOR 연산으로 만들 수 있는 수 자연수의 집합 ${a_1, a_2, …, a_N}$ 이 주어집니다. 우리는 이 중 두 개의 원소를 골라 XOR한 결과를 집합에 추가할 수 있습니다. 이 때, 다음 문제들에 대해 생각해보겠습니다. 자연수 $b$가 주어질 때, 이 $b$가 집합의 원소가 될 수 있는지 판별하기. 이 집합에 들어갈 수 있는 원소의 최대 개수 구하기. 이 두 문제에 빠르게 답할 수 있는 방법을 알아보겠습니다. 우선, 첫번째로 어떤 수들이 집합에 추가 될 수 있는지 알아보겠습니다....
-
ckw1140's profile image
ckw1140
November 15, 2019
알고리즘 문제 풀이7
알고리즘 문제 풀이 7 최근에 푼 재미있는 문제들을 포스팅 해보겠습니다. [BOJ 9208 링월드] 이 문제는 원형으로 나열되어 있는 $M$개의 도시가 있고, 연속된 도시들로 이루어진 $N$개의 구간이 있을 때, $N$개의 구간에서 겹치지 않게 도시를 하나씩 고를 수 있는가를 답해야 하는 문제입니다. 우선, M개의 도시가 원형이 아니라 선형으로 나열되어 있다면 어떨까요? 이 문제는 매우 간단한 그리디로 풀 수 있습니다. 왼쪽 도시에서부터 쭉 보면서 현재 도시를 고를 수 있는 구간들 중 오른쪽 끝 도시가 가장 왼쪽에 있는 구간에게...
-
ckw1140's profile image
ckw1140
September 18, 2019
알고리즘 문제 풀이6
알고리즘 문제 풀이 6 최근에 푼 재미있는 문제들을 포스팅 해보겠습니다. BOJ 1530 금민수의 합 이 문제는 4와 7로만 이루어진 수를 금민수로 정의하고, $N$($\leq1,000,000,000$)이 주어지면 $N$을 금민수의 합으로 나타내는 방법을 찾는 문제입니다. 만일, 방법이 여러가지라면 수의 개수가 적은 방법을, 이러한 방법 또한 여러가지라면 사전순으로 최소인 방법을 찾아야 합니다. 우선 여러가지 관찰을 해봅시다. 첫번째로 주어진 수 $N$을 금민수들의 합으로 표현하는 것이 불가능한 경우가 있을까요? 네, 물론 있습니다. 작은 수에서 예를 들어보면 1, 2, 3, 5, 6, 9,...
-
ckw1140's profile image
ckw1140
August 18, 2019
알고리즘 문제 풀이5
알고리즘 문제 풀이 5 최근에 푼 재미있는 문제들을 포스팅 해보겠습니다. BOJ 1185 숫자 놀이 이 문제는 $2N - 1$ 개의 숫자가 주어질 때, 그 중에서 $N$ 개의 숫자를 골라서 합이 N의 배수가 되도록 만드는 문제입니다.(단, $N = 2^n$ 꼴의 수 입니다) 우선 “합이 $N$ 의 배수가 되는 $N$ 개의 숫자를 골라내는 것이 언제나 가능할 것인가?” 라는 의문이 생깁니다. 수학적 귀납법을 사용하면 이러한 의문과 이 문제에 대한 답을 동시에 제시해주는 풀이를 얻을 수 있습니다. 지금부터 알아보도록...
-
ckw1140's profile image
ckw1140
July 19, 2019
알고리즘 문제 풀이4
알고리즘 문제 풀이 4 최근에 푼 재미있는 문제들을 포스팅 해보겠습니다. [BOJ 2899] 구슬 없애기 구슬 $N$개가 일렬로 놓여있습니다. 같은 색의 구슬이 연속 K개 이상 놓여 있으면 그 구슬들을 없앨 수 있습니다. 구슬을 모두 없애고 싶지만 현재 상태로는 구슬을 모두 없애는 것이 불가능할 수도 있습니다. 현재 구슬의 사이에 마음대로 구슬을 추가할 수 있을 때, 구슬을 모두 없애기 위해 추가해야 하는 구슬의 최소 개수를 구하는 문제입니다. 복잡해 보이지만 다이나믹 프로그래밍을 사용하면 비교적 간단하게 해결 가능한 문제입니다. 먼저...
-
ckw1140's profile image
ckw1140
June 17, 2019
알고리즘 문제 풀이 3
알고리즘 문제 풀이 3 최근에 푼 재미있는 문제들을 포스팅 해보겠습니다. BOJ 1066번 에이한수 각 자리수를 등차 수열을 이루는 연속한 수들끼리 묶어서 $A$ 개의 그룹으로 나눌 수 있으면 $A$-한수 라고 할때, $A$-한수 이고 $(A - 1)$-한수가 아니면서 각 자리수가 비내림차순인 $N$ 자리 자연수의 개수를 구하는 문제입니다. 다음과 같은 사실을 관찰해 봅시다. $A$-한 수 이고 $A < N$ 이면 $(A + 1)$-한 수이기도 하다. 위와 같은 사실이 성립하는 이유는 $A < N$ 이기 때문에 적어도 한 그룹에는...
-
ckw1140's profile image
ckw1140
May 7, 2019
알고리즘 문제 풀이2
알고리즘 문제 풀이 4월에 푼 재미있는 문제들의 풀이를 작성해보았습니다. 문자열 장식 N개의 문자열이 주어지면 이 문자열들을 합쳐서 만들수 있는 사전순으로 가장 앞서는 문자열을 구하는 문제입니다. 단, 각 문자열 안에서의 상대적인 순서는 유지해야합니다. 우선 상대적인 순서를 유지해야 하니까 주어진 문자열들의 앞글자부터 하나씩 때어 온다고 생각합시다. 그러면, 매순간 각 문자열의 앞글자들 중에 사전순으로 가장 작은 알파벳이 있다면 그것을 때어 오는 것이 이득이라는 것을 쉽게 알 수 있습니다. 그런데 이러한 문자열이 여러개가 있으면 어떤 문자열에서 때어오는 것이 이득일까요?...
-
ckw1140's profile image
ckw1140
April 22, 2019
알고리즘 문제 풀이
알고리즘 문제 풀이 3월에 푼 재미있는 문제들의 풀이를 써보았습니다. BOJ 1352번 문자열 아래와 같은 $dp$를 정의합니다. $dp(x, sum)$ := $0$~$x-1$번째 인덱스까지 처음으로 사용한 문자들의 인덱스합이 $sum$ 일 때, $x$번째 ~ 마지막까지를 적절히 정하여 길이 $N$의 ideal string 을 만들수 있는지 여부(가능하면 1, 불가능하면 0) 이 $dp$의 transition은 어떻게 될까요? 각 상태에서 선택할 수 있는 것이 무엇인지 고민해 봅시다. 각 상태에서 우리가 정해야 하는 것은 $x$번째 인덱스에 들어올 문자입니다. 우리가 이 $dp$에서 알고자 하는 것은 최종적으로...
-
ckw1140's profile image
ckw1140
March 8, 2019
meet in the middle
Meet in the middle meet in the middle 은 절반 크기의 비슷한 문제를 두 번 해결한 결과를 통해 본 문제를 해결함으로서 문제 해결에 소요되는 시간 복잡도의 향상을 꾀하는 방법입니다. 저 말만 들으면 어떠한 장점이 있는지 감이 오지 않지만, 문제를 푸는 시간 복잡도가 exponential 한 경우라면 아래와 같이 개선이 된다는 것을 느낄수 있을 것입니다. $2^n > 2 * 2^{n/2}$ 구체적인 예제를 통해 설명해 보도록 하겠습니다. BOJ 1208 부분집합의 합2 이 문제는 $N(N\leq 40)$개의 수로 이루어진 집합이...
-
ckw1140's profile image
ckw1140
January 18, 2019
greedy algorithm study
그리디 알고리즘 스터디 12월 말부터 한양대의 알고리즘 동아리 후배들을 대상으로 스터디를 진행하고 있습니다. 매주 한가지 분야에 대한 문제들을 여러개 풀어보는 방식으로 진행할 계획인데요, 1주차에는 그리디 알고리즘에 관한 문제들을 풀어보았습니다. **** 뒤집기 (https://www.acmicpc.net/problem/1439) 대회 or 인턴 (https://www.acmicpc.net/problem/2875) 택배 (https://www.acmicpc.net/problem/8980) 멀티탭 스케줄링 (https://www.acmicpc.net/problem/1700) 보석 도둑 (https://www.acmicpc.net/problem/1202) 빵집 (https://www.acmicpc.net/problem/3109) 크게 만들기 (https://www.acmicpc.net/problem/2812) 캔디캔디 (https://www.acmicpc.net/problem/2878) 풍선 (https://www.acmicpc.net/problem/4716) 박스 채우기 (https://www.acmicpc.net/problem/1493) 숫자 게임 (https://www.acmicpc.net/problem/2923) 통나무 자르기 (https://www.acmicpc.net/problem/1114) 회의실 배정 (https://www.acmicpc.net/problem/1931) 도서관 (https://www.acmicpc.net/problem/1461) 행렬 (https://www.acmicpc.net/problem/1080) 등수 매기기 (https://www.acmicpc.net/problem/2012) 비슷한 순열 (https://www.acmicpc.net/problem/2413)...