성장 일기 - Small Step

https://www.acmicpc.net/problem/4948 풀이 에라토스테네스의 체를 이용하여 소수들을 모두 구한 후, n+1이상 2n이하의 소수의 개수를 출력하면 되는 문제. 에라토스테네스의 체는 간단히 설명하면 2를 제외한 2의 배수들을 전부 소수에서 제외, 3을 제외한 3의 배수들을 소수에서 제외 하는 방식으로 2부터 숫자를 증가하면서 소수를 구해나간다. 제출한 코드12345678910111213141516171819202122232425#include int arr[246913];int main() { arr[1] = arr[0] = 1; for (int i = 2; i

https://www.acmicpc.net/problem/1063 풀이입력된 명령어에 따라 킹과 돌을 움직여주면 되는 문제이다. 1. 입력된 킹과 돌의 위치를 8by8 맵에 대응시킨다.2. 입력된 명령들을 하나씩 실행해준다.ㄱ. 킹을 움직이기 전 킹의 다음 위치에 돌이 있거나 범위를 벗어나는지 판단한다. a. 범위를 벗어난 경우킹이 움직여야 될 다음 위치가 범위를 벗어나면 continue b. 돌이 있을 경우돌이 있으면 돌도 같은 방향으로 옮겨주어야 한다. 돌도 움직여 주기 전 돌의 다음 위치가 map의 범위인지 판단해준다. 범위를 벗어나면 continue, 범위 안에 있으면 돌을 움직여 준다.ㄴ. 돌을 움직인 후 킹을 움직인다.3. 명령을 다 수행 후 킹과 돌의 위치를 맵의 좌표에 맞게 1번의 반대 과..

https://www.acmicpc.net/problem/1932 풀이 우선 이 문제는 DP문제이다. 그냥 배열이 주어지고 특정 방향을 따라 최대 최소 경로의 수 를 구하는 문제들은 삘링이 그냥 DP같아서...별 생각없이 DP로 먼저 생각하게 된다. 이 정도 난이도의 DP문제는 다 비슷비슷한 거 같다. 최근에 풀었던 삼각 그래프나 기업투자와 유형과 접근이 비슷해 금방 풀었던 것 같다. 1. arr의 맨 아래 삼각형 밑 면까지 모든 경로를 탐색하며 내려간다.2. 밑 면에 도착하면 해당 밑면의 arr배열의 값을 return해준다.3. return된 값과 맨 밑면에 도달하기 전 위치의 arr값을 더해준 뒤 DP배열에 저장한다.4. 모든 밑면에 대하여 3번과 같은 단계를 거치며 return될 때마다 그 전에 D..

https://www.acmicpc.net/problem/4963 풀이 여행을 갔다 오느라..오랜만에 문제를 풀었다!!근데 이건...예전에 풀었던 '2667번단지번호붙이기'와 매우 흡사하여 금방 풀었다. map배열과 방문을 체크하는 visit배열을 선언 후이중 반복문으로 map배열을 다 체크해주며 map의 해당 값이 1이며 방문한 적이 없는 곳이면 이 곳을 기준으로 상하좌우 대각선을 탐색해준다. 더 이상 이어진 섬이 없으면 return 1을 해주어 이 1의 총 합을 출력해주기만 하면 된다. 제출 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include ..

https://algospot.com/judge/problem/read/PICNIC 풀이배열의 순서와 관련된??문제는 왜이렇게 어렵게 느껴지는지 모르겠다. 문제에서 두개의 쌍으로 묶어서 나오는 탐색 문제는 인접 배열로 풀어야 된다!!인접 배열은 두 값이 쌍으로 묶어질 때 두 값을 축으로하는 2차원 배열로 해당 배열의 위치를 표시해주는 것이다. 문제에서 다음과 같은 짝궁들의 배열이 주어지면0 1 1 2 2 3 3 0 0 2 1 3 //짝 입력for (int i = 0; i < m; i++){int a, b;scanf("%d %d", &a, &b);index[a][b] = index[b][a] = 1;}와 같이 배열에 서로가 관련이 있다고 표시해주는 것이다. 그후 탐색을 통해 짝인 경우의 수를 카운트 해주면..

