1543 문서 검색

문자열 a중에 문자열 b가 겹치지 않고 몇번 들어있는지를 판단하는 문제이다.

a를 시작부터 끝까지 반복하면서 b가 들어있는지 검사하고, b와 매칭이 되면 b의 길이만큼 a를 증가시켜주면 된다.

소스

1153 네 개의 소수

주어진 수를 4개의 소수의 합으로 나타내는 문제이다.

이 문제를 풀기위해선 다음의 가설을 알아야 한다.

"2를 제외한 모든 짝수는 두 소수의 합으로 나타낼 수 있다."

이것은 가설로 아직 증명되지 않았지만, 충분히 큰 수에서도 이 가설이 적용된다.

이것을 어떻게 사용해야 할까? 바로 4개의 소수를 2개의 소수로 바꾸면 된다.

주어진 수가 짝수라면 2, 2 를 빼버리면 다른 짝수가 될 것이다. 그 짝수는 다시 두 소수의 합으로 나타낼 수 있다!

만약 주어진 수가 홀수라면 2, 3 을 빼버리면 마찬가지로 다른 짝수가 되서 네 소수를 구할 수 있다.

단, 주어진 수가 8 미만이라면 2 2 2 2 로도 만들 수 없으므로 -1을 출력한다.

두 소수의 합은 이전에도 다뤘지만 에라토스테네스의 체를 이용해서 소수를 구하고 반복을 통해 합이 자신이 되는 두 소수를 찾아내면 된다.

소스

1439 뒤집기

이진수가 주어지면, 연속된 범위의 숫자를 뒤집어서 모두 똑같은 숫자가 되도록 할 때, 최소 몇번 뒤집으면 되는지를 판단하는 문제이다. 뒤집는다는건 0은 1로, 1은 0으로 바꾸는것을 말한다.

이 문제를 푸는 방법은 간단하다. 연속된 숫자를 한 덩어리로 보고, 0의 덩어리의 개수와 1의 덩어리의 개수를 구해서 둘중 작은것을 뒤집어주면 답이 나오게 된다.

소스

2993 삼등분

1251 단어 나누기 와 똑같은 문제이다.

소스

1541 잃어버린 괄호

덧셈과 뺄셈으로 이루어진 식이 주어질 때, 원하는곳에 괄호를 넣어 식의 값을 최소로 하려고 한다. 이 때의 최솟값을 구하는 문제이다.

생각해보면 뺄셈이 나온 순간부터 무조건 빼주기만하면 된다는걸 알 수 있다.

따라서 뺄셈이 나오기전까진 계속 더해주다가, 뺄셈이 나오는순간 그 다음 식은 전부 빼주면 된다.

소스

8892 팰린드롬

주어진 단어중에 서로 다른 두 단어를 조합해서 팰린드롬을 만들 수 있으면 그것을 출력하는 문제이다.

문제대로 서로 다른 두 단어를 골라 조합하고 그것이 팰린드롬인지 검사해주면 된다.

소스

6504 킬로미터를 마일로

주어진 숫자를 피보나치 진법의 2진수로 나타내고, 오른쪽으로 1만큼 쉬프트 시켜서 다시 10진수로 바꿔 출력하는 문제이다.

일단 피보나치 숫자의 목록을 미리 만들어두고, 큰 피보나치 부터 시작해서 주어진 숫자보다 작거나 같으면 숫자를 그만큼 제하면서 피보나치 진수에 체크해준다.

그렇게 구한 수를 오른쪽으로 1씩 쉬프트해주고, 반대방법으로 일반수를 구해주면 된다.

소스

1992 쿼드 트리

흑백영상을 압축하는 방법중 하나로 쿼드 트리가 있다고 한다.
쿼드 트리는 흑을 1, 백을 0으로 놓고 한 숫자로 가득 차 있으면 그 숫자를 반환하고, 섞여있다면 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래의 4면으로 나눠서 다시 검사하는 방법이다.
다시 검사할 때마다 괄호로 묶이게 된다.


위 그림을 쿼드 트리로 나타내보면

(0(0011)(0(0111)01)1) 가 된다.

이것은 단순한 구현문제로 면을 전부 검사해서 같다면 같은 숫자를 출력하고, 다르다면 4방향으로 재귀하여 같은 것을 반복한다. 단, 재귀할 때 시작과 끝에 괄호를 출력하여주면 된다.

소스

5636 소수 부분 문자열

숫자열 안에 가장 큰 소수를 찾는 문제이다. 들어있는 소수는 100000 보다 작다고 한다.

에라토스테네스의 체로 100000이하의 소수를 구하고, 숫자열의 크기를 5부터 시작해서 그 단위만큼 끊어서 소수인지를 검사해주면된다. 만약 그 단위에 소수가없다면 단위를 줄여서 검사한다.

소스

10214 Baseball

야구스코어를 주면 누가 이겼는지를 판별하는 문제이다.

점수를 쌓아주고 비교하면 된다.

소스

1803 무술 연습

두줄에 N명의 사람들이 있고 서로 상대편의 누군가를 조준하고 있다.
조준하는 사람들에게 활을 쏘려고 한다. 그러나 사람이 다치지 않도록 일부는 방패를 들어야 한다.  방패는 누군가에게 조준당하고 있는 사람만 들어야 한다고 할 때
각 사람마다 활이나 방패중 어떤것을 들어야 하는가를 출력하는 문제이다.

이 문제를 풀기위해선 다음의 정리가 필요하다.
1. 아무한태도 지목당하지 않은 사람은 무조건 활을 들어야 한다.
2. 1번의 활을 든 사람이 조준하는 사람은 무조건 방패를 들어야 한다.
3. 2번의 방패를 든 사람은 다른사람을 조준하지 못한다.

위 정리를 이용하여 계속 1번에 해당하는 사람을 찾아주면 된다. 단, 그냥 짰다가는 시간초과가 날 수 있으니 조심하자.

소스

2875 대회 or 인턴

남자 1 여자 2명씩 짝지어서 팀으로 대회에 나가는데 K 명을 제외 해야 한다.
이 때 최대 몇팀이 출전 가능한가를 묻는 문제이다.

일단 K를 무시한 채 몇팀이 나갈수있는지 계산해준다. 그렇게 되면 여자나 남자의 수가 남을탠데, 그만큼을 k에 포함시켜주고, 그래도 k가 남았으면 팀을 하나씩 빼서 3씩 포함시켜준다.

K가 다 채워질 때 남은 팀을 출력하면 된다.

소스

10211 MaximumSubarray

최대 부분합을 구하는 문제이다.

전에 풀은 부분합과 같이 계속 더해주면서 최대값을 구하고, 더한값이 음수가 되면 0으로 초기화해서 계속 하면 된다.

소스

10212 Mystery

고려대와 연세대 어디가 더 뛰어난지를 맞추는 문제이다.

사실 어느한쪽으로 정해지지 않고 값이 1초를 주기로 바뀌게 된다.

따라서 랜덤을 구현해야할 필요가 있다.

그러나 랜덤함수를 쓰자니 time함수를 막아놔서 사용을 못한다. 시드를 바꿀 수 없다는 소리이다.

불규칙한 것을 이용해야 하는데 그중 하나가 동적할당 메모리이다.

정해지지 않았기때문에 동적할당을 이용해서 랜덤을 돌려주면 된다.

소스

2448 별찍기 11

아래 별찍기 처럼 예제를 보고 입력크기에 따라 출력하는 문제이다.

이번에도 예제를 보도록 하자.

이 문제는 간단하게 설명하겠다. 왼쪽,오른쪽 공백은 높이 - 1이고,
맨 위는 그냥 삼각형을 하나 그려준다. 그리고 그 밑에줄엔 위 삼각형을 복제한것을 두개 연달아 그려준다. 그리고 그걸 밑에도 반복해주면 된다.
삼각형을 복제한다기보단, 별이 찍힌 직사각형의 형태로 복제한다고 생각하면 삼각형 사이의 공백관리도 편할것이다.

소스

2447 별찍기 10

예제로 주어진 별찍기를 보고 패턴을 예측해서 주어진 입력에 맞는 크기의 별을 찍는 문제이다.

별찍기라해서 방심해선안된다. 생각보다 까다롭기 때문이다. 예제를 살펴보자.

쳐다만봐도 다른 문제를 풀고싶지 않은가?

사실 본인도 한번 포기했다가 다시 도전한 문제이다.

이 문제는 패턴을 잘 생각해야하는데, 내가 찾아낸 패턴은 다음과 같다.

잘 보면 중간마다 별이 끊어져 있는것을 알 수 있는데, 첫 줄을 0이라고 놓고 별이 새롭게 끊켜지는 줄 번호를 살펴보자.

1 <= L < 2

3 <= L < 6

9 <= L < 18

규칙이 보이는가? L은 1부터 시작해서 3배로 증가하는 위치마다 별이 끊키게 된다.

이 시작 라인을 start, 경계 라인을 end라고 하면

start = 1, start = start * 3

end = start * 2

과 같은 관계가 된다.

여기서 또 알 수 있는건, 각 줄의 끊어지는 위치도 start와 관계가 있다는 것이다.

라인 1을 보자. 3칸마다 1칸씩 끊어져 있는것을 볼 수 있을 것이다.

라인 3도 보자. 9칸마다 3칸씩 끊어져 있는것을 볼 수 있다.


그렇다. 한번에 끊어지는 간격도 start * 3칸 마다 중앙의 start 칸씩 끊어져 있게 된다.
그런데 라인 4를 보면  3칸에 1칸씩도 끊어져 있다. 이것은 과거에 만들어져 있던 라인을 가지고 끊기 때문이다. 과거에 참고하는 라인또한 현재라인 - start 이다.

마지막으로 현재 라인이 end로 설정한 라인과 같다면, 과거에 만들어준 별을 그대로 다시 출력해야 한다. 그것도 0 <= L < start 까지이다.

설명한대로 구현해준다면 답을 얻을 수 있다.

소스

7570 줄 세우기

1~N번의 사람이 아무 순서로 놓아져 있다. 이 때 각 번호의 사람을 맨 앞, 맨 뒤로 보내는 방법으로 오름차순 정렬하려 할 때, 최소 몇번 보내야 하는가를 알아내는 문제이다.

이전에 풀었던 줄 세우기 문제와 비슷한데, 다른점은 이전것은 어디로 보내도 괜찮았지만, 이번 문제는 맨 앞이나 맨 뒤로만 보내야 한다는 점이다.

이 문제를 풀기위해선 먼저 어떤것을 밝혀내야 최소를 구할 수 있는가를 알아내야 한다. 많은 고민을 통해 알아낸것은 다음가 같다.

카운트를 0으로 초기화 하고, 자기 바로 다음 번호가 자신의 뒤에 위치해있다면 카운트를 1 증가시키고 그 다음 숫자에 대해 똑같이 반복해준다.

이 때 카운트가 최대인 경우를 구해서 N - 최대를 해주면 답이 나온다.

이유는 예를통해 설명해보자.

5 2 4 1 3 이라는 숫자가 있다면, 위 방법을 통해 찾아보면

2 3 이 연속되므로 최대치는 2이고 답은 5 - 2 = 3이다.
2와 3을 고정 시키고 2 와 3 사이에 있는 4 , 1 과 나머지를 앞이나 뒤로 빼버리면 되기 때문이다.

2 4를 고정시키면 3을 2와 4 사이에 넣어야 하므로 4를 움직여야만 한다. 따라서 고정이 불가능하다.

따라서 연속된 숫자만이 사이에 넣을 필요가 없으므로 고정이 가능하다.

줄 세우기 문제는 어떤 숫자를 고정시킬지가 중요한것 같다.

소스

7571 점 모으기

좌표평면에 점들이 있고, 점들은 상,하,좌,우로만 움직인다 할 때, 모든점을 한 곳에 모을 때 걸리는 전체 이동횟수의 최솟값을 구하는 문제이다.

나는 이 문제를 푸는 방법을 발견해내지 못했는데, 친구의 도움으로 알게 되었다.
점들의 x좌표와 y좌표를 각각 오름차순으로 정렬해주고, 점의개수 / 2 번째 x,y좌표가 한곳에 모을 때 최소가 되는 좌표이다.
원리는 아직 정확히 이해하지 못했다.

소스

2468 안전 영역

어떤 지역에 좌표마다 높이가 주어지고, 일정 높이 이하의 지역은 물에 잠긴다고 할 때, 물에 잠겨서 얻을수 있는 가장 많은 분단된 지역의 수를 구하는 문제이다.

