방앗간 개발자

문제 출처:https://www.acmicpc.net/problem/6064

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다. 

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라. 

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

문제 자체가 약간 난해한 면이 있지만 몇번 읽어보면 규칙을 파악 할 수 있을겁니다.

해를 표현하는 방법은 문제에 나와있는 그대로 <M:N> 이 주어졌을때 년도를 <X:Y>로 표현한다면 X,Y는 1,1로 시작해서 

1씩 증가하며 X>M이 되면 X%M, Y>N이 되면 Y%N을 해주면 됩니다. 

따라서 문제로 M,N,X,Y가 주어졌을때 <X,Y> 가 몇번째 해인지 알기 위해선 위의 조건을 적용시켜 1,1부터 시작하여 증가시키

며 검사하면 됩니다. 그러나 문제는 <X,Y>로 표현할 수 없는 해가 주어진다는 것인데 이 때 무한 반복을 하지 않으려면 처음

부터  반복의 끝을 정해주어야 합니다.

그리고 이 반복의 끝이 바로 문제에 나오는 '종말의 해' 인데 이 날을 구하는 방법은 바로 N과 M의 최소 공배수를 구하는 것입

니다. 이 N과 M의 최소공배수를 G라고 한다면 이 G번째 해가 달력의 마지막이기 때문에 첫번째 해부터 G번째 해까지 <X,Y>

로 표현되는 해가 없다면 <X,Y> 가 유효하지 않은 표현이고 따라서 -1을 출력해주면 되는겁니다.

최소 공배수를 구하는 방법은 유클리드 호제법을 이용하였습니다. 

최대 공약수 공식(gcd)

1. a,b: 최대 공약수를 구하고자 하는 두 수 

2. r: a를 b로 나눈 나머지 r=a%b

3. 식: gcd(a,b)=gcd(b,r) 을 b가 0이 될때까지 반복해주면 됩니다.

최소 공배수 공식(lcm)

1. a,b: 최소 공배수를 구하고자 하는 두 수

2. gcd(a,b): a,b의 최대 공약수

3 식: a*b/gcd(a,b)

전체 코드입니다.

문제 출처:https://www.acmicpc.net/problem/1652

일 년 동안 세계일주를 하던 영식이는 여행을 하다 너무 피곤해서 근처에 있는 코레스코 콘도에서 하룻밤 잠을 자기로 하고 방을 잡았다.

코레스코 콘도에 있는 방은 NxN의 정사각형모양으로 생겼다. 방 안에는 옮길 수 없는 짐들이 이것저것 많이 있어서 영식이의 누울 자리를 차지하고 있었다. 영식이는 이 열악한 환경에서 누울 수 있는 자리를 찾아야 한다. 영식이가 누울 수 있는 자리에는 조건이 있다. 똑바로 연속해서 2칸 이상의 빈 칸이 존재하면 그 곳에 몸을 양 옆으로 쭉 뻗으면서 누울 수 있다. 가로로 누울 수도 있고 세로로 누울 수도 있다. 누울 때는 무조건 몸을 쭉 뻗기 때문에 반드시 벽이나 짐에 닿게 된다. (중간에 어정쩡하게 눕는 경우가 없다.)

만약 방의 구조가 위의 그림처럼 생겼다면, 가로로 누울 수 있는 자리는 5개이고, 세로로 누울 수 있는 자리는 4개 이다. 방의 크기 N과 방의 구조가 주어졌을 때, 가로로 누울 수 있는 자리와 세로로 누울 수 있는 자리의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다.

첫째 줄에 가로로 누울 수 있는 자리와 세로로 누울 수 있는 자리의 개수를 출력한다.

문제를 이해만 한다면 복잡한 알고리즘 없이 몇가지 조건만 가지고 풀 수 있는 문제입니다.

예제로만 보면 설명이 애매한 부분이 있어 그림을 하나 첨부합니다.

위 그림의 가로로 누울 수 있는 부분 첫 번째 줄을 보면 벽 하나를 두고 양 옆으로 2칸씩 있기 때문에 한 줄에 누울 수 있는

