brute force 브루트 포스. 직역 하면 무식한 힘이라는 뜻이다. 머리가 나쁘면 몸이 고생한다는 것처럼 어떤 문제에 대해 모든 경우의 수를 시도하는 방법이다. 이렇게 보면 비효율적이고 무식한 방법이라고 생각할 수 있지만 의외로 많이 쓰인다. 우선 모든 경우의 수를 해보기 때문에 시간과 자원만 된다면 성공률이 100%이다. 노가다라고도 부르고 ...

Alkon 3주차 챌린지 (6/6) 또 2등에 있다. 이번에는 D번에서 막히면서 느려져버렸다. A번 아카라카 2 (32652, B3) A번 문제 풀이 연속 부분 문자열로 AKARAKA를 n개 만드는 문제이다. AKA가 뒤에 3개 있으니 계속해서 RAKA를 붙이면 만들 수 있다. int main() { ios_base ::sync_...

백준 마라톤 (코스41) (8/8) 이번에도 다 풀 수 있었다. 이분 그래프를 알게 됐어요. 점점 알고리즘 공부에 할애할 시간이 줄어들고 있다. 다음 마라톤에는 플레 문제가 나오지 않을까 기대가 되네요. Virus (13775, B1) A번 문제 풀이 암호학 시저 암호? 같은건데 key가 1씩 증가한다. 그냥 역으로 구현하면 해독이 된다....

Alkon 2주차 챌린지 (6/6) 저번이랑 똑같은 사진 같지만 다른 주차 다른 문제이다. A번 오버플로우와 모듈러 (15818, B3) A번 문제 풀이 주어지는 숫자들을 모두 곱한 값에 모듈러 연산을 한 값을 출력하는 문제이다. 간단하게 곱하는 모든 숫자들에 모듈러 연산을 하며, 마지막 결과에도 한번 더 해주면 된다. int main(...

트리 트리 문제 그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다. 트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개,...

이분 그래프 이분 그래프 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테...

halting problem 우리 교수님이 항상 이 halting problem에 대한 이야기를 첫 수업마다 한다. 재밌는 이야기라 정리해보자. 이발사 문제 우선 이발사 문제에 대해 알아보자. 어떤 마을에는 이발사가 한 명 있는데 이 이발사는 스스로 이발하지 않는 사람 모두 이발을 해준다. 그러면 이발사의 머리는 누가 이발을 하는가? 만약 스스...

트리의 지름 트리의 지름 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000) 둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정...

최대공약수와 최소공배수 수학 관련 문제에서 가장 많이 사용하는 것은 이전 글인 소수와 최대공약수인 것 같다. 보통 최대 공약수를 구하는 문제에서는 유클리드 호제법을 이용한 알고리즘을 사용한다. 시간 복잡도는 O(lonN)이고, 이 글에서는 간단하게 증명을 해보려고 한다. 증명 A와 B라는 두 숫자의 최대 공약수 G를 구해보자. 증명할 내용은 a...

소수 판별 수학 관련된 문제를 풀다보면 어떤 숫자가 소수인지 아닌지를 판별해야 할 때가 많다. 어떻게 어떤 수가 소수인지 아닌지 알 수 있을까? 소수 우선 소수란 자기 자신과 1로만 나누어 떨어지는 수이다. 이 때 1은 제외한다. 2, 3, 5, 7... 숫자 1개가 주어졌을 때 소수인지 판별하는 방법부터 보자. 시간 복잡도 O(N) 가장 간...