꾸준함의 기록

최대공약수 뺴기 누적합 문제 해결 1. 왼쪽부터 차례로 누적 최대공약수를 구합니다. 2. 오른쪽부터 차례로 누적 최대공약수를 구합니다. [8, 12, 24, 36, 48] 예를 들어 index 0의 8이 빠지면 right_prefix_list[1]이 최대 공약수 입니다. index 1이 빠지면 left_prefix_list[1 - 1]과 right_prefix_list[1 + 1]의 최대 공약수가 전체의 최대 공약수입니다. 이 아이디어를 바탕으로 문제를 해결할 수 있습니다. 문제 오류 12는 빠진 수 8의 약수가 아니기 때문에 정답이 될 수 있다. -> 12는 8로 나누어 떨어지지 않기 때문에 정답이 될 수 있다. 예외 케이스 24는 8의 약수가 아니지만, 이것이 반례가 됩니다. 88%에서 막힌 이유 정..

버블 정렬은 맨 왼쪽 원소부터 바로 이웃한 원소와 비교하면서 정렬하는 것이고, 삽입 정렬은 이미 정렬된 부분과 정렬할 부분을 나눠 정렬하는 것입니다. 알고리즘의 핵심인 정렬 중 버블 정렬과 삽입 정렬에 대해 알아보겠습니다. 1. 버블 정렬 개념 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환하는 정렬입니다. 맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해 반복합니다. 예시) 5 3 1 4 2를 오름차순으로 정렬 특징 정확성을 보이기 제일 쉽습니다. 시간복잡도 처음 가장 큰 원소를 구할 때 n-1 번을 비교하고, 두번째 큰 원소를 비교할 때 n-2를 비교합니다. 이런식으로 (n-1) + (n-2) + ... + 2 + 1 = ..

토스 2022 next - 2022-08-06 1차시험 4/7솔 2차 시험 -> 프로젝트를 해야 풀 수 있을듯 (캐시 등) 부족한 점 1. 시간복잡도때문에 제대로 문제를 고민해보지않고 이분탐색이라고 판단하고 풀지 않음. for문 3개로 단순히 풀어 제출하면 되는 문제였음. 피드백: 지금까지의 공부:과정에 큰 문제는 없으나, 문제를 판단하는 부분에 있어 실수를 범함. 값의 범위가 컸지만, 각 경우가 3개씩밖에 없어서 많은 계산이 필요한 문제가 아니었음. 수정: 정확성으로 일단 풀 수 있음 풀자 2. "3으로 또는 2로 자를 수 있다." 등을 수학적으로 풀어내지 못했다. 3으로 나누고 나머지로 판단할 수 있었음. 피드백: 지금까지의 공부: 수학관련 문제는 자주 출제되는 유형이 아니므로, 수학적인 감각을 키우..

투포인터 증명하기 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투포인터에서 정답을 찾기 위해 봐야하는 모든 케이스는 아래와 같다. 하지만 사실 부분합을 찾기 위해 모든 케이스를 탐색하지 않아도 된다. 검은색 부분은 볼 필요 없다. 투포인터는 봐야할 위치에 의미를 부여해 볼 필요없는 위치를 제외하고, 봐야하는 위치만 볼 수 있게 한다. 왜 안봐도되는지는 아래에 설명한다. 빨간 색 구간은 찾아야하는 값 15를 초과할 것이 당연히 ..

백준 드래콘 커브 풀이 파이썬 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 풀이 아이디어 예를 들어 4 2 1 3 이라고 해보자 (설명은 x, y를 바꿔서 한다. 기존의 그래프 탐색처럼! 헷갈리니까) 2세대 까지 하면 아래와 같이 된다. arr = [[2, 4], [1,4], [1,3]] - 기존세대 1세대 arr2 = [[2, 4], [1,4], [1,3], [2,3], [2,2]] - 추가된 세대 2세대 이제 ..

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 코드 # 빗물 import sys si = sys.stdin.readline answer = 0 N, M = map(int, si().split()) height_list = list(map(int, si().split())) # 3 1 2 3 4 1 1 2 graph = [[0 for _ in range(M)] for __ in range(N)] # 벽 초기화 for i in ..

문제 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 2 4 1 3 5 6 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (x, y) 이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다. 지도의 각 칸에는 정수가 하나씩 쓰여져 있다. 주사위를 굴렸을 때, 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다. 0이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며,..

문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 예를 들어, 아래와 같은 지..

목차 동적 계획법 개념 일반적인 피보나치 구현 메모제이션 bottom-up 구현 top-down 구현 1. 동적 계획법 개념 큰 문제를 작은 문제로 나누어서 푸는 방법 * 반대 개념: 결정적 프로그래밍 (BFS, DFS 등이 결정적 프로그래밍 방식임) * DP를 사용하는 경우 큰 문제를 작은 문제로 나눌 수 있는 경우 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일한 경우 2. 일반적인 피보나치 재귀 구현 재귀의 경우 같은 로직을 여러번 반복하기 때문에 비효율적인 계산이 될 확률이 높다. 재귀를 활용한 피보나치 구현코드 # 1로 만들기 def fibo(n): if n

문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일TiPi 3 5 1 1 2 4 2 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다. 상담을 ..