나의 흐름대로 천천히, 그리고 꾸준히 나아가자

난이도: G2알고리즘: DFS https://www.acmicpc.net/problem/19238 1. 문제 탐색 제한 시간: 1초, 메모리 제한: 512MB 길찾기 문제이므로 BFS나 DFS를 사용한다. 길찾기가 사용되는 경우 2가지: 택시가 승객을 태우러 갈 때, 택시가 승객을 태우고 목적지로 갈 때 태우러 갈 승객을 정하는 것에 규칙이 있다. - 최단거리인 승객, 거리가 같다면 행 번호 작은 승객, 행 번호도 같으면 열 번호가 작은 승객 -> 정렬 필요 - 자동 정렬 자료 구조 사용 - 구조체: {최단거리, 행 번호, 열 번호} 2. 코드 설계하기길찾기 함수를 따로 선언 최종적으로 남은 연료 출력, 중간에 연료가 떨어지면 -1 출력 3. 시도회차별 수정 사항   4. 정답코드작성중

난이도: G3알고리즘: BFS https://www.acmicpc.net/problem/2683 1. 문제 탐색 제한 시간: 1초, 메모리 제한: 128MB 격자가 나오고 연쇄적으로 일어나는 상황이므로 BFS를 이용한다. 2. 코드 설계하기- BFS를 구현하기 위해 치즈 위치가 들어가는 큐를 선언한다.- 치즈 내부 공간과 외부 공간을 구분하는 것이 중요하다.그리고 치즈가 녹아서 없어졌을 때, 그 영향에 의해 내부 공간->외부 공간이 되는 위치들을 알아내는 것이 중요하다.-> 따로 함수를 작성- 녹아 없어질 치즈를 따로 자료구조에 보관한 뒤에 한 번에 외부 공간으로 바꿔야한다. 치즈 상태를 하나씩 바꾸고, 다음 녹을 치즈를 판단하게 되면, 앞서 치즈 상태를 바꾼 것에 영향을 받아 제대로 상태 변화가 이루어..

난이도: G4알고리즘: 구현 https://www.acmicpc.net/problem/14499 1. 문제 탐색 제한 시간: 2초, 메모리 제한: 512MB N,M으로 2차원 배열을 만들어야하는데, 각각 범위가 최대 20이므로 제한 시간과 메모리 제한에 크게 걸릴 것 같지 않았다.구현으로 풀자. 2. 코드 설계하기문제를 분해해서 함수로 만들었다. 하나의 함수에 몰아넣기에는 복잡해보였기 때문이다.그리고 조건들이 꽤 있기 때문에 잘 따져주어야한다. 일단 주사위의 각 면의 숫자를 나타낼 배열(dice)을 만들었다. {상, 하, 서, 남, 동, 북} 이렇게 각 방향에 쓰여있는 숫자를 나타내는 배열이다.rollDice함수로 명령에 따라 각 면이 어떻게 바뀔지 다 작성한다. 동/서/남/북으로 굴렸을 때 각 면이 어..

난이도: G1알고리즘: 이분탐색 https://www.acmicpc.net/problem/1561 1. 문제 탐색 제한 시간: 2초, 메모리 제한: 128MB N의 범위가 최대 2억, M의 범위가 최대 10000이므로 O(N)은 시간 초과가 발생한다.이분 탐색으로 풀어서 시간을 단축하자.그리고, 놀이기구 순서보다는 X초에 몇 명이 놀이기구를 타는지 시간 중심으로 생각해보자. 2. 코드 설계하기0초에는 빈 놀이기구에 모두 탑승한다. -> 0초: m명 그리고 x초에는 x/m[i]의 합 만큼 탑승한다. n명의 아이들이 모두 탑승하는 x분를 구해보자. - 이분탐색으로int low = 0(초), int high = n*30(초), int mid = (low+high)/2 target초에 탑승인원이 총 몇 명인지 ..

난이도: G3알고리즘: 이분탐색 https://www.acmicpc.net/problem/2473 1. 문제 탐색 제한 시간: 1초, 메모리 제한: 256MB N이 최대 5000 이므로 5000*연산이분탐색으로 풀어서 연산 횟수를 줄이자. 2. 코드 설계하기이분탐색을 하기 위해 용액의 특성값을 먼저 오름차순으로 정렬한다.배열을 하나씩 돌면서 v[i]를 기준 용액으로 정하고 v[i+1]~v[n-1] 용액 중에 2개를 고르는 방식으로 진행한다.특성값의 합이 0에 가까워야한다는 조건이 있기 때문에 특성값의 총합 뿐만 아니라 절대값으로 판단하는 과정도 들어가야한다. 3. 시도회차별 수정 사항 거의 모든 변수를 long long으로 해놓고 코드를 작성해야한다.int변수로 설정하고 이후에 long long으로 자료..

