C String Refference 함수

1. void*memchr(const void * str, int c, size_t n)
    -첫번째로 나타나는 문자를 찾아줍니다.
2. int memcmp(const void *str1, comst coid *str2, size_t n)
    -n바이트까지 str1과str2의 문자가 같은지 검사합니다.
3. void *memcpy(void *dest, const void *src, size_t n)
    -src에서 n바이트만큼을 dest에 복사합니다.
4. void *memove(void *dest, const void *src, size_t n)
    -src에서 n바이크 만큼을 dest에 복사하는 또하나의 함수입니다.
5. void *memset(void *str, int c, size_t n)
    -str의 n번째 글자를 c로 대체합니다.
6. char *strcat(char dest, const char *src)
    - dest의 뒤에 scr을 붙입니다.
7. char* strncat(char *dest, const char *src, size_t n)
    - dest의 뒤에 src의 n번째 문자까지 붙입니다.
8. char *strchr(const char *str, int c)
    - c가 첫번쨰로 나오는곳을 찾습니다.
9. int srtcmp(const char *str1, const char *str2)
    - str1과 str2가 같은지 비교합니다.
10. int strncmp(const char *str1, const char *str2, size_t n)
    - str1과 str2가 n번째 까지 같은지 확인 합니다.
11. int strcoll(const char *str1, const char *str2)
    - str1과 str2가 같은지 비교합니다. 비교 결과는 LC_COLLATE 세팅에 따라 달라집니다.
12. char *strcpy(char * dest, const char *src)
    - src를 dest에 복사합니다.
13. char *strncpy(char *dest, const char * src, size_t m)
    -src의 n번째 문짜까지를 dest에 복사합니다.
14. stze_t strcspn(const char *str1, const char *str2)
    -  str2에는 포함되지 않은 str1에 포함된 문자의 숫자를 알려줍니다.
15. char *strerror(int errnum)
    - 배열 내부의 에러 'errnum'을 검색고 에러 메시지를 리턴해 줍니다.