단순히 물에 잠기는 높이를 0부터 최대까지 반복하면서 잠긴 지역을 처리해주고, 분단된 지역의 수를 구하면 된다.

소스

2057 팩토리얼 분해

어떤 수 N을 서로 다른 팩토리얼들의 합으로 나타낼 수 있는가를 알아내는 문제이다.
팩토리얼엔 0!도 포함된다.

N보다 작은 팩토리얼을 모두 구해서 재귀를 통해 부분만 덧셈해주면서 답을 구해주면 된다.
시간복잡도가 꽤 크지만 팩토리얼 개수가 20개밖에 되지않아서 금방 찾을 수 있다.

소스

2153 소수 단어

알파벳을 숫자로 바꿔서 더한 다음 그 수가 소수인지 아닌지를 판별하는 문제이다.

문제에 나온 대로만 구현해주면 된다. 소수판별도 시간복잡도 생각안하고 풀어도 된다.

소스

1254 팰린드롬 만들기

문자열이 주어지면 뒤에 임의의 문자들을 붙여서 팰린드롬을 만드는 문제이다.

마땅한 방법이 떠오르질 않아서 문자열 길이가짧다는걸 이용해 가능한 경우를 전부 구해주었다. 문자열의 맨 뒤에 앞의 문자를 1글자씩 늘리면서 거꾸로 붙이고, 그 문자열이 팰린드롬인지 아닌지를 검사하여 주면 된다.

소스

1701 소녀시대 공식팬클럽 회장

주어진 문자열에서 두번이상 반복되는 부분문자열중 길이가 가장 큰것의 길이를 구하는 문제이다.

이 문제도 여러 풀이방법이 존재하는데, 내가 사용한 방법은 문자열을 앞에서부터 잘라가면서 찾을 문자열을 만들고, kmp를 이용해 매칭해주다가 두번 반복되는 최대값을 찾아주는 것이다.

kmp는 원래 두 문자열이 완전 매칭될때를 찾는것인데, 그러지않고 매칭된 상태마다 카운트 해주는 배열을 두어서 카운트가 2이상인 상태중에 최대값을 찾는다.

다른 빠른방법들이 많은거같은데 찾아보아야겠다.

소스

KMP

KMP는 유명한 문자열 매칭 알고리즘중 하나이다.
찾을 문자열에 대해 회귀할 index를 표시해주는 pi를 이용하여 문자열을 검색한다.
최악의 경우 O(nk)의 시간복잡도를 갖는다. n,k는 각각 찾을 문자열과 검색할 문자열의 길이를 나타낸다.

소스

5582 공통 부분 문자열

두 문자열의 가장 긴 공통 부분 문자열을 찾는 문제이다.
LCS랑은 좀 다른데, LCS는 떨어져 있는 문자도 부분으로 취급했지만, 여기선 붙어있는 문자열만 찾아야 한다.

여러 방법이 있는데, 내가 사용한 방법은 KMP를 이용해서 찾을 문자열을 앞에서부터 한개씩 끊어가며, 가장 매칭이 많이된 경우를 찾아주었다.

소스

1958 LCS 3

두 문자열의 LCS가 아닌 세 문자열의 LCS를 구하는 문제이다.

처음엔 단순하게 MIN(LCS(a,b),LCS(b,c),LCS(c,a)) 로 구하려했으나 WA를 받았고..
그 다음으로 생각한게 LCS를 확장하는것이다.

세 문자열의 길이를 각각 p , q , r 이라 할 때,
LCS는 O(pq)의 시간복잡도를 갖지만, 이것을 확장하여 세 문자열로 처리하게끔 하면
O(pqr) 의 시간복잡도를 갖는다. 형식을 똑같이 유지하며 확장시켜주면 답을 구할 수 있다.

소스

9252 LCS 2

두 문자열의 LCS 한 값과, 값에 해당하는 실제 문자열을 출력하는 문제이다.

여러 방법이 있는데, 내가 사용한 방법은 LCS를 구하면서 부분문자열도 같이 가져오는 방법이다. 사실 좋은 방법은 아니다.

소스

LCS

두 수열에서 두 수열의 부분수열이 되는것중 길이가 가장 긴것을 LCS(최장 공통 부분 수열)이라고 한다. LCS 를 DP를 이용하여 구하는 알고리즘을 수록한다.

소스

9251 LCS

두 수열에서 두 수열의 부분수열이 되는것중 길이가 가장 긴것을 LCS(최장 공통 부분 수열)이라고 한다. 이 때 두 문자열의 LCS값을 구하는 문제이다.

이 알고리즘은 널리 알려져있어서 나도 그것을 이용했다. DP로 해결이 가능하며 시간복잡도는 O(n*m) 이다. n,m은 각각 두 수열의 길이를 의미한다.

소스

1081 합

L 이상 U 이하의 모든 자연수의 각 자리수의 합을 구하는 문제이다.

0이 몇개? 문제의 확장으로 생각할 수 있는데,
이 문제 또한 예전에 풀은 문제에서 빌려왔다. 원리는 역시 잘 이해되지 않는다.
마치 고대문명을 발견하는 느낌이랄까..
예전에 풀은 문제는 각 자리수의 개수를 구하는 문제였다.
따라서 구한 개수를 그 수만큼 곱해줘서 누적하면 답이 나온다.

소스

5704 팬그램

문장에 알파벳이 모두 사용되었나를 판단하는 문제이다.

알파벳을 인덱스로 두는 배열을 잡고 문장을 한글자씩 검사하면서 알파벳 배열을 증가시킨 다음 값이 0인 인덱스가 있다면 N 없으면 Y를 출력하면 된다.

소스

1251 단어 나누기

단어를 3등분해서 각 등분을 거꾸로 뒤집어서 이어붙였을 때, 사전순으로 가장 앞서는것을 출력하는 문제이다.

이것저것 고민해보다 결국 길이가 짧다는것을 고려해서 가능한 3등분을 전부해주고 거꾸로 뒤집고 합친다음 비교해줬다.

임시 변수에 각 3등분을 뒤집은것을 저장하고, 사전순으로 높은것을 저장할 변수와 비교를해주어서 갱신하도록 구현하면 된다.

소스

1652 누울 자리를 찾아라

빈 공간과 장애물이 있는 맵이 주어지면,

양 끝이 벽이나 장애물을 등지면서 가로나 세로로 2칸이상의 공간이 비어있는 장소의 개수를 구하는 문제이다.

그냥 왼쪽 맨 위 좌표부터 오른쪽, 아래쪽으로 검사하면서 2칸이상의 공간과 장애물 or 벽이 있으면 증가시켜주도록 하면 된다.

소스

3034 앵그리 창영

가로세로 길이 w,h인 성냥갑안에 길이 l 인 성냥이 들어가는가를 판단하는 문제이다.

성냥갑안에 넣을수있는 성냥크기의 최대값은 root(w*w+h*h)이다.
이 값으로 비교해주면 된다.

소스

5691 평균 중앙값 문제

A B를 주면, A B C의 평균이 중앙값과 같아지는 가장 작은 C를 구하는 문제이다.

이 문제는 수식으로 표현이 가능하다.

B가 중앙값이라 가정하면,

(A+B+C)/3=B
A+B+C=3B
A+C=2B

이렇게 된다. 이 때 C는 가장 작다고 했으니, 중앙값은 A B 중에 작은것이 된다.
따라서 C = 2*MIN(A,B) - MAX(A,B) 를 구해주면 답이 나온다.

소스

1904 01타일

00과 1로 길이 N을 채우려 할 때 가능한 경우의 수를 구하는 문제이다.

몇번 계산해보면 피보나치로 증가하는것을 알 수 있다.

따라서 피보나치를 구해주면되는데, 값이 너무 커지기 때문에 나머지연산을 해주어야 한다.
피보나치에 나머지 연산을 적용하려면 두 수를 더해주는 곳에 적용해주면 된다.

소스

4276 0이 몇 개?

a부터 b사이의 숫자의 0의 개수의 합을 구하는 문제이다.

1부터 b까지의 0의 개수에서 1부터 a까지의 0의 개수를 빼주고 a의 0의 개수를 더해주면 된다.

1부터 n까지의 0의 개수를 구하는것은 내가 예전에 푼 문제에서 가져왔는데
몇번봐도 이해가 잘 안간다..
과거의 나는 굉장히 대단했던거같다..

소스

7576 토마토

토마토 상자에 각 칸의 상태가 다음과 같다.
1 - 익은 토마토
0 - 덜익은 토마토
-1 - 토마토가 없음
이 때 익은 토마토는 하루가 지나면 상하좌우의 토마토를 익게 만든다.

상자의 상태가 주어질 때 토마토가 전부 익으려면 몇일이 걸리는지를 구하는 문제이다.

이 문제는 BFS를 이용하면 간단하게 해결이 가능하다.
익은 토마토를 큐안에 넣고, 큐에서 꺼내면서 상하좌우 토마토를 익게끔 만들어 주면 된다.
이 때 하루에 한번만 익힌다는것에 주의하자. 반복은 그날에 익은 토마토가 없을때까지 지속하면 된다. 만약 모든 반복이 끝났는데 상자에 덜익은 토마토가 있다면 -1을 출력하면 된다.

소스

1695 팰린드롬 만들기

앞에서 부터 보나 뒤에서 부터 보나 같은 수열인 수열을 팰린드롬 이라고 한다.
이 때 주어진 수열에서 숫자를 몇개 끼워넣어 팰린드롬을 만든다고 할 때,  끼워넣는 숫자의 최소개수를 구하는 문제이다.

이 문제는 혼자힘으로 풀지못해 스터디 그룹에서 해결방법을 알아냈는데, 재귀를 이용한 방법이었다.

수열의 양 끝 숫자가 같으면 양 끝 범위를 1씩 줄여서 재귀하고,
다르면 왼쪽에서 하나를 줄여서 재귀 한것과, 오른쪽에서 하나를 줄여서 재귀한것 중 최솟값에서 1을 더한값을 그 범위의 최소개수로 삼는다.

단순히 이렇게 재귀하면 TLE가 뜨게 되므로 DP를 이용해주면 ACCEPT를 받을 수 있다.
다만 이 방법은 메모리와 시간을 꽤 많이 잡아먹는 방법이다. 다른 풀이방법은 O(n^2)으로 풀 수 있는듯 하다.

소스

2631 줄세우기

1~N 까지의 N개의 숫자를 오름차순으로 정렬해야 한다. 이 때 어떤 숫자를 다른 숫자의 앞이나 뒤에 끼워넣는식으로 정렬을 하려 할 때, 이 횟수의 최솟값을 찾는 문제이다.

꽤나 고생한 문제인데 풀이법은 간단하다.
점점 증가하는 수열의 길이가 가장 긴것을 찾으면 된다. 이어져있는것이 아니라 띄어져있어도 마찬가지인데, 예를들면

3 7 5 2 6 1 4 라고 하면,

3 7
3 5 6
5 6
2 6
2 4
1 4

이런식으로 증가하는걸 찾았을 때 가장 긴것의 길이, 즉 위 경우에선 3이 나온다.
이 말은 이미 정렬되어있는게 3개라는 뜻이므로 나머지 4개만 끼워넣으면 된다.
따라서 이 예제의 답은 4이다.

위와같은 방법으로 답을 구해주면 된다. 길이를 구해주는것은 재귀와 DP를 이용하였다.

소스

3067 Coins

9084 동전 문제와 완전 같은 문제로 DP를 이용하면 된다.

소스

4256 트리

이진 트리의 전위 순회와 중위 순회한 결과를 가지고 후위 순회한 결과를 출력하는 문제이다.

이 문제를 풀기 위해선 전위 순회한 결과와 중위 순회한 결과의 성질을 눈치채야 한다.
이 부분은 설명이 복잡하니 예를들어 설명하자면,
전위 순회 : 3 6 5 4 8 7 1 2
중위 순회 : 5 6 8 4 3 1 2 7

전위 순회는 시작부터 결과를 출력하기 때문에 맨 처음 나온 숫자는 루트노드가 된다.
그 노드를 중위 순회한 결과에서 찾아보면, 5번째에 위치한다는 것을 알 수 있다.
중위 순회의 성질을 잘 생각해보면, 루트노드 앞에 나온 결과는 전부 루트노드의 left, 뒤에 나온 결과는 right 자식이다.

