우당탕탕 코딩일기

기억할 것dp는 미래 일 (i+1)과 같은 건 생각하지 않고 현재에 집중해서 풀어야 한다.  문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.출력첫째 줄에 답을 출력한다.예제 입력 1 1010 -4 3 1 5 6 -35 12 21..

기억할 것dp는 현재 시점에서 (i에서) 미래 일(i+@)는 생각하지 않고 풀어야 한다. 문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와..

기억할 것1. 매번 전체 배열을 탐색하지 말고 탐색할 좌표를 저장한 후, 그 좌표에 대해서만 탐색할 것(ex. 여기서는 바다 전체를 들쑤시고 다니지 말고, 딱 빙산이 있는 좌표에 대해서만 탐색 ㄱㄱ) 2. BFS는 재귀 안씀 . deque 써야함. deque가 리스트보다 빠를 때 많음DFS가 재귀를 씀 문제지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.        2453   3 252  7624         그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에..

기억할 것1. 두 포인터 유형의 문제2. 이런 문제는 start와 end 변수를 만들어 index로 조작할 것 (객프시간에 비슷한거 했던거같은데..)3. 목푯값이 더 크면 start 인덱스를 늘리고, 목푯값이 작으면 end 인덱스를 줄여야함. 내가 쓴 코드#include #include #include using namespace std;int main() { int n, m; vector v; cin >> n; for (int i = 0; i > num; v.push_back(num); } cin >> m; sort(v.begin(), v.end()); int cnt = 0; int start = 0; int end = n-1; while (true) { if (start >= end) { b..

기억할 것 1. dp란 반복적으로 사용된 부분을 dp 배열에 저장하여 런타임을 줄이려는 알고리즘이다. 2. dp는 dp배열을 사용하여 기록한다. 이 문제에서 dp 배열이란, 각 위치까지 도달하는데 필요한 최소 점프 횟수를 저장하는 배열을 말한다. 3. 변수가 2개이다 = for문을 2번 사용한다 이 문제에서는 기준 변수를 i, 목표 변수를 j로 잡음 => 중첩된 반복문에서 j는 현재 위치 i 이전의 위치를 나타낸다. j번째 위치에서 현재 위치 i로 도달할 수 있는 경우(즉, j + A[j] >= i), 최소 점프 횟수를 갱신한다. 문제 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, ..

기억할 점 1. 처음에 입력 다 받고 출력 좌르륵 하는 줄 알았는데 그게 아니고 입력 케이스 하나 받을 때마다 결과 하나 출력하는 식이다. 2. R이 짝수일 때 홀수일 때 구분해서 풀어야 한다. R 나올때마다 뒤집으면 시간초과난다.. R이 3번 나왔으면 오른쪽에서 지우고, 4번째 나왔을 때는 왼쪽에서 지우는 식으로 이해하면 될 것 같다. 3. 숫자열에 숫자가 없을 때, 지우는 건(D) error로 처리하지만 뒤집는 건(R) error로 처리하지 않는다. (중간에 이러한 경우가 생겨도 마찬가지.) 4. 내 경우는 아니었지만, 출력할 때 그냥 리스트로 출력하면 안되고 문자열 타입으로 출력해야 한다. 반례 예시) 3 R 0 [] >>> [] D 0 [] >>error RDRD 1 [12] >>>error 이거..

기억할 것 1. 그래프 문제 풀 땐 indexerror 조심해야 하는거 말곤 크게 없는 거 같다. 2. 한번에 최소 일수를 구하려 하지 말고, 각 토마토별로 익는 일수를 구한 후 max 값을 찾아야 한다. 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 ..

기억할 것 1. 스택 개념을 숙지했다고 해서 그것이 바로 적용되는 것은 아니다. 2. 그렇다면 스택을 어떻게 쓰는가? 스택을 안 써도 코드는 돌아가게 만들 수 있다. 알량하게 몇 문제 풀어보면서 느낀 거지만 스택, 큐, 덱을 안 쓰면 시간 초과가 난다. (물론 개념을 써도 추가적인 아이디어가 필요하여 시간초과가 나는 경우도 있긴 하지만 말이다..) 시도했지만 맞지 못한 문제에 한 몇달 묵히다가 알고리즘 공부한걸로 해결하니까 기분이 좋다. 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열..

기억할 것 1. 가중치를 부여하는 그리디 문제라는거..? 사실 그냥 골드4 처음 풀어봐서 기록한다.. 문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최..

기억할 것 1. 큐, 덱이라고 해서 무조건 import deque로 해결되진 않는다. (시간 초과가 나거나 ..등등) 2. 이럴 때 딕셔너리를 사용하는 것이 한가지 방법이 될 수 있다. 딕셔너리로 같은 key 값을 입력받았을때 value값이 변하는 것을 큐처럼 사용할 수 있다. 문제 국민대학교에서는 매 학기 시작 전 종합정보시스템에서 수강신청을 한다. 매 수강신청마다 아주 많은 학생들이 몰려 서버에 많은 부하가 가기 때문에, 국민대학교에서는 수강신청 부하 관리 시스템을 도입하기로 결정하였다. 새로운 관리 시스템은 다음과 같은 방식으로 동작한다. 수강신청 버튼이 활성화 된 후, 수강신청 버튼을 조금이라도 빨리 누른 학생이 대기목록에 먼저 들어간다. 이미 대기열에 들어가 있는 상태에서 다시 수강신청 버튼을 ..