16. size_t strlen(const char *str)
    -str의 길이를 계산합니다. ('널문자는 포함하지 않은길이를 린턴 합니다.)
17. char *strpbrk(const char *str1, const char *str2)
    - str1에서 str2에 있는 문자와 같은 천번째 문자를 리턴해줍니다.
18. char *strrchr(const char *str, int c)
    - str의 마지막에 있는 문자 c와 같은 문자를 알려줍니다.
19. size_t strspn(const char *str1, const char *stre)
    - str2에 완전하게 포함되어있는 str1의 크기를 계산해준다.
20. char *strstr(const char *haystack, const char *needle)
    - 문자열에서 임의의 문자열이 시작하는 위치를 구합니다
21. char *strtok(char *str, const char *delim)
    - strㅇㄹ delim을 기준으로 자릅니다. 잘라낸 문자열의 천번재 포인터를 반환하며, 문자열이 없다면 NULL을 반환합니다.
22. size_t strxfrm(char *dest, const char *src, size_t n)
    - src의 앞에서부터 n번째 까지의 문자들을 수집하여 dest에 위치시킵니다.

4435 중간계 전쟁

간달프와 사우론이 싸우는데 병사의 종류와 가중치가 주어지고, 각 진영의 종류마다 병사의 수가 주어지면 가중치의 합이 큰쪽이 승리한다고 한다. 이 때 각케이스마다 어느진형이 승리하는지를 구하는 문제이다.

간단하게 가중치를 배열에 담아놓고 병사의 종류에 해당하는 가중치 * 병사의 수를 더한다음 비교하면 된다.

소스

9229 Word Ladder

주어진 단어를 한글자씩만 바꾸면 다음 단어를 만들 수 있는지 검사하는 문제이다.

단순하게 단어를 하나씩 받아오면서 한글자만 바꼈는지를 검사해주면 된다.

소스

1855 암호

평문을 종이에 가로 n칸으로 나눠서 왼쪽부터 세로로 작성한 다음, 가로로 한줄씩 읽어서 이어붙여서 암호를 작성하였다. 암호문이 주어지면 다시 평문으로 복구하는 문제이다.

복호화를 위해서는 암호문을 만든 종이를 그대로 만들어내고, 그것을 이번엔 가로로 한줄씩 읽어서 이어붙이면 된다.

소스

9996 한국이 그리울 땐 서버에 접속하지

와일드 카드의 *를 구현하고, 패턴이 주어지면 나머지 문자열이 패턴에 해당하는가 아닌가를 구분하는 문제이다.

*은 문자열의 중간에만 나온다고 하였으므로, *을 기준으로 앞 뒤로 나눠서 주어진 문자열의 앞 뒤와 맞는가 검사해주면 된다.

예를들면
abc*bcd 라는 패턴이 주어지면,
어떤 문자열은 반드시 앞에 abc 가 있어야하고 뒤에는 bcd가 있어야 한다.
단, abcd 처럼 앞 뒤가 섞여있으면 안된다.

소스

1516 게임 개발

건물을 짓는 시간과, 그 건물을 짓기위해 필요한 다른 건물의 번호가 주어질 때, 각 건물마다 짓는데 걸리는 최소시간을 구하는 문제이다.

전형적인 백트래킹 문제로 재귀와 DP를 통해 해결할 수 있다. 각 건물을 짓는데 필요한 건물에 대해 재귀를 하면서, 그 값중에 최대를 찾으면 그것이 최소시간이 된다. 그 값을 따로 저장해주면 DP가 가능해진다.

소스

1063 킹

체스판 위에 킹과 돌맹이가 있고, 킹이 움직일 때 돌맹이에 닿으면 킹이 움직이는 방향으로 돌도 한칸씩 움직인다고 한다. 이 때 킹이 움직이는 방향이 주어지면 킹과 돌맹이의 마지막 위치를 출력하는 문제이다. 단, 킹이나 돌이 판 밖을 넘어가야 하는 입력은 무시한다.

단순한 구현문제로 명령에 따라 움직여야하고, 킹이나 돌이 넘어가는것을 체크하는것이 중요하다.

소스

6600 원의 둘레

세 점의 좌표가 주어지면 그 점을 포함하는 원의 둘레의 길이를 구하는 문제이다.

세 점으로 삼각형을 만들 수 있고, 삼각형의 세 꼭지점으로 만드는 원을 외접원이라고 한다.

이 외접원의 반지름을 구하는 공식은, 삼각형의 세 선분을 a,b,c 넓이를 s라고 할 때,

r = (a*b*c) / (4*s)

이 된다.

원주 l 은 l = r * 2 * pi 로 구할 수 있다.

소스

6131 완전 제곱수

1 <= b <= a <= 500 의 범위의 a,b 중에 a^2 = b^2 + N 인 a,b쌍의 개수를 구하는 문제이다.

범위가 작기때문에 그냥 2중 반복을 통해 위 조건을 만족해주는 쌍을 찾아주면 된다.

소스

1168 조세퍼스 문제 2

1158 조세퍼스 문제 랑 같은 문제인데 범위가 5,000에서 100,000으로 늘었다.

예전에 풀은 소스로 제출하면 시간초과가 났는데, 이번엔 가장 간단한 방법인 배열에 놓고 제거한다음 다시 당겨주는 작업으로 고쳤더니 Accept을 받았다. 하지만 역시 느린것은 마찬가지이다. 빠른 소스를 보니 트리구조로 해결한것 같은데 아직 잘 모르겠다.

소스

1966 프린터 큐

큐에 가중치들이 들어있고, 맨 앞의 값보다 큰 값이 뒤에 존재하면 그 값을 큐의 맨 뒤로 보내고 존재하지않으면 출력할 때, N번째 큐는 언제 출력되는지를 구하는 문제이다.

큐마다 번호를 지정해주고 위 조건에 맞춰서 N번째 큐가 출력될때 까지 출력과 뒤로보내기를 반복해주면 된다.

소스

1456 거의 소수

어떤 자연수가 소수의 N제곱 꼴일 때 거의 소수라고 한다. 이 떄 a부터 b까지 거의 소수의 개수를 구하는 문제이다.

범위가 10^14 까지 되지만, N제곱(N>1)이기 때문에 10^7까지의 소수만 나타나게 된다. 따라서 에라토스테네스의 체로 10^7까지 소수를 걸러주고, 그 소수들에 대해 계속 거듭제곱을 하면서 a와 b사이에 들어있는지 판별하면 된다.

p.s. long long 형으로 구현을 해주니 overflow 문제가 발생했다. 이것저것 고쳐보려다 안되서 double 형을 사용하니 해결이 되었다.

소스

1644 소수의 연속합

자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제이다.

단순히 에라토스테네스의 체로 소수를 구하고 그 소수에 대해 반복하면서 그 소수부터 연속으로 더할 때 N이 나오는지를 따져주면 된다.

소스

1990 소수인팰린드롬

a 이상 b 이하인 소수이면서 팰린드옴인 수를 찾는 문제이다.

재귀를 통해 팰린드롬을 만들어주고, 완성이 되면 그 수가 소수인지를 검사해서 쌓는다.

그 다음 a와 b사이의 소수인팰린드롬 수를 출력해주면 된다.

소스

1312 소수

소수문제인데 문제에서 흔히 푸는 그 소수가 아니라 소수점할때 그 소수이다.
두 수 a, b를 나눌 때, 소수점 N번째 자리수를 구하는 문제이다.

그냥 바로 나눠주면 되는 문제라고 생각했으나, N의 범위가 백만가량 되기 때문에 일반적인 방법으로는 구할 수 없다.

이 문제는 우리가 손으로 소수를 구할 때 사용하는 방법을 그대로 구현해주면 된다.

피제수를 10씩 곱하면서 제수로 나눈값이 그 자리 숫자가 되고, 나머지가 그 다음 연산을 위해 사용되는 값이 된다.

소스

1747 소수&팰린드롬

n보다 큰 소수이면서 팰린드롬인 숫자를 찾는 문제이다.

단순히 n부터 1씩 증가시키면서 소수이면서 팰린드롬인 수가 발견되면 출력하면 된다.
이 때 팰린드롬의 숫자가 소수보다 개수가 적어서 그런지, 팰린드롬을 찾고 소수를 판별하는것이 소수를 찾고 팰린드롬을 판별하는것보다 훨씬 빨랐다.

소스

1963 소수 경로

주어진 소수p를 한 숫자만 바꾸면서 소수 q를 만들려고 한다. 이때 바꾸는 과정에서 나온 숫자도 무조건 소수여야 할 때 최소 몇번을 걸쳐야 되는지를 구하는 문제이다.

이 문제는 다른 소수문제와는 다르게 BFS가 필요한 문제이다. 현재 소수를 큐에 넣은다음, 큐에서 빼내면서 그 소수로 만들 수 있는 다른 소수들을 집어넣어준다.
그런 과정을 계속하면서 카운트를 해주고, q를 발견하면 그 값을 출력하면 된다.
다른 소수를 만드는 방법은 각 자리 숫자들의 숫자를 0~9까지 바꿔가면서 소수판별을 해주면 된다.

소스

9764 서로 다른 자연수의 합

어떤 숫자 N를 서로다른 자연수의 합으로 나타낸다 할 때, 순서를 따져주지 않을때의 경우의 수를 구하는 문제이다.

처음엔 재귀를 통해 문제를 풀었으나 7초나 되는 시간제한에도 불구하고 시간초과가 났고..
어찌어찌 내 PC에선 6초대로 줄였으나 여전히 시간초과가 발생했다.
그래서 할수없이 값을 전부 출력해서 직접 저장해주고 문제를 해결하였다. 사실 이렇게 문제를 푸는건 좋지 않아서 좀 씁쓸하다.

소스

2876 그래픽스 퀴즈

한 책상에 두명의 학생이 앉아있고, 책상은 일렬로 N개 놓여있다고 할 때, 책상마다 한명씩 뽑을 때 같은 등급이 가장 길게 이어져있는 경우의 길이를 구하는 문제이다.

등급이 5개밖에 되지 않으므로 1등급부터 시작해서 책상의 두 학생중에 아무나 그 등급을 가지고 있다면 카운트하고 없다면 초기화 해서 길이가 가장 긴 경우를 구해주면 된다.

소스

2023 신기한 소수

어떤 소수가 뒤에서 부터 한숫자씩 끊어내도 계속 소수일 때 이것을 신기한 소수라고 한다. N 자리 숫자중에 신기한 소수를 출력하는 문제이다.

신기한 소수를 예로 들면, 7331 은 소수이고, 733도 소수, 73도 소수, 7도 소수이다.

이 문제는 재귀로 해결이 가능하고 순서는 다음과 같다.
1. 1의자리 소수를 구한다. 1의 자리 소수는 2,3,5,7이 있다.
2. 이 숫자를 가지고 작은것부터 시작해서 재귀를 한다. 재귀는 현재 숫자와 현재 자리수를 같는다.
3. 재귀를 하면 현재 숫자의 뒤에 0~9까지 숫자를 붙여서 소수인지 판별한 다음, 소수라면 길이가 N이 될때까지 재귀한다.

소스

2740 행렬 곱셈

N*M 행렬과 M*K 행렬이 주어지면 이 행렬을 곱한 행렬을 구하는 문제이다.

두 행렬을 곱하게 되면 N*K 행렬이 생긴다.
행렬의 곱셈 규칙을 이용하여 단순히 구해주면 된다.

소스

3845 잔디깎기

잔디를 깎는데, 모든 칸이 세로로도 가로로도 깎였는지를 검사하는 문제이다.

처음엔 단순하게 map 배열을 이용하여 깎일때마다 표시를 하게끔 하려 했는데, 입력이 소수였다. 게다가 소숫점 아래 7자리..

이 문제는 정렬을 이용하면 쉽게 해결이 가능하다.

우선 가로,세로 깎은 좌표에 대해 오름차순으로 정렬한 다음, 왼쪽 맨 끝부터 시작해서 검사를 한다. 만약 새 좌표가 이전에 깎지못한 좌표를 포함하고 있지 않다면, 이것은 NO이다. 포함하고 있다면 깎인 좌표를 이동하고 다음 좌표를 검사한다.
NO가 발견되지 않았다면 YES를 출력하면 된다.

소스

1213 팰린드롬 만들기

영어로된 문자열이 주어지면 문자의 순서를 마음대로 섞어서 팰린드롬을 만들려고 할 때, 사전순으로 가장 앞서는 팰린드롬 문자열을 구하는 문제이다.

이 문제를 풀기위해 필요한것은 다음과 같다.
1. 정렬(오름차순)
2. 가능/불가능 판별(홀수개수의 알파벳이 두개이상 존재)

위 사항을 구현했다면, 앞에서부터 같은 알파벳을 두개씩 골라 앞,뒤로 배치하면된다.
이 때 홀수개수의 알파벳이 있다면 같은 알파벳이 두개가 나오지 않을 때가 있는데, 그 알파벳은 따로 뒀다가 정중앙에 붙여주면 된다.

소스

1331 나이트 투어

6*6 체스판을 나이트로 모든곳을 탐색 하고 마지막엔 제자리에 돌아온다고 할 때 입력으로 주어진 좌표가 맞는좌표인지 아닌지 구분하는 문제이다.

따져줘야 할 것은 다음과 같다.
1. 나이트의 이동이 맞는가(한쪽 2칸 다른쪽 1칸)
2. 모든 이동이 마친 후 모든곳을 탐색했는가
3. 마지막 입력으로부터 나이트의 이동으로 시작 좌표에 도착할 수 있는가

셋중 하나라도 틀리면 Invalid 를, 맞으면 Valid 를 출력하면 된다.

소스

3221 개미의 이동

일자로 된 나무에 개미가 올려져있고, 위치와 이동방향이 주어진다. 이동하다가 나무 양 끝이나 다른 개미를 만나면 바로 방향을 바꿔 이동한다 할 때, T초 후 개미의 위치를 구하는 문제이다.

이 문제를 푸는 핵심은 바로 개미 이동의 성질이다. 예를들면 개미가 위치 P 에서 왼쪽으로 이동한다 할 때, 왼쪽 끝에 도달하는 시간은 P초일 것이다. 그리고 그것은 그 앞에 어떤 개미가 막고 있던지 마찬가지이다. 사실 현재 개미가 P초 만에 도달하는것은 아니고, 개미가 부딫힘으로 인해 다른 개미에게 자신의 방향을 넘겨주기 때문에, 다른 개미가 결국 P초에 왼쪽 끝으로 도달하게 된다.

따라서 개미를 한쪽 벽으로 보내고, T초를 길이로 나누게 되면 나눈값이 짝수일땐 개미는 제자리, 홀수일땐 반대편 벽에 있게 되고, T초를 길이로 나눈 나머지를 거기서 더해주면 T초후 개미의 위치를 구할 수 있다.

소스

5637 가장 긴 단어

여러 기호가 섞인 문장이 주어졌을 때, 알파벳과 하이픈으로만 이루어진 가장 긴 단어를 출력하는 문제이다.

간단하게 처음부터 시작해서 알파벳과 하이픈으로만 이루어진 숫자면 카운트를 증가시키고, 그 외의 문자가 나왔을 땐 최대값을 갱신하고 카운터를 초기화 시킨다. 마지막엔 최대였던 단어를 출력하면 된다.

소스

2304 창고 다각형

기둥을 오복한 부분을 만들지 않고 전체를 덮을 때 사용되는 최소의 면적을 구하는 문제이다.

오목한 부분을 만들지 않는다는것은, 감소하다가 증가하는 일 없이, 쭉 감소하거나 쭉 증가하는것을 의미한다. 따라서 가장 높은기둥을 찾고, 그 기둥을 중심으로 왼쪽으로 감소, 오른쪽으로 감소 시키면서 면적을 구하면 된다.

다음 기둥을 고르는 방법은 끝부터 현재기둥 중에 현재기둥 다음으로 가장 높은 기둥을 찾으면 된다.

소스

1421 나무꾼 이다솜

N개의 나무가 있고, 그 길이가 주어진다. 각 나무를 잘라서 모두 똑같은 길이로 만들어 주려고 한다. 길이 1당 가격과 한번 자를 때 드는 비용을 주었을 때, 최대 이익을 구하는 문제이다.

이 문제는 자르는 횟수를 구하는것이 중요하다. 예를들어 한 나무의 길이가 5이고, 길이를 2로 맞춰서 자른다면, 2번 자르고 남은 길이 1을 버려주면 된다. 얼핏보면 5 / 2 를 내림해주면 될 것 같지만, 나무의 길이가 4라면 1번만 자르면 된다. 몇번 해보면 확실해지지만 결론은
(길이 - 1) / 2 해준것이 잘라낸 횟수이다.

모든 나무의 길이 중 최대값을 찾아서 그 길이부터 1씩 감소시키면서  모든 나무에 대해 몇번 자르고, 얼마만큼 버려서 얼마를 획득할 수 있는가를 구한다. 모든 나무를 다돌면서 얻은 돈의 최대값을 구해주면 된다.

소스

1773 폭죽쇼

N개의 폭죽이 일정 간격으로 터질 때, 종료 시간까지 초단위로 관찰 하려고 한다. 이 때 총 관찰된 시간을 구하는 문제이다.

이 문제는 체를 이용한 마킹 으로 풀 수 있다. 종료시간까지 초단위로 표시되는 배열을 잡고 각 폭죽마다 폭죽이 등장하는 시간에 전부 마킹을 해두고 겹치는 부분도 그냥 덮어씌운 다음 마킹이 되있는 부분만 카운트해주면 답을 구할 수 있다.

소스

1120 문자열

A, B문자열이 주어질 때, A문자열의 앞 뒤에 아무 문자열이나 붙여서 B와 길이를 똑같이 맞춘다고 할 때, A와 B문자열의 차이의 최솟값을 구하는 문제이다.

앞 뒤에 아무 문자열이나 붙여도 되므로 추가로 붙여주는 문자는 고려할 필요가 없다.
따라서 B문자열의 위치를 한칸씩 옮겨가면서 A문자열과 비교를 해주고, 그때마다 나온 차이의 최솟값을 구해주면 답이 나온다.

소스

1058 친구

N명의 친구 목록이 주어지면, 친구와 그 친구의 친구를 2-친구라고 한다.
이 때 2-친구의 수가 가장 많은 사람의 2-친구의 수를 구하는 문제이다.

우선 N*N 배열을 잡고, 각 사람마다 친구인지 아닌지 표시한다.
그 다음 자신의 친구에 대해서 그 친구와, 그 친구의 친구를 자신의 2-친구 를 기록하는 배열에 추가한다.

마지막으로 각 사람마다 2-친구의 숫자를 구해 최대를 찾아주면 된다.

소스

2853 배

여러 배들이 일정한 간격으로 돌아온다고 할 때, 배가 한척이라도 돌아온 날을 기록한다.
그 기록을 가지고 배가 최소 몇대있는지를 구하는 문제이다. 첫날엔 모든 배가 동시에 도착했다고 가정한다.

만약 배가 2일 주기로 온다면, 첫날을 0일이라 할 때, 2 4 6 8.. 일에 도착할 것이다.
같은 원리로 배가 n일 주기로 온다면 n, 2n, 3n, ... 일에 도착한다.

따라서 배가 돌아온 날짜를 하나씩 저장하면서 현재도착한 날짜가 이전에 도착한 날짜와 나누어 떨어진다면, 이 배는 예전에 왔던 배로 간주하여 카운트 하지 않는다. 그 외엔 카운트 해주면, 배의 개수의 최소를 구할 수 있다.

소스

2564 경비원

w*h크기의 블록의 경계에 상점들이 있고, 그 어느 한 좌표에 경비원이 있다고 할 때, 경비원의 그 위치에서 각 상점까지 가는 최단거리의 합을 구하는 문제이다. 단, 경비원은 경계로만 이동해야 한다.

최단거리라고해도 사실 한 위치에서 다른 한 위치로 가는 최단거리는 이 문제에서 두가지 경우밖에 없다. 그것은 한쪽으로 가는 거리와 경계의 총 길이에서 그쪽으로 가는 거리를 빼준 거리이다. 따라서 각 상점마다 방금말한 두 거리중 작은값을 구해서 더해주면 된다.

소스

8974 희주의 수학시험

1 2 2 3 3 3 4 4 4 4 ... 이런식으로 늘어나는 수열이 있을 때, 수열의 a번째에서 b번째사이의 합을 구하는 문제이다.

1부터 직접 수열을 구현하면서 a번째부터 b번째사이일 때 숫자를 더해주면 된다.

소스

1038 감소하는 수

큰 자리수부터 작은 자리수 까지 계속 감소하는 수를 감소하는 수라고 한다. 이 때 N번째 감소하는 수를 구하는 문제이다.

마땅한 방법이 떠오르지않아서 첫 번째부터 N 번째까지 감소하는 수를 전부 구해주었다.
구해 주는것은 숫자를 증가시켜주면서 감소하는 수가 되지 않을때 그 다음 자리수를 늘려주고 그 아래는 다시 초기화시켜주는 방법으로 구현하였다.

소스

2493 탑

N개의 탑이 일렬로 세워져 있고, 탑마다 높이가 각각 주어진다. 탑은 자신의 높이와 수평으로 왼쪽에 레이저 신호를 보낸다고 할 때, 각 탑의 레이저가 수신하는 탑의 번호를 출력하는 문제이다.

이 문제를 풀기 위해선
처음부터 반복을 하면서 자신의 높이에 어떤 탑이 수신하는가를 확인하기 위해 이전 탑을 들여다 볼 필요가 있다. 그러나 단순히 하나하나 들여다 보았다간 TLE를 받게 된다.
따라서 어느정도 워프가 필요하다. 바로 왼쪽 탑을 확인해서 그 탑의 높이가 자신보다 낮다면, 그 왼쪽탑이 송신에 성공한 곳으로 간다. 그리고 거기서도 비교해서 송신이 불가능 하다면 다시 반복해준다. 물론 어느곳에도 송신이 불가능한 경우또한 따져주어야 한다.

소스

2261 가장 가까운 두 점

2차원 평면에 가장 가까운 두 점의 길이를 찾는 문제이다.

단순히 모든 두 점을 비교해주면 TLE를 받게 된다.
이 문제는 정렬로 해결할 수 있다. 먼저 점들을 x좌표의 오름차순으로 정렬을 해주고, 바로 인접한 두 점의 길이를 구해 최소를 저장한다.
그리고 나서 y좌표의 오름차순으로 다시 정렬해 준다음 앞서 한것과 똑같이 비교를 해주면 가장 가까운 두 점을 구할 수 있다.

소스

LIS

LIS는 최장 증가 부분 수열로, 어떤 수열에서 점점 증가하는 부분 수열중 가장 긴것을 찾는 알고리즘이다.

이 수열 자체를 찾을 수 있는 방법과, 길이만 알 수 있는 방법이 있고, 둘다 O(nlogn)으로 해결이 가능하다. 전자는 구현이 복잡해서 후자로 구현해보았다.

후자는 이진탐색과 새로운 배열로 구현이 가능하다.

소스

Binary Search

이진탐색 알고리즘은 정렬이 되어있는 배열에서 원하는 값을 O(logN) 으로 찾는 알고리즘이다. 인덱스의 중간부터 시작해서 점점 거리를 좁히는 방법으로 원하는 값을 찾는다.

소스

1965 상자넣기

앞에서부터 차례대로 증가하는 부분 수열의 개수가 가장 긴 것의 길이를 구하는 문제이다.

이것은 LIS(Longest Increasing Subsequences) 문제로, 직역하자면 최장 증가 부분 수열문제이다. 

이 문제는 O(nlogn)으로 풀이가 가능하다. 이 문제를 해결하는대에도 여러 해법이 있지만, 내가 사용한것은 추가 배열과 이진탐색을 이용하여 문제를 해결하였다.

소스

9626 크로스워드 퍼즐

단순한 꾸미기 문제이다.
별다른 설명은 필요 없을 듯 하다.

소스

6378 디지털 루트

숫자 n을 자리수만 다 더하고, 그 수가 일의자리수가 될 때 까지 계속 반복한다 할 때, 마지막으로 나오는 일의 자리수를 구하는 문제이다.

길이가 나와있지않지만 실험을 통해 1000이라는것을 밝혀냈다. 그만큼 문자열로 받아온다음에 각 자리수를 더해주고 반복하면 된다.

소스

2156 포도주 시식

포도주가 일렬로 놓여있고, 각 포도주마다 가중치가 있다. 연속된 세개의 포도주를 고를 수는 없다고 할 때, 가중치의 합의 최대를 고르는 문제이다.

DP로 해결이 가능하다. 여기서 DP는 i번째까지 골랐을 때 가중치의 합의 최대값을 나타낸다. 비교는 i번째의 두칸 전 DP와 세칸전 DP + 한칸 전 포도주 중 큰 값을 고르면 된다.

소스

2164 카드2

2161 카드1 과 같은 문제에 범위가 크게 잡혀있다.

카드1 처럼 배열로 풀어도 해결이 가능한데, 다른사람의 소스를 보니 2의 배수로 나누어주면서 재귀로 해결이 가능한 듯 하다. 서울대생의 소스였는데 역시 서울대생..

소스

1931 회의실배정

한 방에 N개의 회의 시작 시간과 끝시간을 주었을 때, 회의가 겹치지 않으면서 최대한 많은 회의를 할 때의 회의 수를 찾는 문제이다.

처음엔 복잡하게생각해서 이러저러한 알고리즘을 찾아 다녔는데, 다시 생각해보니 간단했다.

회의 들을 끝 시간을 기준으로 오름차순으로 정렬한 뒤, 처음의 끝시간을 max로 잡고 반복하면서 max값과 다른 회의의 시작 시간을 비교해줘서 max값 이상이면, 다시 max를 그 회의의 끝시간으로 잡는다. 이렇게 max값이 갱신될 때 마다 카운트 해주면 답을 구할 수 있다.

소스

2399 거리의 차이

수직선에 N개의 좌표가 찍혀 있을 때, 가능한 모든 쌍의 거리의 합을 구하는 문제이다.

범위가 적어서 그대로 구해주었다. 다른 방법으로는 정렬을 해서 그 위치와 연관되게 구해주는 방법이 있다.

소스

1406 에디터

문서편집기 처럼 문자사이를 왔다 갔다 하면서 삽입, 삭제를 수행하는 에디터를 만드는 문제이다.

중간에 삽입을 하려면 일반 배열로는 한칸씩 밀어야만 한다. 따라서 연결리스트를 이용하여 삽입 삭제를 해주면 간단하게 해결이 된다.

소스

4095 최대 정사각형

1915 가장 큰 정사각형 과 거의 같은 문제이다.
다른 점은 넓이 대신 한변의 길이만 출력하면 된다.

소스

1915 가장 큰 정사각형

n * m의 배열에 0,1 의 값이 있는데, 1의 값으로 채워져 있는 가장 큰 정사각형의 넓이를 구하는 문제이다.

이 문제는 DP로 해결이 가능한데, dp를 구성하는 방법은 다음과 같이 하면 된다.


(i = 0~m-1, j = 0~n-1)
dp[0][j] = 좌표값이 1이면 1, 아니면 0.
dp[i][0] = 좌표값이 1이면 1, 아니면 0.

i,j 좌표값이 1일 때,
dp[i][j] =  1+MIN(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])