위에 나온 결과로 보아 루트노드(3)의 왼쪽 자식은 4개, 오른쪽 자식은 3개이다.
이것은 전위 순회에도 찾아볼 수 있는데, 루트노드의 다음 4개가 왼쪽 자식이고, 그 다음 3개가 오른쪽 자식이 된다.

이것은 루트노드에서만 해당되는것이 아니라 자식에도 적용이 가능하다.
루트의 왼쪽 으로 가보면, 전위 순회의 루트 다음 숫자가 6이기 때문에 6이 루트노드의 왼쪽 자식노드이다.  중위 순회에서 6을 찾아주면 두번째에 있게 되는데, 여기서도 앞에있는 5는 6의 왼쪽 자식이고, 뒤에있는 8 4는 오른쪽 자식이 된다. 이런 과정을 왼쪽으로부터 오른쪽 까지 재귀하면서 마지막에 결과를 출력해주면 후위순위한 결과가 된다.

소스

8901 화학 제품

화학 제품의 양 a,b,c가 주어지고, 두 화학제품을 섞었을 때의 가중치 ab, bc, ca가 주어졌을 때, 화학 제품으로 만들 수 있는 가중치의 합의 최대값을 구하는 문제이다.

너무 greedy 하게 접근하려 해서 상당히 애를 먹은 문제인데, 풀고나면 방법은 간단하다.

우선 ab를 몇번 섞을것인가에 대해 반복을 한다.

한번도 안섞을 수도 있고, 있는대로 섞을 수도 있다.

그 상태에서 bc를 몇번 섞을것인가에 대해 반복을 한다.

그러면 자연스럽게 ca를 몇번 섞을수 있는가를 정할 수 있는데,

이렇게 구한 ab bc ca의 수치를 합한것 중의 최대값을 구하면 된다.

소스

1720 타일 코드

2*N의 타일을 2*1, 2*2 의 조각으로 채울 때, 좌우 대칭이 되는 경우를 제외한 나머지 경우를 구하는 문제이다.

우선 좌우 대칭을 고려하지 않고 경우의 수를 측정하면
f(n) = f(n-1) + 2*f(n-2) 가 된다.

좌우 대칭을 제외 하는것은,
f(n) 에서 좌우대칭이 되지 않는 조각의 수를 뺀것을 2로 나누어 주고,
다시 그 값을 f(n) 에서 빼주면 된다.

좌우 대칭이 되지 않는 조각의 수는 n이 짝수이면 f(n/2 + 1) 홀수이면 f((n-1)/2)  로 구할 수 있다.

왜 저렇게 풀리는지는 정확히 모르겠다.

소스

2579 계단 오르기

계단을 오르는데, 계단마다 각각 가중치가 있고, 한번에 1칸이나 2칸씩 올라갈 수 있다.
하지만 세칸연속 밟아선 안된다. 예를들면 첫번째 계단, 두번째 계단을 밟았다면 세번째 계단은 밟아선 안된다는 뜻이다. 그리고 마지막 계단은 무조건 밟아야만 할 때, 가중치의 합이 가장 큰 경우를 고르는 문제이다.

당연하게도  DP로 해결하는 문제이다.
해당 계단에 몇번의 기회(세칸연속 밟지 않기위한 기회)로 그 때까지의 가중치의합이 최대 몇인지를 누적해가면서 마지막 계단의 결과를 구해주면 답이 나오게 된다.

소스

4084 Viva la Diferencia

네 개의 양의 정수 a, b, c, d가 있을 때, 아래와 같이 차이를 계산할 수 있다.
|a-b| |b-c| |c-d |d-a|
이렇게 나온 네 개의 수를 이용해서 다시 또 차이를 계산할 수 있다. 이 작업을 모든 네 개의 정수가 같아질 때까지 반복한다.
이 때 총 몇번을 반복하는지를 계산하는 문제이다.

왠지 그냥 계산하면 TLE가 나올법 하지만
힌트를 보니 네 정수가 2^n보다 작으면 3*n 이내에 답이 나온다고 한다.
숫자가 커봐야 n이 31이니 그냥 구해줘도 답이 나오게 된다.

소스

1197 최소 스패닝 트리

주어진 그래프의 최소 스패닝 트리를 구하는 문제이다.
최소 스패닝 트리는 모든 간선을 연결하는 트리중 가중치의 합이 가장 작은것을 말한다.

나는 그래프 알고리즘중에 최소 소패닝트리를 구축하는 알고리즘중 하나인 프림 알고리즘을 이용하여 문제를 해결했다. 프림 알고리즘은 힙구조를 사용할 때 O(E*log(V))의 시간복잡도를 보인다. 여기서 V는 정점의 수이고, E는 간선의 수를 말한다.
그런데 상당히 느린 결과가 나왔다.

다른 사람이 해결한 방법을보니 정렬을 이용하여 해결해주었다.

그래프문제를 항상 그래프 알고리즘으로만 생각하는 버릇을 고쳐야겠다.

소스

1092 배

여러대의 크레인으로 짐을 나르려고 한다. 크레인 마다 실을 수 있는 무게가 정해져있고, 짐의 무게도 제각각이다. 크레인 하나당 1분에 1개씩 나를 수 있다고 할 때, 짐을 다 나르기 위해선 최소 몇분이 필요한지를 구하는 문제이다.

생각보다 까다로운 문제이다. 처음엔 짐을 무게순으로 오름차순 정렬하여 크레인 무게가 되는대로 가져갔으나 WA(Wrong Answer)가 떴다. 왜냐하면 가벼운 짐밖에 들지 못하는 크레인이 들 수 있는것이 사라져버리기 때문이다. 그렇다고 반대로 해줘도 최소 시간은 나오지 않는다.

이 문제를 풀기 위해선 각 크레인이 가져가야 좋은 짐의 개수를 구해야 한다.
예를들어 크레인이 들 수 있는 무게가 6 8 9 이고, 짐의 무게가 2 3 5 7 9라고 하면,
6이 가져가야 좋은 짐은 2 3 5로 3개.
8이 가져가야 좋은 짐은 7로 1개.
9가 가져가야 좋은 짐은 9로 1개가 된다.

만약 9보다 무거운 짐이 존재한다면 옮길 수 가 없으므로 -1을 출력한다.

이렇게 개수를 구해줬다면 루프를 돌면서 하나씩 제거한다.
위 예제에선 1분이 지나면 6 8 9 는 각각 2개 0개 0개가 된다.
2분이 지나면 6은 1개를 제거해서 1개, 8 9 는 0개가 남는데, 이 땐 자신보다 가벼운 무게의 짐을 하나씩 골라가면 된다. 즉, 8이 6이 들어야 좋은 짐을 가져가게 되면 2분에 모든 짐을 나를 수 있다.

위와 같은 방법으로 문제를 해결해주면 된다.

소스

1068 트리

이진 트리의 노드들의 부모노드번호가 주어지고, 지울 노드 번호가 주어질 때, 리프노드의 개수를 구하는 문제이다.

노드 번호가 뒤죽박죽이라 실제 트리구조를 구현하면 풀기가 힘들다. 따라서 배열을 잡고 주어진 부모노드에 자식노드를 추가시키고 루트노드의 번호를 구한다음, 지울 노드번호를 제외한 트리에서 리프노드의 개수를 구해주면 된다.

소스

2491 수열

수열이 연속으로 커지거나 연속으로 작아질 때 길이가 가장 긴것을 구하는 문제이다.

하나씩 반복하면서 구해주면 되는데, 같은 숫자가 이어지는 경우는 잘 고려해서 구현하는것이 중요하다.

내가 사용한 방법은 같은 숫자는 하나로 합쳐버리고 카운트를 나타내는 변수를 따로 두어서 처리해 주었다.

소스

1874 스택

스택에 입력이 1부터 N까지 차례대로 들어온다고 할 때,
출력된 결과를 가지고 Push 와 Pop 여부를 가리는 문제이다.

이 문제를 풀기 위해선 일단 스택처럼 사용할 배열이 필요하다.
배열을 잡아주었으면 입력을 하나씩 받아와 처리하면 되는데,
push와 pop 여부를 알기위해선 입력된 값들의 최대값을 저장하는 max변수가 필요하다.
max변수의 시작은 0이다.

나머지 과정을 예를들어 설명하자면, max 변수의 값이 0인 상태에서 입력으로 4가 들어왔다고 하자.
그러면 우선 4까지 push 됬다는 의미 이므로 Push Push Push Push 가 되고,
4가 출력됬으므로 Pop이 된다.
그러면 스택에 저장되있는값은 1,2,3 이고, max값은 4가 된다.

이 상태에서 다음 입력이 3이라고 하자. 그러면 max보다 작기때문에 push를 한것이 아니고 Pop만 해준것이다. 그러므로 Pop 한번이고 스택의 값은 1,2 가 된다. max값은 변함없다.

이 때, 입력으로 3이아니라 2가들어오면 이것은 잘못된 입력이다. 왜냐하면 2로 가기위해선 2번이 Pop되야하는데 이 과정에서 3이 출력되기 때문이다.

3다음에 6이 들어왔다고 하자. 그러면 max값이 4고, 5 6이 Push된 것이므로
Push Push 가 되고, 6이 출력됬으므로 Pop이 한번 실행된다.
이 때 스택안의 값은 1,2,5가 된다.

이런식으로 스택을 구현해주고 검사를하면 답을 얻을 수 있다.

소스

1173 운동

운동과 휴식을 반복하여 정해진 범위내의 혈압을 유지하며 운동을 하려고한다.
이 때 운동이 끝날때까지 걸리는 시간을 측정하는 문제이다. 운동과 휴식은 각각 1분이라고 가정한다.

이것은 단순한 그리디 문제로, 혈압이 운동할수있을 만큼 낮다면 바로 운동을하고, 그렇지못하면 휴식을 해주면 된다.

소스

9077 지뢰 제거

10000*10000 크기의 좌표평면에 지뢰들의 좌표가 주어질 때, 10*10 크기의 지뢰제거기가 있을 때, 한번에 최대 몇개의 지뢰를 제거할 수 있는가를 묻는 문제이다.

10000*10000을 전부 돌면서 10*10을 검사해주면 당연히 TLE가 나온다.
여기선 한가지 규칙을 정할 수 있는데 바로,
"한 지뢰를 꼭지점에 두어도 최대치를 검사할 수 있다."
이다.
따라서 지뢰들의 위치를 하나부터 검사하면서 10*10 사각형의 네 꼭지점중 한곳에 두고 검사하는것을 네 꼭지점에 대해 반복하면 최대치를 구할 수 있다.

소스

1699 제곱수의 합

모든 자연수는 그보다 작은 자연수들의 제곱의 합으로 나타낼 수 있다고 한다.
이 때 제곱수의 개수가 최소인 경우를 구하는 문제이다.

나는 DP를 이용해서 해당 제곱수로 만들수있는 숫자들에 횟수를 넣어주면서 횟수가 최소인경우만 쌓이게 구현하였다.

소스

3063 게시판

처음에 붙여진 종이가 다음에 붙여진 종이에 가려질 때 처음 종이가 보이는 면적을 구하는 문제이다.

처음엔 좌표평면 배열을 선언해서 점을 찍어서 체크해주려고했는데 점의 개수를 가지고는 제대로된 면적을 구할 수 없었다.

그래서 생각한것이 좌표의 대소를 이용해 겹치는 부분의 면적을 구하는 것이다.

(x1,y1) , (x2,y2) 를 처음 종이의 왼쪽 아래와 오른쪽 위 좌표,
(x3,y3) , (x4,y4) 를 다음 종이의 왼쪽 아래와 오른쪽 위 좌표 라고 하면

겹치는 부분의 면적은 다음과 같다.

(MIN(x2,x4)-MAX(x1,x3))*(MIN(y2,y4)-MAX(y1,y3))

처음 종이의 면적에 저 수치를 빼면 답이 나오게 된다.

소스

2044 windows

전부 안겹치게 흩어져있는 윈도우 창을 주면
창의 제목을 사전순으로 정렬하여 왼쪽 위부터 차례로 창을 정렬하는 문제이다.

우선 창의 제목을 알아야 하고, 창의 시작좌표와 크기,높이를 알아야 한다.
창이 여러개 존재하므로 위 사항들을 구조체로 저장한다.

그렇게 했으면 모든 창들을 탐색하면서 구조체의 요소들을 채운다.
시작위치 크기 높이는 창 모서리의 '+' 기호를 중심으로 파악이 가능하다.

