늘 겸손하게

DP 문제를 처음으로 스스로 풀었네요 문제 풀이 모든 경우를 다 구하려면 시간 초과가 나오므로 dynamic programming으로 풀어야 한다. 1. 합이 최대가 되는 경로에 있는 수의 합을 출력해야 하고, 위에서 아래로 내려갈 때 더 큰 숫자가 있는 방향으로 나아가야 하므로 두 개의 숫자를 비교한 후 더 값이 큰 숫자를 반환하는 함수를 만들어두자. 2. 삼각형의 맨 위에서 아래로 내려가는데, 더 큰 수가 있는 방향으로 내려가고 더 큰 수를 합하면서 맨 아래까지 내려가야 한다. -> 이 과정에서 지금까지 합한 값을 기록해야 하고 다음 값을 계산할 때 기록한 값을 사용한다. 3. edge case 주의 : 맨 오른쪽 정수는 바로 윗줄의 맨 오른쪽, 맨 왼쪽 정수는 바로 윗줄의 맨 왼쪽만 선택 가능하다...

큐를 이용하라고 했지만 일차 배열로도 충분히 풀 수 있는 문제이다. 문제 풀이 1. 길이가 n인 배열을 준비하고 1부터 n까지 저장한다 2. 선형으로 배열의 원소를 하나씩 참조한다. 3. 검색하면서 0이 아닌 원소가 있다면 counter값을 1 증가시킨다 4. counter값이 k와 동일해지면 해당 인덱스의 원소 값 출력, 해당 인덱스 값 0으로 변환 5. 배열에 0이 아닌 숫자가 더 이상 남아있지 않을때까지 반복한다 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #inclu..

좌표 압축 주어진 좌표의 크기 순위를 출력하면 되는 문제 문제 풀이 1. 좌표의 개수 n을 입력받고 길이가 n인 벡터 2개를 준비한다 2. 벡터 1개를 정렬한다 3. 정렬한 벡터의 중복 값을 모두 제거한다 4. 원본 벡터의 원소들을 선형으로 하나씩 참조하여 참조한 원소들이 정렬한 벡터에서는 몇 번째 인덱스에 위치하는지 찾아서 출력해준다 추가 설명 좌표값을 읽어 저장할때 벡터의 push_back 메소드를 이용하는 것보다는 벡터의 길이를 n으로 먼저 선언하고 인덱스 값을 참조하며 좌표를 저장하는 것이 더 빠르다. 벡터에서 중복값을 지울 때는 벡터의 erase와 unique 메소드를 이용한다. 원소 값을 벡터에서 찾을 때는 선형으로 찾지 말고 이진 탐색(binary search)같이 탐색 속도가 더 빠른 알고..

두 수의 합 투 포인터 기법으로 x 값에 해당하는 (ai , aj ) 쌍을 찾는 문제 문제 풀이 1. 서로 다른 n개의 자연수를 입력받아 배열에 저장한다. 2. 배열을 정렬시킨다. 3. 2개의 변수를 준비하여 한 개의 변수(lp)에는 배열의 첫 번째 인덱스 값을 저장하고 다른 한 개의 변수(rp)에는 배열의 마지막 인덱스값을 저장한다. 4. 정답 개수를 저장할 변수를 준비한다. ( ans ) 4. 배열[lp] + 배열[rp] 값이 x 값보다 작으면 lp++ 5. 배열[lp] + 배열[rp] 값이 x값보다 크면 rp-- 6. 배열[lp] + 배열[rp] 값이 x값과 동일하면 ans++ , rp--; 7. lp < rp일때 동안 반복 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..