이 때 나온 dp 값중에 최대값을 저장해서, 넓이를 출력하면 된다.

소스

4998 저금

N원에서 년 b%복리로 M원을 넘기려할 때 몇년이 걸리는가를 구하는 문제이다.

복리기 때문에 년마다 N원에 계속 현재 N원의 b%씩 쌓아가면 된다.

소스

2636 치즈

2638 치즈 와 같은 문제인데, 여기서 두 면에 닿아야 녹는것을 한 면으로 고치고, 전부 녹기 바로 전날의 치즈 개수만 구해주면 된다.

소스

2355 시그마

두 수 i,j 사이에 있는 정수의 합을 구하는 문제이다.

두 수중 큰것을 i로 놓고, 작은것을 j로 놓아준 다음,
1부터 i 까지의 합에서 1부터 j까지의 합을 빼주면 된다.

소스

1236 성 지키기

주어진 크기의 모든 행, 모든 열에 경비원을 한명씩은 배치하려고 할 때 추가로 배치해야하는 경비원의 수의 최솟값을 찾는 문제이다.

각 행과 각 열에 경비원이 몇명이나 배치되어있는지 확인하고,
행에 비어있는 경비원의 수와 열에 비어있는 경비원의 수중 큰값을 고르면 필요한 경비원의 수의 최소가 된다.