창을 모두 구했으면 구조체를 창 제목의 사전순으로 정렬해주고
왼쪽 맨 위 부터 시작하여 창을 하나씩 그려준다.

소스

9093 단어 뒤집기

주어지는 문장을 각 단어마다 뒤집어서 출력하는 문제이다.

단어의 시작위치와 끝 위치를 특정지으면 바로 해결이 가능하다.

소스

9020 골드바흐의 추측

2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다고 한다.
이 두 소수를 골드바흐의 숫자라고 하는데 주어진 문제는 짝수를 받아 그 두 소수로 나타내는것이다. 답이 여러개이면 두 수간의 차이가 가장 작은것을 출력해야 한다.

일단 소수라면 우선으로 에라토스테네스의 체를 떠올릴 수 있다.
나는 범위만큼 체를 통해 소수를 걸러내고 입력을 받아 그때그때 처리할 수 있도록 했는데 TLE가 떴다. 그냥 두 수를 고르는것은 쉽지만 두 수의 차이를 알아야 하면 O(n^2)의 시간복잡도가 걸리기 때문이다.

매 번 고를때마다 그렇게하기 때문에 내가 생각한 방법은
처음부터 각 수의 차가 작은 두 소수를 전부 만들어주고 한번에 출력하는 방법이다.
DP와 구조체를 이용해서 동전문제처럼 구현이 가능하다.
그렇게되면 매 입력을 처리하는대에 걸리는 시간은 O(1)이다.

소스

1158 조세퍼스 문제

1~N번 의 사람이 원을 둘러 앉아있고, 순서대로 M번째 사람을 제거한다. 이 때 제거되는 사람을 순서대로 출력하는 문제이다.

매우 빠르게 푸는 방법이 있는거같은데, 생각이 나지 않아서 원형 큐를 구성해서 문제를 풀었다. 원형 큐를 만들고, M번째 사람을 출력한다음 큐에서 제거해주는 작업을 반복한다.

소스

5698 Tautogram

문장의 맨 앞 글자가 모두 같은것을 Tautogram이라고 할 때, 이것을 만족하는지 안하는지 정하는 문제이다.

맨앞글자를 대소문자를 구별하지 않으니 그냥 대문자로 처리해서 저장해두고 각 단어마다 일치하는지를 검사해주면 된다.

다만 개행을 기준으로 문장을 구분해줘야 하고,

띄어쓰기를 기준으로 단어를 구분해줘야 한다.

소스

9213 꽤 좋은 숫자

자기 자신을 제외한 약수의 합이 자기 자신이 되는 자연수를 완전수라고 한다.
이 때, a 이상 b 이하의 자연수중에 자기 자신을 제외한 약수의 합이 완전수와 c이하로 차이나는 수가 몇개인지 찾는 문제이다.

하나하나 약수를 구해서 비교해주면 TLE가 뜬다.
이를 해결하기 위해 에라토스테네스의 체를 응용한다.
우선 주어진 범위만큼 배열을 잡는다. 그 배열의 값은 각 인덱스의 자신을 제외한 약수의 합이다.

값을 정해주기 위한 방법은 i=1부터 범위까지 반복하면서
j= i * 2 부터 범위까지 i만큼 증가하면서 반복하고 j 위치의 배열에 i를 더해준다.

이렇게 하면 자기 자신은 제외하면서 약수들을 전부 더해줄 수 있게 된다.

배열을 다 구성하였으면 조건대로 비교해주면 된다.

소스

3896 소수 사이 수열

정수 n이 주어지면 n을 둘러싸고있는 두 소수 사이의 길이를 구하는 문제이다.

이쯤되면 눈치가 채겠지만 에라토스테네스를 이용하여 소수의 목록을 구하고 n이 어느 소수 사이에 있는가를 찾아내서 계산해주면 된다.

소스

4811 알약

통에 N개의 알약이 들어있다. 여기서 하나의 알약을 꺼내면 반절만먹고 반절은 다시 넣는다. 반절짜리 알약을 꺼내면 다 먹는다. 이 때 하나의 알약을 꺼내는 경우 W, 반절짜리를 꺼내는 경우 H를 출력한다 할 때, 출력되는 문자열의 경우의 수를 구하는 문제이다.

이 문제는 점화식이 매우 간단하다.
F(w,h) = F(w-1,h+1) + F(w,h-1)

여기까진 쉽게 떠올랐고 당연히 DP로 풀면 금방이다.

그러나 본인은 이 점화식을 DP로 생각하지 못하고 노가다에 노가다를 거듭하여 점화식을 풀어냈다.

F(n) = (2n)! / (n! * (n+1)!)

아래 식을 이용하여 답을 구했는데, 이것도 자꾸 오버플로우가 일어나기 때문에 최대공약수를 이용하여 조금씩 값을 증가시켰다.

상당히 서러운 문제였다.

소스

9094 수학적 호기심

0<a<b<n 인 a,b 중에 (a^2 + b^2 + m)/ab 가 정수인 a,b쌍의 개수를 구하는 문제이다.

별다른 공식이 있는 줄 알고 고민하다 안풀려서 반복으로 구해줬는데 다른 사람도 다 이렇게 풀었다.. 딱히 공식이 없는 문제인가 보다.

소스

1526 가장 큰 Shom 수

4와 7로만 이루어진 수 중에 n하고 가장 가까운 수를 구하는 문제이다.

하나씩 비교해주면서 구현하려했는데 너무 복잡해서 그냥 4부터 시작해서 4와 7로만 이루어진 숫자를 차례대로 만들어주면서 비교하였다. 만들때는 문자열을 이용하여 만들고 비교할때는 atoi 함수를 이용하였다.

소스

1547 공

세 컵안에 공을 숨겨두고, 계속 컵의 위치를 바꿔주었을 때, 공의 위치를 출력하는 문제이다.

적혀있는 그대로 스왑해주면 된다.

소스

2729 이진수 덧셈

두 이진수의 덧셈문제이다.

이진수 문제는 보통 길이가 길기 때문에 문자열로 받아와야 한다.
예전에 만들어둔 큰자리 덧셈을 이진수로 변형하여 해결해주었다.

소스

2226 이진수

0 을 10 으로, 1을 01로 치환하면서 N번 반복할 때, 연속인 0의 그룹의 수를 구하는 문제이다.

처음엔 단순히 문자열로 수열을 구현해줬는데 입력이 1000까지여서
2^1000 의 길이가 필요하다는것을 깨달았다. 물론 구현 불가능하다.

규칙을 살펴보니 다음과 같은 점화식이 보엿다.
f(n) = f(n-1) + 2*f(n-2)
그런데 이렇게 구현해주어도 문제가 생겼다. 입력이 1000까지라 값이 long long 형을 넘어버리는 것.

따라서 큰수의 연산을 구현해줄 필요가 있었다.
즉, 위 점화식을 큰수 연산으로 구해주면 된다.

소스

1927 최소 힙

최소 힙을 구현해서 중간 중간에 출력해주는 문제이다.

미리 구현해둔 힙을 가지고 데이터만 문제에 나온대로 넣고 빼면 된다.

소스

Heap

Heap은 우선순위가 높은 데이터를 빠르게 추출하는 자료구조로 일반적으로 최댓값, 최솟값을 찾아낼 때 사용한다. Heap을 응용한 것중에 대표적인것이 우선순위 큐(Priority Queue)이다.

내가 구현한 Heap함수는 int형만 사용할것이 아니라 구조체에도 돌아가게 할 것이므로 비교 함수를 함수포인터로 받아오게끔 하였다.(C 레퍼런스 함수인 qsort와 유사)
그런데 함수포인터를 사용하게 되면 테스트 결과 속도가 약간 느려진다는 단점이 있다.
차츰 최적화가 되게 수정해봐야 겠다.

소스

7662 이중 우선순위 큐

최소, 최대를 둘 다 검사 가능한 이중 우선순위 큐(Priority Queue)를 구현하는 문제이다.

괜한 편법을 부렸다간 가차없이 TLE선고를 맞게 된다.
본인도 무려 41회나 틀림과 TLE를 맞고 42번째에 간신히 정답을 받았다.

이 문제를 풀기 위해선 Max Heap과 Min Heap을 둘다 구해주어야 한다.
그리고 값이 들어갈 때, 두 힙 모두 insert 해 주고, 뺄 때는 동기화를 시켜주어야 하는데,
동기화를 시켜주는 방법은 insert 하는 값에 번호를 매겨서 그 번호를 index로 가지는 check 배열을 선언한다. 이 배열은 index가 빼져서 없다면 0, 있다면 1을 나타낸다.
매 동기화 때마다 각 힙의 루트 부분을 검사하여 check 값이 0 이 나오면 제거해준다.
동기화문제가 해결 되었다면 최대값을 뺄때는 Max Heap 에서, 최소값을 뺄때는 Min Heap에서 제거해주면 된다.

소스

10103 주사위 게임

두 사람이 주사위를 던져서 작은 수가 나오면 상대방의 주사위 수만큼 점수가 깎이는 게임을 할 때 게임이 끝나고 두 사람의 점수를 출력하는 문제이다.

위에 나와있는 대로 구현하면 되는 간단한 문제다.

소스

10101 삼각형 외우기

삼각형의 세 각이 주어지면 그것이 삼각형이 아닌지, 정삼각형인지, 이등변 삼각형인지, 일반삼각형인지를 판별하는 문제다.

세 각의 합이 180도가 아니면 삼각형이 아니고, 모두 60도면 정삼각형이고, 두 각이 같으면 이등변 삼각형이고 모두 아니면 일반 삼각형이다.
위 방식 그대로 구현해주면 된다.

소스

2665 미로만들기

1,1 부터 n,n으로 가는데 사이사이가 끊켜져있어서 갈수가 없다. 이 때 칸을 매꿔서 통로를 만들려고 할 때, 매꿔야하는 칸의 최소값을 구하는 문제이다.

매우 난해한 문제였는데, 여러 수행착오 끝에 정답을 맞은 방법은 다음과 같다.
각 칸에 대응하는 매꿔야 하는 숫자 배열 point[n][n]을 선언하고, 최대값으로 초기화한다. 1,1부터 n,n까지 반복하면서 자신의 위치의 point 값과 자신의 왼쪽, 자신의 위 point 값의 최소값을 고른다. 그 다음 현재 위치가 끊켜져 있다면 1을 더해준다.

그렇게해서 n,n까지 반복했다면 point[n][n]의 값이 정답이 된다.
단, 이 때 point 배열의 초기 설정이 또 필요한데, 이것은 재귀를 이용해서 처음위치부터 밟을수 있는 모든 칸의 point 값을 0으로 주었다. 그런데 이것이 왜 제대로 동작하는지 나도 잘 모른다. 다른사람들에게 질문해봐야 겠다.

현재 이것은 잘못된 풀이로, 나중에 제대로된 정답을 맞으면 수정할 예정이다.

소스

8394 악수

사람들이 일렬로 앉아있을 때, 양 옆사람 끼리 악수를 할 수 있다고 한다. 이 때 가능한 모든 경우의 수를 계산하는 문제이다. 모든 사람이 악수를 안하는것도 계산해야 한다.

패턴을 살펴보면 피보나치 수열이 나오는것을 알 수 있다. 따라서 피보나치 수열을 구현해주면 되는데, 숫자가 매우 커지기 때문에 10 으로 나눈 나머지를 구해야 한다. 피보나치를 구하면서 swap 을 한 후에 10으로 나머지연산을 해주면 된다.

소스

5217 쌍의 합

1~12 숫자가 주어지면, 그 수를 두 수의 합으로 나타낼 수 있을 때 사전순으로 출력하는 문제이다.

문제 자체는 간단하나 출력조건이 조금 까다로운 문제이다. 쉼표를 찍어주냐 안찍어주냐만 신경써주면 금방 해결이 가능하다.

소스

5218 알파벳 거리

주어지는 단어의 각글자의 알파벳 거리를 구하는 문제이다. 첫 알파벳이 두번째 알파벳보다 작으면 두번째에서 첫번째를 빼주고, 크면 두번째에서 26을 더하고 빼준다.

문자열로 받아와서 위 방법대로 처리해주면 바로 해결이 가능하다.

소스

2178 미로 탐색

n * m 크기의 미로가 주어지는데, (1,1) 에서 (n,m)으로 가려고 할 때 이동거리의 최소값을 찾는 문제이다.

