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을 출력하면 된다.

소스