한 경비원이 한 행,한 열을 차지하도록 놓을 수 있기 때문이다.

소스

2638 치즈

치즈가 외부 공기 두 면이상에 노출되면 녹는다고 한다.
이 때 치즈가 모두 녹으려면 몇일이 걸리는가를 구하는 문제이다.
단, 내부에 뚫려있는곳은 녹는것과 관련이 없다.

맵을 한바퀴 돌면서 치즈가 있다면 치즈의 4 방향을 살펴봐서 2 방향이상이 외부와 접촉한다면 녹이면 된다.

여기서 외부와 내부를 구별하는 방법은, 외부는 항상 0,0과 이어져있다. 따라서 0,0을 시작으로 연결되어있는 모든 위치에 외부라는 표시를 해두고, 치즈를 녹일때도 그 외부인 표시만으로 판별해주면 된다.

소스

1952 달팽이2

m줄 n칸의 격자에 달팽이 수열을 그리려 할 때, 위치가 꺾이는 곳의 수를 구하는 문제이다.

직접 돌아줘도 되는데, 이런답도 된다고 한다.

m > n ? 2*n-1 : 2*m-2

정확히 왜 이렇게 되는지는 모르겠다.

소스는 직접 돌아주는것으로 첨부한다.

소스

1388 바닥 장식