https://algospot.com/judge/problem/read/BOGGLE 풀이책에서 풀라는데로 풀었는데...시간초과가 떠서...봤더니 당연히 시간 초과가 날 수 밖에 없다. 내가 계산한바에 따르면.. 단어의 최대 길이는10으로 가정하고 주어진 단어가 존재하지 않을경우맵을 전체 5*5를 다 뒤지며 8가지 경로로 10번 나아간다고 치면 25*8^9가되어 시간초과가 난다.(계산이 틀릴수도 있지만 시간초과가 나는 것은 확실하다.) 풀이는 처음에 main함수에서 주어진 배열 map의 시작점을 다 뒤지도록 이 중 포문을 돌리며재귀한수에 함수의 위치와 index값을 넘겨준다. 그리고 해당 index값과 map의 문자가 같지 않으면 return 0; 값으면 다음 인자를 찾기 위해 주위의 8방향을 탐색해준다...

https://www.acmicpc.net/problem/11052 풀이2662번 기업투자를 푸는데...왠지 붕어빵과 비슷한 느낌이나서 다시 풀어보았다. 기업투자는 조만간 올리겠다!! 붕어빵을 어떻게 묶어 팔아야 제일 비싸게 팔 수 있느냐를 구하는 문제이다...DP문제는 글로 설명하기가 어렵다. 붕어빵이 n개 있으면 다음과 같이 생각할 수 있다.1. 처음에는 0~n개 까지 붕어빵을 묶어 팔 수 있으며, 이때 i 개를 팔았다.2. 전에 묶어판 붕어빠의 개수가 i개이면 지금 팔 수있는 붕어빵의 개수는 0~n-i이다. 이 경우의 수에서 j개를 팔았다.3. 위의 1,2 경우에서 i+j개를 팔았으므로 지금 팔 수 있는 붕어빵의 개수는 0~n-i-a개이다. 이와 같은 방식으로 팔 수있는 경우의 수가 0개가 될 때 ..

https://www.acmicpc.net/problem/4883풀이 지금까지 경로의 수나 최소값을 구하는 DP들의 풀이와 재귀 함수의 형태가 대부분 비슷하다. 함수가 시작할 때 빠져나오는 조건과 마지막에 return 사이의 구성을 어떻게 해주냐만 해주면 되는데...이게 어려운 것 같다. 처음에는 N,2 지점까지가면 이 값을 max로 하여 이 값과 비교해가면서 모든 경로를 비교하면서 답을 구했다. 이랬더니...시간 초과가 나버렷다. 나름 DP라고해서 짠건데...ㅜ,ㅠ 생각이 안 나..친구의 설명을 듣고 다시 풀었다. 우선 N,2에 도달 후 return하면서 그 전에 DP배열에 저장된 값과 지금 return된 값중에 최소값으로 DP배열에 저장하면서 올라오는 방법인데...글로 설명하기가 어려다... 중요한건..

https://www.acmicpc.net/problem/2688풀이오랜만에 알고리즘을 다시 풀었다...최근에 피파에 빠져서......ㅜ,ㅠ이건 예전에 풀었던 오르막수와 90%동일한 문제이다. 다이나믹 프로그래밍이며 이차원 배열을 통해서 풀어야된다. 이 문제에서 다음에 올 수는 맨 마지막에 있는 숫자보다 큰 수들이다. 따라서 맨 뒤의 숫자들에 따라 다음에 올 경우의 수들이 달라진다. n=1일 경우0일 경우 0과 같거나 큰 0~9의 숫자들이 올 수 있으므로 경우의 수가 101일 경우 1과 같거나 큰 1~9의 숫자들이 올 수 있으므로 경우의 수가 9....9일 경우 9와 같거나 큰 수는 9 하나이므로 9뒤에 올 수 있는 경우의 수는 1이다. 따라서 n은 1일 경우 총 경우의수가 55이다. n=2일 경우는0뒤..

https://www.acmicpc.net/problem/1520 풀이예전에 푼 문제이나 오늘 내리막길과 완~~전 비슷한 점프를 풀어서 포스팅하는김에 같이 올린다. 이 문제는 내가 처음으로 DP라는 것을 알게 되었고 메모이제이션이라는 단어를 처음 들어본 문제이다. 단순한 탐색으로 풀면은 시간초과가난다. 좀 설명하기 어려운데...나름 자세히 설명을 하겠다. 1. 해당 y x 좌표에서 현재 위치에서 작은 값으로 진행을 하면서 나아간다.2. 이렇게 작은 수로 나아가다가 y==N,x== N 지점이 되면 return 1;을 한다.3. y==N, x==N가 return되면 리턴된 값을 DP배열에 저장하고 이 함수는 DP배열을 return한다.4. 이렇게 상하좌우로 갈라지는 지점에서 그 경로에서 N,N까지 가는 경로..