처음엔 재귀를 이용해서 무한정 찾으려 했으나 TLE가 나고 말았다.
그래서 BFS를 이용하여 한번 탐색할 때 마다 이동가능한 좌표를 쭉 조사해서  n,m 을 발견하면 종료하도록 작성하였다.
미로 문제는 유명하기 때문에 여러문제들을 풀어보는게 좋을것 같다.

소스

4158 CD

두 사람의 CD 번호가 오름차순으로 들어온다고 할 때, CD번호가 같은것이 몇개 있는지를 구하는 문제이다.

처음엔 오름차순으로 들어오니까 이진탐색으로 풀면 되겠다고 생각했으나, 입력이 너무 많아 TLE가 나고 말았다. 그 다음으로 생각한 것이, 일단 첫 사람의 CD번호만 배열에 저장한 후, 뒷 사람의 CD번호를 하나씩 받아와 검사를 한다.
검사를 할 때 둘 다 오름차순으로 주어진다는 점을 이용하여 검사를 이미 했던 부분은 제외하고, 그 다음부터 비교하여 받아온 숫자가 배열안의 값보다 같거나 작아질 때 까지 검사한다. 만약 그 사이에 없으면 일치하는 번호는 없다고 판단한다.

소스

1145 적어도 대부분의 배수

5개의 자연수중에 3개 이상으로 나누어 떨어지는 수중에 가장 작은 수를 구하는 문제이다.

사실 최대공약수를 이용해 문제를 푸는게 맞지만, 숫자의 범위가 매우 작았기 때문에 그냥 1부터 시작해서 전부 나머지 연산을 해줘서 카운트 해줬다. 시간나면 다시 풀어보는게 좋은 문제.

소스

4948 베르트랑 공준

임의의 n보다 크고 2n보다 작거나 같은 소수가 반드시 하나 이상 존재한다고 한다.
이 때 소수의 개수를 구하는 문제이다.

이 문제 또한 범위만큼 에라토스테네스의 체를 통해 소수들을 구하고 n과 2n사이의 범위로 조사해주면 된다.

소스

4673 셀프 넘버

자신과 자신 + 각 자리의 숫자 를 더해서 수열을 만든다고 할 때, 절대 만들어내지 못하는 수를 셀프넘버라고 한다. 예를들어 1은 위 수열로 만들 수 없기 때문에 셀프넘버다.
1~10000 사이의 셀프넘버를 출력하는 문제이다.

이 문제는  에라토스테네스의체 방식으로 해결할 수 있다. 수열이 계속 증가하는 수열이기 때문에 1부터 시작해서 10000이 될때까지 반복하면서, 각 숫자를 위 수열대로 만들어 주고  숫자를 체크해준다. 1은 1의 수열, 2는 1의 수열에 포함되므로 제외, 3은 3의 수열, 이런식으로 10000 까지 반복해주면 된다.

소스

1343 폴리오미노

.과 X로 이루어진 문자열에 X를 AAAA와 BB로 전부 덮으려고 한다.
사전순으로 가장 앞에 있게 끔 덮을 때의 결과를 출력하는 문제이다. 만약 덮지 못하면 -1을 출력해야 한다.

문자열로 받아와서 처음부터 검사하다가 X를 발견하면, 연속된 X가 몇개있는가를 검사한다.
만약 홀수개가 있다면 덮지못하므로 -1을 출력하고 종료, 4보다 크거나 같다면 4의 배수만큼 AAAA로 덮어주고, 덮고 나서 2칸이 빈다면 BB로 덮어준다. 4보다 작으면 BB만 덮어주면 된다.

소스

8320 직사각형을 만드는 방법

길이가 1인 n개의 정사각형으로 크기가 서로다른 직사각형을 몇개 만들 수 있는가를 묻는 문제이다. 3*2 와 2*3 같은 경우는 같다고 친다.

패턴을 찾아보면, n이 6이라 할 때, 세로나 가로길이가 1인 직사각형 6개,
2인것 2개로 총 8개였다.

이 관계를 생각해보니, 한 길이i를 1부터 n으로 놓고 반복하면서,
j=i 부터 i*j<=n 을 만족할 때 까지, 만들수 있는 직사각형이 하나씩 늘어난다.
위 방법으로 전부 구해서 출력해주면 된다.

소스

3036 링

n개의 링들을 모두 맞물리게 해놓고, 첫번째 링을 한바퀴 돌렸을 때, 다른 링들은 얼마나 도는가를 알아내는 문제이다. n개의 링의 반지름이 주어진다.

링이 실제 움직인 거리에 따라 다른 링들도 돌기 때문에, 결과적으로 링의 반지름에 비례하게 돈다. 따라서 반지름 r이 한바퀴 돌면,
s = r * 1 이고, s = r2 * x  이므로 r/r2 바퀴만큼 돈다.
위 식을 기약분수로 나타내 줘야 하는데, 기약분수는 분자,분모의 최대공약수로 각각을 나눠주면 구할 수 있다.

소스

4706 쌍둥이 역설

상대성이론에 의해 두 쌍둥이가 다른 속도로 달릴 때 한쪽이 더 늙게되는 현상을 쌍둥이 역설이라고 한다. 이 때 두 쌍둥이에게 흐른 시간 ta,tb가 주어지고 ta는 지구에서 흐른 시간, tb는 우주선에서 흐른 시간이라고 할 때, 우주선의 속도를 구하는 문제이다.


$$t_B=\mathrm{\gamma <!--\; \gamma \; -->}{t}_A$$ $$\mathrm{\gamma <!--\; \gamma \; -->}= root(\sqrt{1-<!--\; -\; -->\frac{{\mathrm{v^}}^{\mathrm{2\; /}}}{{\mathrm{c^}}^{\mathrm{2)}}}}$$
속도를 구하기 위한 수식은 위와 같다.
위 식을 속도에 대해 정리해서 나타내면 v = c*root(1-(tb/ta)^2) 가 된다.
속도의 단위가 c라고 주어져 있기 때문에 루트 부분만 구해줘서 출력하면 답이 나온다.

소스

1929 소수 구하기

M이상 N이하의 소수를 구하는 모두 문제이다.

M부터 N까지 하나하나 전부 소수를 구해도 되고,
에라토스테네스의 체를 이용하여 1~N까지의 소수를 구한다음에 M이상인 소수부터 출력해줘도 된다.
후자가 훨씬 빠른 방법이므로 후자를 사용하였다.

소스

5717 상근이의 친구들

남친수와 여친수를 가지고 친구수를 구하는 문제이다.

.. 당연히 두 수를 합치면 답이다. 사실 여친수는 1명으로 취급해야 하지 않을까?

소스

1377 버블 소트

다음 과 같은 소스의 결과를 출력하는 문제이다.
바보같이 저대로 입력해서 제출하면 바로 TLE를 맛보게 된다.
즉, 저 소스의 결과를 유지하면서, 연산은 최소화 해야한다.

어떤 규칙이 있을까? 가장 눈에 보이는것은 1부터 시작해서 n-1까지 계속 스왑을 해주는것이다. 변화가 없을때 까지 반복한다는것은, 가장 변화를 늦추게 하는 숫자를 찾으면 되지않는가! 그리고 그 변화를 늦추는것은 정렬 위치상 앞에 있는 숫자가, 뒤에 있는 경우이다. 그 간격이 가장 큰 것이 변화를 가장 늦추는 숫자이다.

따라서 이 문제를 풀기위해선 같은 값을 저장하는 배열a,b를 저장하고, a는 빠른 정렬함수를 이용해 정렬을 해준다.
그리고 b의 처음 숫자부터 시작해서 a에 같은 숫자가 있는지를 이진탐색을 통해 찾아준다.(반드시 있어야 한다)
찾으면 처음 숫자의 인덱스 - a에서 찾은 숫자의 인덱스 의 최대값을 구하면 된다.
여기서 문제는, 이진탐색으로 찾게 되면 중복된 숫자가 있을 때 값이달라져 버린다. 이 때는 중복된 숫자의 위치상 상한을 찾아서 그것과 비교하도록 처리해주어야 한다. 매번 검색해주면 TLE가 생기니 한번 검색해준것은 저장하여 다음엔 바로 넘어가도록 해주자.

소스

1072 게임

게임을 한 전적 x판 y승이 주어질 때, 앞으로 전부 승리한다고 하면 몇판만에 승률이 바뀌는가를 묻는 문제이다. 여기서 승률은 0~100으로 소숫점은 버림한다고 가정한다.

수학 문제기 때문에 한번에 답을 구할 수 있으나 그 방법을 찾지 못해 이진탐색을 응용하도록 했다. 큰 수를 더해서 승률을 구한다음, 변동이 있으면 더 낮은 수로 비교하고, 변동이 없으면 더 높은 수로 비교하는 방식이다. 만약 처음 정한 큰 값을 넘어가버리면 승률을 구할 수 없는것으로 보고 -1을 출력한다.

승률을 구하는 방법은 y/x를 실수형으로 구하고, 버림해준다음 100을 곱해서 처리한다.

다른사람의 소스를 보니 역시 한번에 구하는 방법이 있었으나 봐도 잘 모르겠다.

소스

1731 추론

n개의 수열을 보고 등차수열인지 등비수열인지를 판별하고, n번째 수열 다음 수열을 출력하는 문제이다.

등차수열인지 등비수열인지를 알아내려면 처음 3 숫자만 알면 되는데,

b-a == c-b 이면 등차, b/a == c/b 이면 등비이다.
이때, b/a와 c/b는 int 형 나눗셈을 하면 결과가 달라질 수 있으니 실수형으로 형변환 해주어야한다.

등차인지 등비인지를 알아냈으면, n번째 수열에 알맞는 숫자를 연산하여 출력해주면 된다.

소스

1816 암호 키

주어지는 숫자가 10만이하의 소인수를 가지면 NO, 아니면 YES를 출력하는 문제이다.

에라토스테네스의 체로 10만까지의 소수를 뽑아내서, 숫자마다 비교해주면 된다.

소스

10102 개표

두 후보의 투표결과를 출력하는 문제이다.

간단하게 문자열로 받아와서 문자 하나하나 마다 비교해 투표해주면 된다.

소스

1753 최단경로

한 정점에서 다른 모든 정점으로의 최단경로를 찾는 문제이다.

이 문제에 대한 해법은 이미 많이 알려져있어서 그 중 하나를 사용하면 되는데,

나는 이중에 다익스트라 알고리즘을 사용하였다.

다익스트라 알고리즘은 힙을 사용하였을 때, O(E*log(V)) 의 시간복잡도를 갖는다.

E는 간선의 개수, V는 정점의 개수다.

사실 알고리즘 자체는 어렵지 않게 만들었지만, 힙을 구현하는대서 많이 애를 먹었다.

역시 C++로 갈아타야 하나싶다.

소스

2824 최대공약수

큰수 A와 B의 약수들을 줬을 때, A와 B의 최대공약수를 구하는 문제이다.

은근 복잡해 보이지만 풀이는 간단하다.
우선 A의 약수들을 다 저장한 후,
B의 약수를 하나씩 받으면서 A의 약수들과 전부 비교를 해 준다.
B의 약수와 A의 약수의 최대공약수를 구해서 한 변수에 곱해주고,
그 약수들 모두 최대공약수로 나눈다.

소스

2998 8진수

2진수를 8진수로 바꾸는 문제이다.
입력이 길기 때문에 문자열로 받아와서
2진수이기 때문에 3글자씩 끊어서 a*4+b*2+c의 식대로 계산해서 출력해주면 된다.
이렇게하면 맨 앞을 몇칸씩 끊을지 정해야 하는데,
3글자씩 끊기 때문에 3으로 나눈 나머지 대로 결정해 주면 된다.

소스

KCPC

대회의 순위를 매기는 문제이다.
점수가 높을수록 순위가 높고, 같은 등수에선 제출 횟수가 낮을수록 순위가 높고, 제출 횟수도 같다면 마지막 제출한 시간이 빠를수록 순위가 높다.
여기서 좀 다른것은, 이미 제출한 문제도 스코어가 높으면 갱신해줘야 한다는 점이다.

일단 제출횟수를 세는 배열, 시간을 체크하는 배열, 점수를 체크하는 배열을 잡아야 한다.
여기서 점수는 총점수를 체크하는 배열과 각 문제별로 받은 점수를 체크하는 배열을 잡는다.
시간은, 한번의 제출을 처리할때 1씩 증가하고, 그때그때 제출한 팀의 시간을 갱신해준다.
제출 횟수는 제출할때마다 1씩 증가시킨다.
점수는, 이미 받은 점수가 있으면 그 점수보다 높을 때 갱신해주고 없으면 그냥 갱신해준다.