바닥 장식에 필요한 나무 판자의 개수를 물어보는 문제이다. 이어져있는 판자는 같은것이라고 취급한다.

문제 대로 판자가 있으면, 카운트를 1 더해주고 그 판자 및 이어져있는 판자를 제거해준다. 그렇게 계속 돌면서 판자가 다 없어질 때 까지 하면 된다.

소스

9465 스티커

스티커가 2줄로 배치되어 있고 각 자리마다 가중치가 주어진다.
한 위치의 스티커를 때어내면, 그 상 하 좌 우의 스티커도 같이 떨어진다고 할 때,
때어낸 스티커의 가중치의 합의 최대를 구하는 문제이다.

전형적인 DP 문제로, 이런 DP를 구상할 수 있다.
바로 이전 스티커가 때어졌다면, 현재 위치의 스티커는 때어낼 수 없다. 하지만, 바로 이전 스티커의 반대편 스티커가 때어졌다면, 그 스티커와 현재위치의 스티커 모두 때어낼 수 있다.
따라서 바로 이전 스티커와 바로 이전 스티커의 반대편 스티커 + 현재 위치의 스티커중의 최대값을 고르면서 DP를 진행하면 정답을 구할 수 있다.

소스

2992 크면서 작은 수

숫자 N의 각 자리수를 조합해서 N보다 크면서 그중에 가장 작은 수를 구하는 문제이다.

여러 방법이 있을것 같은데 내가 한 방법은, 재귀를 통해 모든 경우의 수를 구해서 조건에 맞는수를 골라주었다.

소스

9242 폭탄 해체

도형으로 나타내진 숫자가 주어지고, 그 숫자가 6으로 나누어 떨어질 때 BEER!!을, 나누어 떨어지지 않거나 잘못된 숫자일 경우 BOOM!! 을 출력하는 문제이다.

도형을 정확하게 숫자로 나타내주고, 6으로 나머지연산을 해주면 된다.

소스

8911 거북이

거북이가 2차원 평면위에 있고, 다음의 4가지 명령을 내릴 수 있다고 한다.
1. 앞으로 가기
2. 뒤로 가기
3. 왼쪽으로 90도 회전
4. 오른쪽으로 90도 회전

이 때 주어진 명령으로 거북이가 지나간 영역을 감싸는 직사각형의 넓이를 구하는 문제이다.

이것은 거북이의 좌표를 0,0으로 잡고, minX,minY, maxX,maxY 를 구해주면 된다.
현재위치를 잡고, 회전은 행렬의 회전공식을 이용하여 회전해주면서 1,2번 연산을 수행해주면 된다.

면적은 (maxX-minX)*(maxY-minY) 로 나타낼 수 있다.

소스

2231 분해합

어떤수와 그 수의 각 자리수의 합이 N 이 되는 어떤 수를 찾는 문제이다.

반대로 생각하면 N을 이용해 어떤 수의 범위를 특정 지을수 있다.

결론부터 말하자면 N - N의 자리수 * 9 보다 크거나 같고 N보다 작다.
예를들면 N이 987 이라고하면, 어떤 수 X는 N 보다 작으면서 N - 3*9 보다는 크거나 같을 것이다. 각 자리수를 아무리 더해봤자 각 자리수의 최대는 9이고 더하는 횟수도 N의 자리수보다 작거나 같기 때문이다.