난이도: G4알고리즘: 이분탐색 https://www.acmicpc.net/problem/1477 1. 문제 탐색 제한 시간: 2초, 메모리 제한: 256MB 문제에 주어진 휴게소 정보를 이용하여 구간 마다 {휴게소 간 거리, 구간 시작점, 구간 끝점} 이렇게 구조체를 만들고 이것을 우선순위큐에 넣어 거리가 큰 게 먼저오도록 정렬하여 m번마다 pop하고 하나의 구조체를 거리/2하여 두 개로 나누어2개의 구조체를 다시 push하는 구조로 생각하였다. 이게 문제가 있었다. 같은 지점에는 휴게소를 하나씩만 세울 수 있어서 중복체크를 해야한다는 것인데 이렇게 되면, 하나의 휴게소를 기준으로 옆으로 한 칸씩 휴게소를 세울 수 있는지 체크해야하는 로직이 필요했다. 너무 쓸데없이 복잡해진다는 생각이 들었고, 그냥 휴..

난이도: P5알고리즘: dp https://www.acmicpc.net/problem/8895 1. 문제 탐색 제한 시간: 1초, 메모리 제한: 256MB 완전탐색으로 풀기엔 시간이 너무 많이 걸릴 것 같았다. 1~n 길이의 n개 막대를 배치하려면 n!의 경우의 수가 발생하고 개수를 셀 때에도 추가적으로 필요하기 때문이다. dp로 이전 것을 활용해서 풀어야 시간이 절약된다고 생각했다. n개의 막대를 배치할 때 1~n-1길이의 막대를 배치하고 n길이의 막대를 위치시키려고 생각했으나 너무 복잡해서 해결할 방법이 생각이 나지 않았다. 해설지를 참고하니, 2~n길이의 막대를 배치하고 길이가 1인 막대를 위치시키는 게 더 문제가 단순해진다고 했다.   2. 코드 설계하기 dp[n][l][r] : n개의 막대가 있..

난이도: G3알고리즘: dp https://www.acmicpc.net/problem/2342 1. 문제 탐색 제한 시간: 2초, 메모리 제한: 128MB 완전탐색으로 풀기엔 시간이 너무 많이 걸릴 것 같았다. 하나의 지시사항에 왼발을 움직일지, 오른발을 움직일지 다 따지면 지시사항이 최대 100000개이기 때문에 2^100000 = 10^15정도?로 시간 초과할 것 같았다. dp로 이전 것을 활용해서 풀어야 시간이 절약된다. 2. 코드 설계하기 dp[i][j][r]라고 하고, 이것을 i번째 발판을 밟았을 때, 왼발이 l에 있고 오른발이 r에 있는 경우의 힘이라고 하자. 발이 target위치에 있을 때는 왼발이 target에 있거나, 오른발이 target에 있는 경우이다.왼쪽이나 오른쪽 발이 target..

난이도: G1알고리즘: dp https://www.acmicpc.net/problem/1562 1. 문제 탐색 제한 시간: 2초, 메모리 제한: 128MB 완전탐색으로 풀기엔 시간이 너무 많이 걸릴 것 같았다. 한 자리당 0~9까지 넣을 수 있고, 총 100자리까지 가능하기 때문에 10^100이나 걸리기 때문이다. dp로 이전 것을 활용해서 풀어야 시간이 절약된다.  2. 코드 설계하기 dp[i][j]라고 하고, 이것을 길이가 i이고 끝자리가 j인 계단수라고 한다면i-1 길이의 계단수의 끝자리에 따라 3가지 경우가 있다.1. i-1 길이의 계단수의 끝자리가 0인 경우: i 길이의 계단수의 끝자리는 1만 가능하다.2. i-1 길이의 계단수의 끝자리가 9인 경우: i 길이의 계단수의 끝자리는 8만 가능하다...

난이도: G4알고리즘: dp https://www.acmicpc.net/problem/10422 1. 문제 탐색 제한 시간: 2초, 메모리 제한: 256MB테스트케이스 개수: 1-> T*연산횟수 연산횟수는 2*10^7 이하 - 연산횟수는 충분히 크다.  - 올바른 괄호의 조건: () -> 올바른 괄호끼리 붙여도 되고, 올바른 괄호 안에 올바른 괄호를 넣어도 된다. 일단 L=1인 경우부터 나열해보자.L=1: 불가능L=2: () -> 1가지L=3: 불가능L=4: ()(), (()) -> 2가지L=5: 불가능L=6: ()()(), ()(()), (())(), (()()), ((())) -> 5가지즉, L은 짝수여야한다. 그리고 이전의 것들을 붙여서 사용하거나, 괄호에 넣어서 사용하기 때문에 dp로 풀어야하는 ..