총 점수는 받은 모든 점수의 합계로 둔다.

모든 제출을 마쳤으면.  위 조건에 맞게 등수를 매겨 출력해준다.

소스

6064 카잉 달력

60갑자의 확장판이다.
60갑자가 10 * 12로 이루어진 년도라면,
m * n년도에서 x , y 가 주어졌을 때의 년도를 구하는 문제이다.

x,y는 동시에 증가하면서 각각 m,n에서 초기화 되기 때문에 다음과 같이 풀 수 있다.

x,y를 m으로 고정시킨 후, y를 m씩 증가시키면서 n으로 나눈 나머지를 취한다. 년도도 m년씩 증가시킨다. 그렇게 하면서 x,y가 둘다 주어진 값과 같으면 더한 년도를 출력한다.
년도가 구할 수 없다면 -1을 출력해야 하는데, 구할 수 없는지 판별하는 방법은
m n 의 최소공배수를 구한 다음, 더한 년도가 이 수를 넘어가면 -1을 출력하도록 했다.

소스

5480 전함

2차원 좌표평면 안에 전함들이 선분으로 주어질 때, 대포를 수직 수평으로 발사한다고 한다.
대포는 직선에 있는 모든 배를 뚫는다고 할 때, 발포된 대포가 부순 가장 무거운 배를 출력하는 문제이다.

얼핏보면 선분의 기울기를 이용하여 대포에 맞는지 안맞는지를 확인해야 하는 문제로 보인다.
하지만 대포가 수직, 수평으로 발사되기 때문에 단순히 전함의 x좌표 사이에 있는가, y좌표 사이에 있는가만 확인해주면 된다.

우선 전함을 구조체로 잡고, 그 안에 생존여부, 시작x 시작y, 끝x 끝y, 무게를 담았다.
그리고 쏘아진 대포에 대해 전함전체를 검사하면서 생존해 있다면 전함에 닿는지 안닿는지를 판별해서 무게의 최대값을 잡고, 격침시키게끔 했다.

그렇게 했는데 시간제한이 6초나 됬지만 TLE가 나왔다.
아무래도 대포가 격침되어도 전함 전체를 검사하는것에 문제가 있다고 판단하여
연결리스트를 이용해, 격침된 전함은 리스트에서 제외하도록 구현하였더니 ACCEPT를 받았다.

다른 사람들이 푼 것에 비해 상당히 성능이 좋아서 기분이 좋았다.

소스

2765 자전거 속도

바퀴의 지름 (inch), 회전수. 시간(s)이 주어질 때
달린 거리(miles)와 속도(miles/h)를 구하는 문제이다.

거리는 지름 * 파이 * 회전수이고 , inch 를 mile 로 바꿔야 하는데 63360을 나눠주면 된다.
속도는 거리를 시간으로 나눠주면 되는데, hour단위 이므로 3600을 곱해주면 된다.

소스

2512 예산

n개의 예산신청들을 m 원으로 분배한다고 할 때, 다음과 같은 방법으로 분배한다고 한다.

  (1) 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.

  (2) 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

이런 방법으로 분배할 때, 예산신청 이하의 수 중 최대의 상한액을 정하는 문제이다.

나에게 있어 상당히 암을 유발하는 문제였다.
각설하고 문제를 푼 방법은
우선 받아온 예산들을 오름차순으로 정렬 하고, 처음부터 점점 누적해가면서 끊을 곳을 정한다.
그리고  m * 끊은대까지 누적한 수 / 남은예산수 가 정답이 된다.
만약 끊어지지 못하면 가장 큰 예산을 출력하면 된다.

문제는 끊어주는 부분인데, 이는 누적한 수 + 그 바로 다음수 * 남은예산수 > m  를 만족 할 때 끊어주면된다.

소스

10157 자리배정

c*r 크기의 좌석에 자리배정을 달팽이 수열로 할 때, i번째 좌석이 가리키는 x,y좌표를 출력하는 문제이다.

달팽이 수열을 구현하는대엔 여러 방법이 있는듯 하나, 내가 사용한 방법은
x,y마다 방향변수를 잡아주고, 다음번의 턴 포인트를 잡아두고, 방향변수대로 이동한다.
턴 포인트에 도달하면, 방향을 90도 회전시킨 다음에 다음 턴 포인트를 잡는다.
턴 포인트를 잡는 방법은 방향에 따라 현재 번호에 c나 r 만큼 더해 주는데, 턴을 할수록 간격이 점점 좁혀지기 때문에 이를 처리해줘야 한다.
계산한 결과, 3번째 턴마다 부터 간격이 좁혀진다.

소스

10156 과자

K원의 과자를 N개 사는데 M 원이 있다고 할때, 얼마가 필요한지를 구하는 문제이다.

k*n-m 을 출력하되 값이 0보다 작으면 0을 출력해주면 된다.

소스

2018 수들의 합 5

숫자 N을 연속적인 숫자들의 합으로 나타낼 때, 나타날 수 있는 가짓수를 구하는 문제이다.

여러 풀이법이 존재하는데, 내가 푼 방법은
합에 사용되는 길이 i를 1부터 늘려가면서,
 n/i - i 부터 길이 i 만큼의 숫자를 더해서 비교하고,  n/i 까지 그것을 반복한다.
만약 그 사이에 길이가 맞는 숫자가 나오면, 카운트를 증가시켜주고 다음 i로 반복한다.

이 방법은 정답이 뜨지만 효율이 좋지 않다. 다른 빠른 방법들이 있는데
원리가 딱 와닿질 않는다.

소스

4299 AFC 윔블던

문제가 이리저리 길지만 요약하면 다음과 같다.
두 수의 합과 차가 주어졌을 때, 두 수를 큰 순으로 출력한다. 만약 성립하지 않으면 -1을 출력한다.

두 수를 a,b (a>b) 라고 하면,
합과 차는 a+b, a-b가 된다.
따라서 두 수는
a = ((a+b) + (a-b))/2
b = ((a+b) - (a-b))/2
로 구하면 된다.
성립하지 않는 경우는, 합과 차의 합이 홀수이거나, 합이 차보다 작을 때 성립하지 않는다.

소스

1057 토너먼트

N명이서 벌이는 토너먼트의 A,B번 선수가 계속 이겨나간다고 할 때, 몇라운드에서 마주치는지를 출력하는 문제이다.

토너먼트는 매 회마다 2분의1씩 선수가 줄어들기 때문에, A와 B의 번호도 그에 맞춰서 갱신해주면서, A와 B가 같다면 그 라운드에서 마주치는것이다.

소스

1681 줄 세우기

어떤 숫자 L을 사용하지 않는다고 할 때, n번째 나오는 숫자를 출력하는 문제이다.

단순히 모든 숫자에 대해 L이 존재하는가를 판별해서 n번째일 때 출력해줘도 정답이 뜬다.

이렇게 했을때 28ms 가 뜨는데, 다음의 방법으로 좀 더 최적화가 가능하다.

만약 비교하는 숫자의 k자리 숫자에 L이 존재한다면, 숫자를 k만큼 증가시켜 준다.

왜냐하면 k가 10이고 L이 1이면 처음 걸리는 숫자는 10이 될탠데, 10,11,12...19 까지 모두 L이 존재하기 때문에 10만큼 건너띄어주면 된다.

이 방법으로 하게 되면 20ms로 줄어든다.

소스

5893 17배

주어진 이진수를 17배를 해서 이진수로 출력하는 문제이다.

길이가 길기 때문에 숫자가 아닌 문자열로 받아와야 한다.
17배만 하면 되고 굳이 이진수의 곱셈을 구현할 필요는 없기 때문에 다음과같이 하면 된다.

17은 이진법으로 바꾸면 10001(2) 이므로 이진수 * 1 + 이진수 * 10000 을 해주면 된다.

소스

10093 숫자

a와 b사이의 숫자를 구하는 문제이다.
반복문을 이용해 바로바로 출력해주면 된다.

소스

1912 부분합

n개의 정수 수열중, 연속된 숫자의 합이 최대인것을 고르는 문제이다.

숫자를 처음부터 차례대로 더해가면서 최대를 체크하고, 더한 값이 음수인 경우는 0으로 초기화해서 다시 구해주면 된다.

소스

1806 부분합

연속적인 숫자들의 합이 s 이상이면서 가장 짧은 길이인 경우의 길이를 구하는 문제이다.

처음엔 sliding window기법으로 길이를 일정하게 잡고, 이동하면서 최소인 경우를 찾았는데 TLE가 났다.

그래서 숫자들을 따로 저장해서 내림차순으로 정렬하고, 거기서 길이를 늘려가면서 시작 위치를 찾아주었는데, 그렇게 시작위치를 찾아준 결과 accept 를 받았으나 여전히 시간이 좋지 않았다.

지금은 매우 빠른 성능으로 답이 나오는데,
이 방법은 먼저 처음부터 길이를 쭉 늘려가면서 더해준다.
더해주다가 합이 s를 넘어가게 되면 뒤에서부터 길이를 줄여나간다. 이 때 줄이면서 합이 s를 넘게 유지시켜주는것이 중요하다.
위와 같은방법으로 끝까지 이동하면서 가장 짧았던 순간을 비교해주면 된다.

소스

4307 개미

길이 l cm 의 막대에 개미가 올려져있고, 개미는 한방향으로 1cm/s 씩 움직인다. 움직이다 서로 마주치면 개미의 방향은 반대로 바뀐다. 막대의 끝에 다다르면 즉시 떨어지게 된다고 할 때, 모든 개미가 떨어지게 되는 시간중 최소와 최대를 구하는 문제이다.

복잡하게 생각하면 끝이 없지만, 사실 간단한 문제이다.
결론만 말해보자면
최소시간은 한 개미가 가장 짧게 갈 수 있는 거리중 최대값을 구하면 되고,
최대시간은 한 개미가 가장 길게 갈 수 있는 거리중 최대값을 구하면 된다.

소스

4470 줄번호

문자열을 받아와서 앞에 줄번호를 붙이고 출력하는 문제이다.
gets 함수로 받아와서 앞에 줄번호를 붙이고 출력해주면 된다.

소스

4493 가위 바위 보?

둘이서 가위 바위 보를 하여 승이 많은 사람이 이기는 문제이다.
간단하게 둘의 가위바위보 정보를 받아와서 이기는 규칙대로 처리해주면 된다.

소스

8891 점 숫자

위와 같은 방식으로 각 좌표에 숫자가 적혀있다. 두 숫자가 주어지는데, 이 두 숫자가 나타내는 좌표를 밝혀내고, 그 두 좌표를 합쳤을 때의 숫자를 알아내는 문제이다.

이 문제를 풀기 위해선 먼저 숫자를 주면 좌표를 알아내는 함수와, 좌표를 주면 숫자를 알아내는 함수가 필요하다.
규칙을 살펴보면 (x,1) 부분이 1 3 6 10 으로  규칙적으로 증가하는 것을 알 수 있다.
따라서 숫자를 입력하면, 위의 화살표대로 따졌을 때 몇번째 화살표 안의 숫자인지를 밝혀 내고, (x,1) 의 숫자와 주어진 숫자를 비교해서 y를 밝혀낸다.

위와 같은 방법으로 두 숫자의 좌표를 알아냈으면, 그 좌표를 더하고, 다시 숫자로 되돌려야 한다. 되돌릴 때는 x + y - 1 이 화살표 번호를 나타내고, 그걸 이용해 그 화살표의 (x,1) 숫자를 밝혀 내면, 1 + 숫자 - y 가 원하는 답이 된다.

소스

2774 아름다운 수

주어진 숫자의 각 자리의 숫자중, 서로 다른 숫자가 몇개인지를 구하는 문제이다.

단순히 받아와서 한숫자씩 비교하면서 0~9를 check 하는 배열에 표시를 해준다.

그리고 체크된 숫자를 계산하면 답이 나온다.

소스

2667 단지번호붙이기

맵에 각 집들이 서로 붙어있으면 같은 단지로 취급한다. 그렇다고 할 때, 단지의 갯수와, 단지마다 몇개의 집이 있는지를 오름차순으로 출력해주는 문제이다.