그 범위부터 N-1까지 더해봐서 나타나면 출력하고, 나타나지 않으면 0을 출력하면 된다.

소스

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인 경우를
판별하면 된다.

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

소스

1069 집으로

2차원 그래프에서 0,0으로 다음의 두 조건을 통해 가려 할때의 최솟값을 찾는 문제이다.
1. 1초에 1의 속도로 걷는다.
2. t초에 d 만큼 점프한다. (직선으로만 도중에 멈추기 안됨)

이 문제는 두 점을 잇는 직선으로만 생각하면 안된다. 왜냐하면 각도를 조금 틀어서 한 번 더 점프하는것이 이득인 경우가 있기 때문이다.
내가 본 가장 효과적인 방법은
점프 가능한 거리만큼은 점프를 하고 나머지 1번을 여러 케이스로 나눠서 최솟값을 찾는것이다. 보면 구현은 쉽지만 각 케이스가 실제 그런지에 대한 고민이 필요하다.

나는 결국 생각하지 못하고 다른 사람이 올린 소스를 중심으로 풀었다.
반성이 필요한 순간이다..

소스

2417 정수 제곱근

정수의 제곱근을 찾아 올림하는 문제이다.

간단하게 sqrt 함수와 ceil 함수를 이용했다. 이렇게 하지 않고 반복문을 통해 하는 방법도 가능하다.

소스

Pollard's Rho

어떤 수의 인수(factor)를 찾아내는 알고리즘이다.
특히 큰 수의 인수를 찾을 때 유용하고, 메모리를 거의 차지하지 않으며 O(n^(1/4))의 시간복잡도를 보인다고 한다.

gcd 와 x^2+-a (1,-1) 을 이용하는데, 정확한 수학적 원리는 모르겠다.
실제 테스트를 해봤는데, 약수를 전부 찾아내는건 아니지만 큰 수인데 인수가 2~3개 밖에 안되는 경우도 빠르게 찾아냈다.

참고

소스

modular exponentiation

a^b mod c 를 구하는 알고리즘이다.
단순하게 a^b를 하고 c로 나머지를 하면 프로그래밍에서 오버플로우가 발생하기 때문에,
중간과정에 modular 연산을 해줌으로써 오버플로우를 방지한다.
물론 이렇게 해도 결과가 달라지는 일은 없다고 한다.

b승을 단순히 a를 b번 곱하는 식으로 하게 되면 O(b)의 시간복잡도가 생기는데,
이것은 빠른 방법이 아니다.
이에 관련된 알고리즘엔 여러가지가 있는데,
이 중 하나의 방법으로 2씩 나눠가는 방법이 있다.
a^b = (a^2)^(b/2) 라는것을 이용하여 O(log2(b)) 의 시간복잡도 안에 해결 가능하다.

소스

2986 파스칼

파스칼 코드로 되어있는 프로그램의 결과를 출력하는 문제이다.
파스칼 코드의 의미는 N-1부터 1까지 반복하면서, N과 나누어떨어지는 수가 발견되면 그 숫자가 나올때까지의 반복횟수를 출력하는것이다.

사실 이 소스를 그대로 C로 구현해도 정답이 맞아야 하지만, 얄밉게도 TLE가 발생하는 구조로 되어있다.

따라서 이 문제는 N보다 작으면서 N과 나누어떨어지는 수의 최댓값을 찾아야 하는데,
이는 N을 N의 가장 작은 약수로 나눈값과 같다.

따라서 N의 가장 작은 약수를 찾으면 되는데, 이것은 O(root(N))의 시간복잡도를 가지게 찾을 수 있다.

소스

5054 주차의 신

가게가 일렬로 되어 있을 때, 모든 가게를 들른다고 가정하면 차까지 돌아오는 거리가 가장 짧은 경우를 출력하는 문제이다.

얼핏보면 주차의 위치를 선정해야하는 것처럼 보인다. 하지만 사실은 어느곳에 주차를 하던 상관이 없다. 왜냐하면 차까지 돌아오는 거리가 가장 짧으려면, 주차된 위치에서 오른쪽 끝 가게 까지 일직선으로 들렀다가 돌아오고, 다시 왼쪽 끝 가게 까지 일직선으로 들렀다가 돌아와야 하는데, 그 거리는 왼쪽 끝에서 오른쪽 끝까지의 거리의 2배가 되기 때문이다. 따라서 어디다 주차를 하던, 왼쪽 끝과 오른쪽 끝 사이의 거리는 일정하기 때문에, 답은 이 값의 2배를 한 것이다.

소스

2607 비슷한 단어

첫번째 단어와 비슷한 단어의 갯수를 구하는 문제이다.
비슷한 단어란, 처음단어와 주어진 단어가 사용된 문자, 문자의 갯수가 같거나, 문자를 하나 더하거나 빼주거나 한 문자를 다른 문자로 바꿔 주는 작업을 통해 앞의 조건을 만족한다면 비슷한 단어라고 한다.

이 문제를 푸는 방법은, 처음 단어의 사용된 문자와 횟수를 담는 배열을 만들어 주고, 주어지는 단어의 배열도 만들어 준 다음, 둘을 서로 비교하여 횟수가 다른것을 찾아야 한다. 횟수가 다른것에 여러 패턴이 있는데, 그것들을 이용해서 둘이 같은단어인지, 한번의 작업을 통해야 하는지, 둘이 다른단어 인지를 밝혀내면 된다.

소스

2563 색종이

도화지에 색종이를 겹쳐 쌓았을 때, 색종이가 이루고있는 면적을 구하는 문제이다.

간단하게 좌표마다 색종이가 쌓였다는 표시를 해주면서 덧붙여주고, 마지막에 한번 싹 훑으면서 쌓아가면 답이 나온다.

소스

9081 단어 맞추기

주어지는 단어에서, 단어안의 알파벳으로만 이루어진 단어를 사전순으로 나타낸다고 할 때, 주어진 단어의 다음번에 나오는 단어를 출력하는 문제이다.

이 문제를 풀기 위해선 단어를 정렬하는 과정이 필요한데, 문제는 어떤단어를 얼마나 정렬하는가 이다. 내가 푼 방법은 단어의 끝부터 시작하여 알파벳을 고르고, 그 알파벳을 앞의 알파벳과 비교하면서 위치를 바꿨을 때 사전순으로 뒷서는지를 검사한다. 그런 알파벳이 여러개 존재할 때는, 바꾸는 위치가 가장 뒤로가 있는것(변화가 가장 작은것)을 택한다.

만약 그런 알파벳이 존재하지 않으면 그대로 뿌리면 되고, 존재해서 찾았다면 고른 알파벳을 찾아낸 위치에 끼워 넣는다. 그리고 그 뒤의 문자열을 오름차순으로 정렬해주면 된다.

소스

4773 로마 숫자 계산기

