우당탕탕 코딩일기

기억할 것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차원 배열에..

기억할 점브론즈 문제긴 한데 효율적으로 딕셔너리 value에 대해 sorting하는 법이 중요하여 포스팅하고자 한다. 1. box = sorted(box.items(), key=lambda x: x[1], reverse=True)  문제알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.입력첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다.출력첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다.예제 입력 1 복사Mississipi예제 출력 1 복사?..

문제0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.입력첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.출력첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.예제 입력 1 복사20 2예제 출력 1 복사21예제 입력 2 복사6 4예제 출력 2 복사84 내 풀이N, K = map(int, input().split()) # 6 4box = [[ 0 for j in range(K)] for i in range(N+1)]box[0] = [1 for i in range(K)]for j i..

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