우선 각 집들이 붙어있는지의 여부는 dfs로 재귀하면서 확인 가능하다. 맵의 처음부터 끝까지 돌면서 해당 맵에 집이 있으면, 그 집을 중심으로 동서남북으로 재귀한다. 집이 없으면 리턴, 있으면 카운트를 증가시키면서 집을 없다고 표시해준다. 값을 오름차순으로 정렬해야 하므로, 각 좌표의 재귀가 모두 끝나면 결과값을 배열에 따로 저장해둔다.

모든 반복이 끝났다면, 결과를 오름차순으로 정렬해서 뿌려주면 된다.

소스

1395 스위치

s번부터 t 번까지의 스위치를 반전시키는 명령을 반복해주면서 중간중간에 결과를 출력하는 문제이다.

문제대로 구현해줘도 Accept가 뜬다. 내 경우 720ms가 뜨는데, 가장 빠른 사람은 96ms가 뜬다. 소스를 보니 트리구조를 이용하는것 같은데 아직 잘 모르겠다.

소스

4806 줄 세기

입력된 줄 수를 세는 문제이다.
gets 함수를 이용하면 매우 간단하게 문제해결이 가능하다.

소스

6322 직각 삼각형의 두 변

직각 삼각형의 세 변중 두 변의 길이를 알려주면 나머지 한 변의 길이를 알아내는 문제이다.

직각 삼각형은 a*a+b*b=c*c 를 만족하기 때문에, 저 식을 변형하고 sqrt를 사용하면 나머지 한 변의 길이를 알아낼 수 있다.
문제에는 불가능한 경우도 알아내야 하는데, 불가능한 경우란 두 제곱수의 차가 음수일 경우가 된다.

소스

9095 1, 2, 3 더하기

각 수를 1,2,3의 덧셈만 이용해서 만든다고 할 때, 나올 수 있는 경우의 수를 구하는 문제이다.

dp방법으로 계산하면 될거같긴한데, 테스트범위가 1~11밖에 안되서 간단하게 재귀로 구현해줬다. n으로 시작해서 1,2,3 씩 뺐을 때, 0이 되는 경우의 카운트를 새면 답이 나온다.

소스

1564 팩토리얼5

n!의 0이아닌 5자리수를 구하는 문제이다.

바로 아래 마지막 팩토리얼과 푸는 방법이 동일하다.
다만, 5자리를 출력해야 하므로 나머지를 구하는 수도 그만큼 커져야 하는데,
여기선 10^7 로 잡아주고 5자리만 출력되게 하니 정답이 나왔다.

소스

2553 마지막 팩토리얼 수

n! 의 0이아닌 마지막 자리수를 구하는 문제이다.

1부터 n까지 차례로 곱해가면서, 0인 부분을 때어내고 마지막 자리만 저장하면 되는것 같았으나, 15부터 값이 달라졌다. 이것은 n의 자리수가 변하면서 결과에 영향을 주는것인데,
따라서 저장해주는 자리수도 똑같이 늘려주면 된다. 즉, 1~10까진 10으로 나눈 나머지 값을 취해주고, 11~100 까진 100으로 나눈 나머지 값을 취해주고 하는식으로 하면 된다.

마지막에는 그 취한 값을 10으로 나눈 나머지를 출력해주면 답이 나온다.

소스

1660 캡틴 이다솜

크기가 1인 구슬로 길이가 N인 정삼각형을 만들고, 위에 N-1, N-2... 1 의 정삼각형을 계속 쌓아서 사면체를 만드려고 한다. 구슬의 갯수를 주어주면 최소 몇개의 사면체를 만들 수 있는가를 출력하는 문제이다.

우선 사면체에 필요한 구슬의 갯수를 구해야 한다.
길이가 1씩 길어지면서 계속 쌓아야 하니, N은 1부터 시작해서 점차 증가하고 1~N의 합의 합을 구해야 한다. 그렇게 구한 각 사면체에 필요한 구슬 갯수들을 따로 배열로 저장해놓는다.

이제 만들수 있는 사면체 수의 최솟값을 구해야 하는데, 이것은 DP를 이용해야 한다.
해당 구슬의 갯수로 만들 수 있는 사면체 수를 비교하면서 작은 값으로 갱신해주면 된다.

소스

7579 앱

n 개의 메모리-코스트 의 묶음에서 하나씩 골라 , M메모리 이상을 만들려고 할 때,
코스트의 합이 가장 작은 경우를 고르는 문제이다.

DP로 푸는 문제인데, DP로 삼는 방법은 코스트의 index 배열을 선언하고
해당 코스트에 적재 가능한 최대한의 메모리를 넣으면 된다.

비교 할때는, 현재 코스트에 지정된 메모리보다 현재 코스트 - 해당 코스트 의 메모리 + 해당 메모리가 더 큰 경우로 하면 된다.

소스

5426 비밀 편지

n*n의 정사각형에 암호화된 편지가 있다. 이를 왼쪽으로 90도 회전하여 읽으면 원문일 때, 원문을 출력하는 문제이다.

회전은 행렬의 회전변환 공식을 이용하여 주면 된다.
이 경우엔 y -> n-x , x -> y 가 된다.
n도 처음부터 주어지는것이 아니라 판별을 해야 하는것인데,
n은 strlen 과 sqrt 함수를 통해 판별 가능하다.

소스

7523 Gauß

정수 n에서 m까지의 합을 구하는 문제이다.
이 문제는 실제로 반복하면서 더하면 TLE가 발생하게 된다.
따라서 1~n까지 더했을 때의 공식인 n*(n+1)/2 를 이용해주면 된다.

고려해야할 사항은 n,m의 부호가 같을 때와 다를 때이다.
부호가 같으면 둘 중 큰수의 합에서 작은수의 합을 빼주면된다.
부호가 다르면 음수인 쪽의 합에 -를 붙여준다. 이유는 위 공식을 사용하면 무조건 양수가 되기 때문이다.

소스

9243 파일 완전 삭제

주어진 수가 짝수면 주어진 두 비트열이 서로 같아야 하고, 홀수면 서로 완전 반대여야 한다.

문자열로 받아와서 짝수일때와 홀수일때의 처리를 반복문을 사용하여 해주면 된다.

소스

5800 성적 통계

각 학생의 성적을 내림차순으로 정렬하고, 가장 높은 성적, 가장 낮은 성적, 인접한 두 성적의 격차가 가장 큰 수를 출력하는 문제이다.

입력을 받아오고, 내림차순으로 정렬하여 가장 첫번째것이 높은성적, 마지막것이 낮은 성적이다. 인접한 두 성적은 처음부터 반복하여 찾아주면 된다.

소스

5789 한다 안한다

문자열의 양 끝을 시작으로 각 문자가 같으면 한다, 다르면 안한다일 때, 맨 마지막 결과를 출력하는 문제이다.

모두 비교할 필요 없이, 가운대에 있는 문자만 비교해주면 된다. strlen함수를 이용해서 길이를 반으로 나누고 검사를 하면 된다.

소스

1225 이상한 곱셈

두 숫자에서 각 자리의 숫자를 하나씩 뽑아서 둘을 곱한다. 이것을 모든 자리에 대해 수행하고 그 값들을 더할 때의 값을 구하는 문제이다.

길이가 10000 까지기 때문에 문자열로 받아와야 한다. 두 숫자 A,B에 대해 문자열을 받아오고, A의 각 자리 숫자에 대해 B의 각 자리 숫자를 각각 곱하고 더해주면 된다.
위 방법대로 풀면 O(len(A)*len(B)) 의 시간복잡도가 나오는데, 곱셈의 성질을 이용하여
두 숫자의 각 자리수를 더한 다음, 더한 두 수를 곱해도 같은 답이 나온다.
이때의 시간 복잡도는 O(len(A)+len(B))가 된다.

소스

5026 박사 과정

문자열을 입력받아 덧셈식이면 덧셈을 수행하고, P=NP이면 skipped 를 출력하는 문제이다.

문자열로 받아와서 첫글자가 P 이면 P=NP이고 그렇지않으면 덧셈인데,
덧셈의 두 수를 구하는 방법은 '+' 가 나타나는 배열의 위치를 골라서
atoi함수로 첫번째 위치, '+'가 나온 위치의 다음 위치 로 각각 구해주면 답이 나온다.

소스

9086 문자열

문자열의 가장 첫번째 글자와 마지막 글자를 출력하는 문제이다.
매우 간단하게 배열로 받아와서 strlen함수를 이용해 풀어주면 된다.

소스

9237 이장님 초대

나무가 다 자라는데 각각 t(i) 시간이 걸린다고 한다. 하루에 하나씩 심을 때, 나무를 심는 순서를 조절하여 가장 짧은 시간에 모두 다 자라도록 할 때, 몇일이 걸리는가를 알아내는 문제이다.

간단하게 나무가 자라는 시간을 내림차순으로 정렬해서 t(i) + i 시간이 가장 큰것이 다 자라는데 걸리는 최소시간이다.

소스

2249 동전 2

n개의 가치가 다른 동전을 적절히 사용해서 k 가 되게 하려고 한다. 동전의 수가 무한할 때, 동전의 갯수를 최소로 사용하는 경우의 갯수를 구하는 문제이다.

전형적인 DP 문제이다. 그러나 내 입장에서 DP는 어떤것도 어렵게 느껴진다.

이 문제를 푸는 방법은,
우선 1~k 까지, 각 숫자에 몇개의 동전 갯수가 사용 됬는지를 저장할 배열을 만든다.
그리고 그 배열을 최대값으로 초기화 한다.

또, n개의 동전의 값어치에 해당하는 배열의 위치를 1로 초기화 한다.
동전의 값어치에 해당하는 위치는 동전 1개만 사용하면 만들 수 있기 때문이다.

그다음 한 동전씩 골라서 매번 1~k까지 비교를 한다.
비교 방법은, 현재 숫자에 현재 동전의 값어치 만큼을 더한 숫자의 갯수가, 현재 숫자의 갯수 + 1 보다 크면, 새로운 최소값이 생긴것이기 때문에 값을 갱신한다.
이 때, 오버 플로우 문제가 생기지 않도록 해준다.

반복이 끝난 후, k에 해당하는 배열의 숫자를 출력해주면 된다.

소스

1407 2로 몇 번 나누어질까

A 이상 B 이하의 자연수에 대해서, 각 수와 2의 거듭제곱 과의 공약수 중에 가장 큰 공약수를 골라서 그 수들을 합쳤을때의 결과를 묻는 문제이다.
문제에 주어진대로 풀면 범위가 매우 커서 TLE가 발생한다.
이 문제는 범위로 생각하는게 좋다.
a~b 범위중에 2의 배수의 갯수, 4의 배수의 갯수, ... 2^n(<=b)의 배수의 갯수를 구해서 합쳐줘야한다.
단, 갯수를 구하는 문제가 아니라 실제 수들을 합쳤을때의 결과를 묻기 때문에, 주의해야 한다.
예를들면 4는 2의 배수에도 속하고 4의배수에도 속하기 때문에 2의 배수였을때의 경우를 빼주고 4의배수로 갱신해야 한다.

또 하나 신경써줘야 할것은 A가 2^n의 배수가 아닐경우, A에서 가장 가까운 수부터 그 숫자를 정해야 할탠데, 그 방법은
a를 2^n 으로 나누고, 그 값을 올림 해준다음 2^n으로 곱하면 된다.

소스

2630 색종이 자르기

N*N 크기의 정사각형에 파란색과 하얀색의 두 색이 칠해져 있다.
이를 한 색깔로만 채워지도록 계속 4등분 하여, 파란색과 하얀색 각각의 색종이가 몇개 존재하는가를 구하는 문제이다.

딱봐도 4등분하는 재귀 문제로 보인다.
풀이 방법은 아래와 같다.

white = 0;
blue = 0;
split(p,q,size)
{
  // p,q 점을 시작으로 size크기의 정사각형이
  // 하얀색이나 파란색으로 가득 찼는지 검사.
  if(isWhite(p,q,size) == true) { white++; return; }
  if(isBlue(p,q,size) == true) { blue++; return; }

  // 각 사분면으로 재귀
  size /= 2;
  split(p,q,size);
  split(p+size,q,size);
  split(p,q+size,size);
  split(p+size,q+size,size);
}

소스

7806 GCD!

n! 과 k 의 최대공약수를 구하는 문제이다.

n!은 매우 큰 숫자기 때문에 long long 형의 범위도 가볍게 넘어버린다.
그러나 k가 int 형 범위이기 때문에 결과는 최대 공약수가 나와서 big integer를 구현할 필요는 없다.