로마 숫자로 사칙연산을 수행하는 프로그램을 만드는 문제이다.
단, 숫자를 스택구조로 저장하여, 한번에 여러 숫자를 저장할 수도 있고, 연산한 결과를 계속 이어갈 수도 있다.

이 문제를 풀기위해선 우선 스택구조를 만들어야 한다. 나의 경우는 data_structure 태그에 있는 소스를 이용했다. 스택을 구성했으면 입력을 받아온 것이 로마숫자일 경우, 10진법으로 바꿔서(rome2dim) 스택에 push 하고, 연산자일 경우 연산을 해준다.
연산을 해줄땐 단순히 10진법으로 계산을 하고 출력할때만 다시 로마숫자로 바꿔주면 된다.(dim2rome)
여기서 연산은, 두 숫자를 pop 하고, 연산한 하나의 값을 다시 push 해주는것을 말한다.
단, = 연산자는 pop하지않고 뿌려주기만 한다.

여기서 주의해야 할 것은 예외인데, 그 상황은 아래와 같다.
1. = 연산자가 들어왔을때, 스택에 아무것도 없으면 stack underflow
2. = 연산자인데 가장 첫값이 1보다 작거나 4999보다 크면 out of range exception
3. 연산자인데 = 가 아닐때, 스택에 데이터가 두개보다 적으면 stack underflow
4. / 연산자일 때 나누어 주는수가 0이면 division by zero exception

1,2,3번 상황이 발생하면 오류메세지만 뿌려주고 연산을 수행하지 않고, pop도 하지 않는다.
4번 상황이 발생하면 0이 아닌 다른값만 push 해준다.

p.s. 나누기 연산은 int형의 나눗셈만 하면 된다. (소숫점이면 맨붕..)

소스

2608 로마 숫자

두 로마숫자의 합을 물어보는 문제이다. 로마숫자는 아래와 같다.

합을 구하기 위해서 로마숫자를 10진법으로 바꾸고, 10진법을 로마숫자로 바꾸는 방법을 이용했다.

로마숫자를 10진법으로 바꾸는 방법은, 앞자리 부터 시작해서 기호에 맞는 문자를 찾아 그 숫자를 더해주면 된다. 이 때 CM(900) 과 같은 경우만 고려해주면 된다.

10진법을 로마숫자로 바꾸는 방법은 1000부터 시작하여 10씩 나눠가면서 비교한다. 이 값일 m이라고 할 때, 해당 숫자가 m 이상이면  각 숫자에 맞는 문자를 추가해준다.
이 땐 900, 500, 400의 경우까지 합쳐 총 4번을 검사해주면 된다.

소스

1914 하노이 탑

하노이 탑에 원판이 n개 쌓여있을때, 옮기는데 드는 총 횟수와 옮기는 과정을 출력하는 문제이다.

하노이 탑이란
3개의 기둥이 있고, 처음 기둥에 n개의 원판이 크기가 큰 순서대로 쌓여있다.
이 원판들을 3번째 원판에 모두 옮겨야 하는데,
한번에 1개의 원판만 옮길 수 있고, 작은 원판위에 큰 원판을 올릴 수 없다는것이 규칙이다.

스페셜 저지 문제가 아니기 때문에 항상 최적의 경우를 구해야만 하는데,
최적의 해의 횟수는 2^n - 1 번이다.
머리를 짜보았지만 도저히 알고리즘이 떠오르질 않아서 검색을 했는데,
재귀를 이용해서 문제를 푸는 것이었다.

답은 맞았지만 알고리즘을 봐도 원리가 정확히 이해가 되지 않아서 푼거같지가 않다..

소스

1065 한수

1부터 N까지 각자리의 수가 등차수열인 숫자의 갯수를 구하는 문제이다.
무언가 공식이 있을법 하지만 범위도 적기때문에
직접 구해주었다.
1의자리와 10의자리의 공차를 구한 다음, 각자리마다 전부 같은가 비교해주면 된다.

소스

2072 오목

두 플레이어가 오목게임을 한다고 했을때, 몇수에서 승부가 나는가를 판단하는 문제이다.

오목에서 승부가 난다는것은 한쪽이 연속으로 5개의 돌을 놨다는 말이다.
따라서 돌을 놓을때마다 가로,세로 , 두 대각선을 중심으로 돌이 5개 놓여져있는가를 판단해주면 된다. 이때, 돌이 5개 이상일 경우에는 승리가 아니므로 주의해야 한다.
3,3같은 금지룰이 없어서 다행이다.

소스

4880 다음수

세 수가 등비수열인지, 등차수열인지를 판단하는 문제이다.

세 수를 a,b,c라고 하면, b-a와 c-b가 같으면 등차, b/a와 c/b가 같으면 등비이다.
이를 이용해서 답을 출력하면 된다.

소스

1252 이진수 덧셈

두 이진수를 덧셈하는 문제다.
파이썬같은 언어로는 바로 덧샘해주면 그만이지만, C에서는 생각보다 쉽지 않다.

우선 길이가 80이기때문에 문자열로 받아주어야 한다.
그리고 두 이진수를 첫자리부터 계산해주기 위해 reverse를 한다.
첫자리부터 계산을 하는데, 범위는 가장 큰 문자열로 한다.
각 자리의 숫자는 '1'과 '0'의 문자로 되어있기 때문에, 그 자리의 문자가 '1'이면 1, 아니면 0으로 바꾸어주고, 덧셈을 한다.
덧셈을 할때 해당자리는 2로 나눈 나머지 값을 놓으면되고, 만약 각 자리가 1,1이라 자리올림이 생기면 처리해주는 변수를 따로 둔다.
이때 바로 출력하지말고 출력할 버퍼에 하나씩 쌓는다.
반복이 끝나면 맨마지막 자리에 올림이 발생했는가를 판단해서 추가해주고,
출력버퍼를 reverse 해준다.
그 후 시작부터 끝까지 보면서 0으로 시작하는 경우엔 잘라내준다.

첨엔 간단해 보였으나 생각보다 어려운 문제였다.

소스

1922 네트워크 연결

N개의 컴퓨터를 전부 하나의 네트워크로 묶으려고 할 때,
가장 작은 비용이 드는 경우를 고르는 문제이다.

딱봐도 간선문제인것이 그래프 문제라는 생각이 들었고,
그래프 알고리즘 중에서 프림알고리즘이 이 문제와 알맞는 알고리즘이라고 생각했다.
프림알고리즘은 자신의 영역과 이어진 간선중에서 가장 최소가 되는 간선을 골라서 자신의 영역을 늘려가는 방식이다. greedy 알고리즘의 일종인데, 보통 greedy 알고리즘은 최적의 결과를 낳지는 않는것으로 알려져 있으나, 이 알고리즘은 특이하게도 greedy 알고리즘이면서 최적의 결과를 낳는 알고리즘이다.

그래서 prim알고리즘을 적용하여 정답을 맞았으나..
TLE에 아주 아슬아슬하게 걸쳐있었다. 다른 사람의 소스는 매우 짧은 시간이 소요된것에 비해 내 방법은 매우 느린 결과를 보였다.
그래서 다른 사람의 소스를 살펴보니, 간선정보들을 오름차순으로 정렬하고 거기서부터 하나씩 뽑아서 연결하는 방법이었다.