자리는 2개가 됩니다. 전 처음에 이부분을 생각하지 않고 풀었다가 뒤늦게 깨닫고 수정했습니다. 

이 부분만 주의하면서 임의의 cnt변수를 하나 만든뒤 2차원 배열을 한 줄씩 탐색하며 빈 방이 나오면 1씩 증가시키다 

cnt == 2가 되면 누울 수 있는 자리라 판단하여 체크해주고 계속 탐색하다가 벽이 나올경우 cnt 변수를 0으로 초기화 

시켜주면 됩니다. 

코드는 짧고 이해하기 어렵지 않으므로 전체 코드를 한번에 올리겠습니다.

문제 출처:https://www.acmicpc.net/problem/2108

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최대값과 최소값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절대값은 4,000을 넘지 않는다.

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

1. 산술평균은 소수점 첫째 자리에서 반올림 한 값을 출력해야 하기 때문에 N으로 나눌때 double형으로 나누어 주고 printf출력할때 "%.0f" 로 출력해주면 소수점을 생략하고 반올림하여 출력해줍니다. 

2. 중앙값은 N이 홀수이기 때문에 배열이나 벡터를 정렬한뒤 N/2부분을 출력해주면 됩니다.

3. 최빈값은 약간 복잡한데  입력으로 들어오는 정수가 -4000~4000이기 때문에 8001의 크기를 가지는 배열 하나를 선언해주고 -4000~-1까지는 양수로 바꿔주고 바꿔준 값의 배열 인덱스를 +1 해줍니다. 

 1~4000까지는 +4000을 해주고 그 값의 배열 인덱스를 +1 해줍니다.

 이 뒤에 배열의 최대값을 구하고 배열을 전부 탐색하며 최대값을 가진 인덱스를 모두 벡터에 넣어주는데 이 과정에서 1~4000까지는 음수화 해주고 4001~8000까지는 -4000을 해주어야 합니다.

 마지막으로 벡터를 오름차순 정렬한뒤 벡터의 사이즈가 1이면 첫번째 값을 출력해주고 사이즈가 1 이상이면 2번째 값을 출력해주면 됩니다.

4. 최대값과 최소값은 입력을 받을때 구해주는게 가장 좋습니다만 중앙값을 구하기 위해 정렬을 수행했으므로 벡터의 첫번째와 마지막 값을 출력해주면 됩니다.

문제 출처:https://www.acmicpc.net/problem/1629

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

이 문제는 얼핏보면 그냥 A의 제곱을 구하는 간단한 문제로 보입니다. 그러나 막상 문제를 풀어보면 2가지 문제점을 발견하게 됩니다. 

1. 숫자의 범위가 자료형의 표현 범위보다 커진다.

2. O(n)의 시간복잡도로 문제를 풀어도 시간제한에 걸린다.  

1번의 해결방법으론 long long 자료형을 사용하는 것입니다.

그러나 이러한 자료형을 사용하더라도 문제는 제곱수이기 때문에 적은 연산에도 숫자가 기하급수적으로 커지게 되고 결과적으로 long long자료형의 범위도 넘어가버리게 됩니다.

따라서 연산을 할때마다 C로 나눈 나머지로 값을 바꿔주어야 자료형의 범위를 넘지 않고 계산이 가능합니다.

2번은 B의 크기가 최대 2,147,483,647인데 이 수를 for문을 사용하여 그대로 2,147,483,647번 반복한다면 대략 1억번의 반복을 1초라 생각했을때 21초나 걸리게 되어 문제의 시간제한인 2초를 훨씬 넘기게 되버립니다.

따라서 이 문제는 for문을 사용하지 않고 함수의 재귀를 이용하는 분할정복 알고리즘을 이용하여 풀어야 O(log n)의 시간복잡도를 가지게 되고 문제의 최대값이 들어와도 바로 결과값을 나타낼수 있습니다.

분할정복 알고리즘이란 - https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98