이 문제를 풀기 위해선 k를 소인수 분해할 필요가 있다.
k를 소인수 분해 하는것은 소수판별 할 때 처럼, 2부터 root(k)까지만 검사하면 된다.
푸는 방법을 의사 코드로 나타내 보았다.

s = 1;
for(i = 1; i <= sqrt(k); i++)
{
  p = 0;
  while(k % i == 0)
  {
    b /= i;
    p++;
  }
  if (p)
  {  
    // n!에서 인수 i가 몇개 존재하는가
    k = primeFactorCountOfFactotial(n,i); 
    s *= pow(i,k);
  }
}
print s;

primeFactorCountOfFactorial(n,i)
{
  result = 0;
  for(j = i; j <= n; j *= i)
  {
    result += (int)(n / j);
  }
  return result;
}

소스

1946 신입 사원

n명의 사람의 a,b의 순위가 주어질 때, 어떤 사람에게도 a,b 모든 순위에서 지면 제외시킨다고 할 때, 살아남는 사람의 숫자를 구하는 문제이다.

생각보다 고민한 문제인데,  내가 푼 방법은 우선 a순위를 정렬하는것이다.
한 순위를 정렬하게 되면(순위가 높은 순으로), 다음 과 같이 구분한다.

1. 1순위는 무조건 추가한다. 1순위는 무조건 살아남기 때문이다.
2. 그 다음 2순위부터 차례대로, 이미 추가된 사람들의 b순위와 비교한다.
2순위는 1순위보다 무조건 a에서 지지만, b에서 이기면 살아남는다.
따라서 이미 추가된 사람들의 b순위보다 순위상 위라면 추가해준다.

위와 같은 방법으로 문제 해결이 가능하지만, 사실 그대로 구현하면 TLE가 나오게 된다.
시간복잡도가 정렬하는대서 O(nlog(n)), 아래 비교하는대서 O(n^2)이 뜨기 때문이다.

TLE를 해결하려면 2번을 고쳐줄 필요가 있다.
2번에 이미 추가된 사람들의 b순위를 하나하나 비교하지 말고, 추가된 사람 중에서 가장 높은 b순위를 max로 저장하고 이것하고만 비교해주면서 갱신하면 된다.
여기서 max만 갱신해주면 딱히 추가할 필요도 없어져서 메모리 절약도 가능하다.
이 때의 시간복잡도는 O(n)이 된다.

소스

1793 타일링

2*n의 타일을 2*1,1*2,2*2 타일을 붙여서 만드는데 나올수 있는 경우의 수를 구하는 문제이다.

이런 문제는 점화식이 중요하다. 여기서 사용된 점화식은
f(0) = 1
f(1) = 1
f(n) = f(n-1) + 2*f(n-2)
이다.
이것에 맞춰서 구하면 되는데, 숫자의 길이가 기하급수적으로 증가해서 long long 형을 넘는다. 따라서 big integer의 덧셈을 구현해주어야 한다. 사실 곱셈도 구해야하지만, 덧셈을 두번해주면 되니깐.

언젠가 big integer 알고리즘을 미리 구현해둘 필요가 있다.

소스

9372 상근이의 여행

연결 그래프에서 가장 적은 "종류"의 간선을 타고 모든 정점을 돌때의 종류의 수를 구하는 문제이다. 이 때 한번 간 장소도 다시 갈 수 있다.

뭔가 복잡해보이지만 사실 조금만 생각해보면 모든 정점을 돌기 위해선 최소로 정점-1개의 간선을 돌아야 한다. 즉, 간선이 연결그래프를 이룬다고 했으니 간선이 어떻게 되어있던 간에 정점-1을 출력해주면 된다. 간선을 이동한 횟수가 아니라 종류라서 그렇게 된다.

소스

1872 로마숫자

주어진 문장에서 한 문자씩 따와 가장 큰 로마숫자를 만드는 문제이다.
처음에 도전했다가 포기하고 다른분(pichulia)의 도움을 받아 다시 도전하여 풀게 되었다.

이 문제는 로마숫자의 규칙을 잘 이해해야 풀 수 있다.

처음엔 X문자는 최대 3번밖에 못쓰는 줄 알고 있었으나,
XXXIX 같은 경우가 존재했다. (다른분의 도움으로 반례를 찾음)

이 문제를 푸는 방법은 우선,
로마숫자의 가장 큰 수 M부터 가장 작은 수 I 까지 반복하면서 문자열을 살펴본다.
M을 제외한 모든 로마 숫자에는 사용될 수 있는 갯수가 제한되어있다. 따라서 제한된 숫자를 기록하는 배열을 하나 잡는다.
각 로마숫자에 맞는 문자가 나타나고, 횟수가 남아있으면, 그 문자를 고른다.
그리고 다음 반복은 그 문자의 위치부터 시작하기위해 변수(m)를 하나 둔다.

그렇게 돌다가 횟수가 0인데 다시 문자가 나타나는 경우, 그리고 그 문자가 X와 C일때
그 위치부터 m까지 되돌아가면서 IX 나 XC를 만들 수 있는지 살펴본다.
만약 가능하면 그 문자를 추가 한 후, m값을 다시 조정하고
그 문자의 횟수는 -1로 바꾼다.(IX는 한번만 나와야 하므로)
그 문자의 다음 문자와 그 다음 문자의 횟수를 0으로 만든다.
예를들어 XC를 만들었으면, L과 X의 횟수를 0으로 만드는 것이다.
여기서 X의 횟수가 0이 됬지만 IX는 만들 수 있다는것에 주목하자.

이것은 로마숫자의 규칙에 의한것이며, X와 C일때만 이렇게 해주는 것은,
이 경우를 제외한 경우에서 규칙에 맞는 최대값이 존재하지 않기 때문이다.

위와 같은 방법으로 반복을 마쳤다면, 고른 문자들을 10진법으로 바꿔주고 출력해주면 된다.

소스

2075 N번째 큰 수

주어지는 N*N개의 숫자중에 N번째 큰 수를 구하는 문제이다.
원래같으면 모두 받아와서 정렬해주면 그만이지만, 여기선 메모리가 적게 주어지기 때문에
그 방법은 사용할 수 없다. 사실 있긴한데, 정렬방법에 메모리(스택이라던지)가 조금이라도 필요해지면 메모리초과가 발생하게 된다.

내가 사용한 방법은 n개만큼의 배열만 생성하여 그 안의 숫자를 정렬해주는 것이다.
물론 매번 전부 정렬하는것이 아닌, 배열이 꽉찼을때 처음만 정렬해주고, 그 뒤엔 추가할때 한칸씩 당기는식으로 처리해줬다. 다른사람의 소스를 보니 여러가지 방법이 있었는데,
모두 받아와서 메모리가 적게 쓰이는 정렬을 해주거나 독특한 방법으로 수행시간을 줄인 경우도 있었다.

소스

몇몇 수학 알고리즘

그다지 복잡하진 않지만 자주 쓰이는 수학 알고리즘들은 한곳에 모아두려고 한다.

소스에 수록되있는 알고리즘은 다음과 같다.

1. 소수판별
2. GCD
3. 에라토스테네스의 체
4. n!의 소인수 i의 갯수
5. 큰 수 덧셈

소스

앞으로도 계속 추가할 예정이다.

2578 빙고

빙고게임이 언제 끝나는지를 판별하는 문제이다.
여기서 빙고게임은 가로,세로,대각선의 각 줄이 x로 채워져 있으면 +1로 취급하여 +3이 되면 승리한다.

데이터를 받아올 때 마다 빙고를 검사해서 3줄이상이 채워지면 승리하도록 하면 된다.

소스

1347 미로 만들기

오른쪽,왼쪽 90도 회전과 전진 만을 수행 가능 할 때, 진행한 경로로
미로를 만드는 문제이다.

우선 맵을 충분한 크기로 잡고, 맵 중앙에 놓은 다음, 명령대로 수행하면 된다.
회전은 행렬의 회전변환을 이용하여 주면 된다.
다만 출력할때, 맵을 잘라야 하는데,
가로,세로를 줄단위로 검사해서 밟힌 적이 없으면 잘라주면 된다.

소스

2712 미국 스타일

kg은 lb로 lb는 kg로, l은 g로 g는 l로 변환하는 문제이다.

숫자와 문자열을 받고, 문자열로 단위를 파악해서 표를 통해 구해주면 된다.

소스

6500 랜덤 숫자 만들기

다음 과 같은 방법으로 랜덤숫자를 만들었을 때, 최대 몇개의 랜덤숫자를 구할 수 있는지를 구하는 문제이다.

길이가 n인 초기숫자를 고르고, 그것을 제곱한 후, 길이가 2n이 되도록 앞에 0을 붙인다. 그리고 중앙에서 길이 n만큼 숫자를 때어낸다.

위의 과정을 사이클이 생기기 전까지 반복해주면 된다.

소스

5883 아이폰 9S

주어진 숫자들 중에 한 숫자를 뺐을때, 다른 연속된 숫자의 길이가 가장 긴 경우를 구하는 문제이다.

별다른 알고리즘 필요없이, 처음부터 끝까지 중에 한 숫자를 빼서, 가장 연속된 숫자의 길이를 구하면 된다.
단, 똑같은 숫자를 또 뺄수 있기 때문에, 배열로 체크를 한다던가 하는 방법으로 막아주면 된다.

소스

3028 창영마을

공의 위치를 세곳으로 나눠서 다음과 같은 A,B,C로만 위치를 바꾸는 문제이다.

공의 위치를 1 2 3 이라고 하고 주어진 규칙에 맞에 위치를 바꿔주면 된다.

소스

5724 파인만

N*N의 정사각형안에 크기가 서로 다른 정사각형이 모두  몇개 들어있는가를 알아내는 문제이다.

이 문제는 규칙을 잘 생각해보면 점화식이 다음와 같이 나타나게 된다.

f(1) = 1
f(n) = n*n + f(n-1)

이 점화식에 맞춰서 구해주면 된다.

소스

9421 소수 상근수

각 자리의 숫자를 제곱해서 더한 후, 그 값이 1이 될 때 까지 반복해서
1이 되면 상근수, 그렇지못하고 무한루프를 돌게되면 상근수가 아니라고 할 때,
n 이하의 소수인 상근수를 모두 출력하는 문제이다.

이 문제를 풀기위해선 일단 소수를 걸러내야 한다.
일반적인 소수판별 알고리즘을 사용하면 O(n*root(n))의 시간으로 소수를 판별 가능하다.
이렇게 하면 풀리긴하지만 TLE인 1초에 매우 근접하게 된다.
여기선 에라토스테네스의 체를 통해 1부터 n까지의 소수를 미리 걸러내 주면
O(nlog(n)) 의 시간복잡도로 소수를 밝혀낼 수 있다.
둘다 별로 차이가 없어보일지 모르지만 이 문제에선 15배 더 빠른 결과를 보인다.

소수를 판별했으면, 상근수를 구해야 하는데, 이것도 모든 수를 일일히 구해볼 수는 없으므로
DP를 이용한다. 즉, 제곱해서 더한 수들이 이미 있으면 그 결과를 출력하고, 없으면 구해서 채워넣는 방식이다. 각 자리의 숫자를 구하는것을 반복하는것은 재귀를 이용했다.

소스

1964 오각형, 오각형, 오각형...

오각형의 크기를 점점 키웠을 때 찍게되는 점의 수를 구하는 문제이다.
몇가지 케이스를 가지고 공식을 새워주면 된다.
이 경우에는, 1+sigma(i=1 to n){3*i + 1} 이 공식이 된다.
2차 방정식으로 나타내보면

f(n)=1.5*n^2 + 2.5*n + 1

이 된다.

소스

3040 백설 공주와 일곱 난쟁이

9명의 난쟁이중에서 합이 100인 7명의 난쟁이를 골라내는 문제이다.
단순히 재귀를 이용해서 전부 검사하면서 7명일때 합이 100인 경우 를 가려내면 된다.
하지만 이것은 매우 효율이 안좋은 방법이다.
최악인 경우 9! 만큼 재귀하기 때문이다.

다른사람의 소스를 확인해보니 9*8 만큼의 반복으로 문제를 해결하였는데,
방법은 9명 전원의 숫자를 합쳐서 2명을 제외 했을때 합이 100인 경우를
판별하면 된다.

역시 생각하기에 따라서 효율이 천차만별로 달라지게 된다.

소스