그래프 알고리즘에 정렬을 사용한다는 생각은 못하고 있엇는데 역시 실력차이인것 같다.

소스

Queue

Queue 구조는 Stack 구조와 같은 연결리스트(Linked List) 방식이다. 다만, pop하는 과정에서 Stack 처럼 LIFO 가 아닌 FIFO(First In First Out) 방식을 사용한다.
다른 설명은 Stack과 같으니 생략한다.

소스

Stack

Stack 구조는 연결리스트(linked list)의 한 갈래이다. 연결리스트는 자신이 자신의 다음 위치(pointer)를 담고있는 자료구조이다.

연결리스트 함수의 구성은 push와 pop 으로 되어있다. push 는 새로운 데이터를 연결리스트를 이용해 추가하는 함수이다. 배열의 다음 index에 값을 넣는과정과 비슷하다. 단, 여기선 동적 할당을 이용하여 새로운 데이터를 넣는다.
pop 은 넣은 데이터를 빼내는 함수이다. pop 함수의 데이터를 빼내는방법은 여러가지가 있다.

Stack 구조의 특성은, 가장 나중에 넣은 데이터가 가장 먼저 나온다는 점이다. (LIFO -> Last In First Out) 즉, pop 함수는 새로 넣은 값을 뽑아 내도록 해야 한다.

소스에는 이 두 함수 외에도 init, destroy 등등 여러 함수가 들어있고, 점차 추가시킬 계획이다.

소스

1592 영식이와 친구들

원형 큐에서의 왼쪽,오른쪽 이동을 물어보는 문제이다.
일반 배열로도 문제를 해결할 수 있는데,
왼쪽으로 갈 때는, 현재위치에서 왼쪽으로 가는만큼을 뺀다.
만약 그 수가 음수가 되면, 거기에서 큐의 크기만큼을 더해준다.
오른쪽으로 갈 때는 현재위치에서 오른쪽으로 가는만큼을 더한다.
만약 그 수가 큐의 크기를 벗어나면, 큐의 크기만큼을 빼준다.

소스

9084 동전

2293 동전 1 의 문제와 똑같은데, 테스트 케이스가 추가된 문제이다.
별 어려울것 없이 2293의 소스에 입력을 맞춰주면 된다.

소스

2684 동전 게임

동전의 앞뒷면의 결과를 가지고 연속된 3개의 결과를 나타내는 문제이다.
처음부터 마지막결과-2 까지 슬라이딩 하면서
알맞은 수열의 index에 추가해주면 된다.

소스

2293 동전 1

n개의 동전을 조합하여 k원을 만들 때 만들 수 있는 모든 경우의 수를 구하는 문제이다.
이 문제는 TLE가 중요하게 작용한다.
내가 처음에 생각한 방법은 재귀로,각 동전으로 만들 수 있는 돈의 모든 경우로 분기하여
K원이 될때 표시해주는 방식이었는데, 답은 정확했으나 쉽게 TLE가 발생했다.

그 다음으로 생각한것이 dp인데, 동전으로 만든 각 원에 대한 index 배열을 생성하고,
해당 동전을 0개~m개 사용할 때의 경우를 가정하여 계산했다.
정답은 맞았으나 다른 사람의 소스에 비해 시간이 많이 느렸다.

그래서 다른 사람의 소스를 살펴본 결과,
각 동전의 값어치 부터 k원까지 증가시키면서, 그 값에 원래의 값어치를 감소 시켰을 때의 배열값을 덧붙여 나가는 방법으로 해서, 소스도 시간도 줄이는 멋진 코드가 되었다.

역시 다른사람들의 소스를 보는것은 중요한 것 같다.

소스

2949 45도

문자열을 45도의 배수만큼 회전시키는 문제이다.
회전 알고리즘은 특정 좌표를 직접 회전시켜서 나온 좌표와 비교하면 편한데,
문제는 45도로 여러번 회전시킬 때이다.
결과적으로는 회전이 되긴하는데, 제자리 회전이 아니라 간격이 계속 벌어지게 된다.
이럴때 좋은 방법은 90도 회전을 따로 구현하는 방법이다.
90도 회전은 간격이 벌어지지않고 가로,세로 길이만 바뀌기 때문에,
45도가 넘어갈땐 90도로 연산을 처리 한 후, 그 나머지가 45도이면 45도 회전을 수행하면 된다.

소스

2784 가로 세로 퍼즐

주어진 6개의 단어로 3*3 가로세로퍼즐이 성립하도록 배치하는 문제이다.
알고리즘으로 생각하려면 매우 복잡해지지만, 퍼즐이 3*3밖에 안된다는 점을 이용해서
가능한 모든 케이스를 넣고, 이 케이스가 퍼즐이 성립하는지를 판단하면 된다.

정답이 복수인 경우는 사전순으로 출력해야 하므로 우선 정렬을 해주고,
3중 반복으로 각 라인에 단어를 넣은 후, 퍼즐이 성립하는지 보면 된다.

퍼즐이 성립하는지의 여부는 6개의 단어가 퍼즐의 가로, 세로에 모두 배치되어있는지를 보면 된다.

소스

5211 가단조와 다장조

주어진 음계가 가단조인가 다장조인가를 찾는 문제이다.
각 마디의 첫 음이 A,D,E로 시작하는게 많으면 가단조, C,F,G로 시작하는게 많으면 다장조 이다. 둘이 같으면 가장 마지막 음으로 구분한다.

strtok함수를 써서 |로 마디를 구분하여 첫음을 찾으면 된다.

소스

5692 팩토리얼 진법

각 자리의 수를 팩토리얼로 나타낸 수가 팩토리얼 진법이다. 이를 10진수로 나타냈을때의 수를 구하는 문제이다.

팩토리얼은 원래 엄청나게 큰 수가 되기 때문에 어려운 문제인 줄 알았으나, 다행히도 최대 5자리 밖에 입력이 주어지지 않는다. 따라서 10진수를 구할때 10씩 곱해주듯이, 팩토리얼도 마찬가지로 다음숫자를 곱해주면 된다.

소스

5623 수열의 합

수열에서 두 수를 뽑아 그 합으로 만든 행렬으로 원래의 수열을 판별하는 문제이다.

이 문제를 푸는 방법은 행렬 각각의 숫자의 합,차를 이용하는것인데,
예를들면
A[2] = S(0,2) + S(1,2) - S(0,1)
A[3] = S(0,3) + S(1,3) + S(2,3) - S(0,1) - A[2]
이런 방법으로 A[2]를 구하면 다음 수를 밝혀낼 수 있다.
문제는 A[0]과 A[1]인데,
이것은 A[2] 를 구해내면 A[0]= S(0,2) - A[2] , A[1]= S(1,2) - A[2] 의 방법으로 구할 수 있다. 이 방법을 통해 A[0],A[1]의 값을 측정해낸 후,
A[3] = S(0,3) - A[0]
A[4] = S(0,4) - A[0]
이렇게 A[0]만 가지고도 값을 구할수도 있다.
생각 여하에 따라 시간차이가 많이 나는 문제이다.

소스