10986. 나머지 합

문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 이해 구간의 합을 구해야하는 문제이므로 누적 합 알고리즘을 활용한다. N의 범위가 100,000이므로 O(N)만큼 활용할 수 있고, 탐색을 통해 선택해야 하므로 이분 탐색이나 투포인터를 활용해야한다. 배열 값의 범위가 1,000,000,000이므로 이를 매번 다루면 연산 시간으로 인해 시간 초과가 염려되니, M으로 나눈 나머지 값을 가지고 활용..

• format_list_bulleted Algorithm/BaekJoon Review
• · 2024. 4. 2.
• textsms

11286. 절댓값 힙

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 이해 우선순위 큐를 이용하여 풀 수 있는 문제 파이썬 내장함수인 Heapq를 사용하면 간단하게 풀 수 있지만, 직접 구현해봄 구현 내장함수 사용 import heapq 를 사용하여 절댓값과 실값을 같이 저장하여 비교하여 사용 직접 구현 class를 통해 실 값을 저장하면 절댓값을 기준으로 비교하여 트리를 구성 코드 # 11286 절댓값 힙 import sys input = s..

• format_list_bulleted Algorithm/BaekJoon Review
• · 2024. 3. 12.
• textsms

1149. RGB거리

https://www.acmicpc.net/problem/1149 이해 완전 탐색을 통해 해결할 수 있지만, 완전 탐색시 O(3000^3)으로 시간 초과 동적 계획법을 통해 빨강, 초록, 파랑으로 칠하는 경우 중 비용이 가장 작은 경우만 저장하는 배열을 통해 해결 구현 빨강, 초록, 파랑으로 칠할 경우 드는 비용을 저장할 dp배열 생성 N개의 집을 칠하기에 빨강, 초록, 파랑 각각 칠해온 비용을 저장할 N*3배열 생성 dp 배열은 최대의 경우를 가정했을 때 나오는 수보다 1큰 수로 저장 dp = [[1000 * 1000+1] * 3 for _ in range(N)] dp배열의 첫번째 줄은 첫 집을 빨강, 초록, 파랑을 칠할 경우의 비용으로 채움 for i in range(3): dp[0][i] = cos..

• format_list_bulleted Algorithm/BaekJoon Review
• · 2024. 1. 15.
• textsms

15684. 사다리 조작

https://www.acmicpc.net/problem/15684 이해 사다리를 모두 놓아보면서 판별해야하는 문제 DFS 를 통해 완전 탐색을 하되, 중간 가지치기를 이용한 시간을 단축해야함 구현 사다리 타기를 통해 i → i 가 모두 가능한 지 체크 하는 함수 DFS를 통해 사다리를 놓는 경로를 모두 탐색해야하는 함수 사다리 조작에 있어 사다리를 추가할 때, 추가한 사다리가 3개가 초과되면 가지치기 만약 이전에 확인된 사다리의 조작한 사다리 수가 현재 돌고 있는 사다리의 조작한 사다리 수 보다 높은 경우 가지치기 사다리를 놓음에 있어 만약 2개 혹은 3개째 사다리를 놓을 때는 이전에 놓았던 사다리 위치보다 위에 놓을 필요가 없음 코드 # 15684 사다리 조작 import sys input = sys..

• format_list_bulleted Algorithm/BaekJoon Review
• · 2024. 1. 12.
• textsms

1932. 정수 삼각형

https://www.acmicpc.net/problem/1932 이해 완전 탐색을 통해 모든 경우의 수를 확인하는 방식을 사용할 수 있지만, 삼각형의 크기가 1~500 이기 때문에 완전 탐색을 할 경우 시간 초과가 날 수 있다.(2^500가지 경우의 수) 따라서 동적 계획법이용하여 시간을 줄여야 한다. 구현 동적 계획법(DP, Dynamic Programing 이하 DP)을 사용하되, 기본적인 풀이 방식이 아닌 입력을 받은 후, 입력받은 배열을 변경하는 식으로 구현 문제에 있는 크기 5의 정수 삼각형을 예시로 들어보자 i/j j=0 j=1 j=2 j=3 j=4 i=0 7 0 0 0 0 i=1 3 8 0 0 0 i=2 8 1 0 0 0 i=3 2 7 4 4 0 i=4 4 5 2 6 5 i=0일 때는 Pa..

• format_list_bulleted Algorithm/BaekJoon Review
• · 2024. 1. 11.
• textsms

18111. 마인크래프트

https://www.acmicpc.net/problem/18111 이해 평탄화가 가능한 높이에 대해 모든 경우의 수를 비교해가며 풀어야하는 문제이다. 문제를 읽어보면 알 수 있 듯, 높이에 대한 인덱스가 중요하지 않아 2차원 배열이 아닌 1차원 배열로 입력을 받아도 되고, Dictionary 형태로 받아도 된다. 구현 N*M 행렬을 높이에 대한 Dictionary로 정의 collections 내부 defaultdict를 활용 높이에 대해 쌓을 블럭 수와 부술 블럭 수를 따로 저장하여 계산 식으로 풀이 만들 수 있는가? 👉 (부술 블럭 수) + (최초 인벤토리 블럭 수) >= (쌓는 블럭 수) 걸리는 시간 👉 (부술 블럭 수) + 2 * (쌓는 블럭 수) 걸리는 최소 시간 저장 및 최소 시간 중복 시 최..

• format_list_bulleted Algorithm/BaekJoon Review
• · 2024. 1. 9.
• textsms