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

13549. 숨바꼭질 3

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이해 완전 탐색을 통해 구현할 수 있지만, 이동에 있어 비용이 다르기 때문에 우선순위 큐를 활용한 다익스트라가 더 유리 비교를 위해 두 방식 모두 풀이했습니다. 구현 BFS 방문했을 때 최소값을 알기 위한 visited 배열 선언(초기화 값은 최댓값인 100,001) N부터 너비우선 탐색을 통해 탐색 방문 시 이전 방식보다 가중치가 작다면 최솟값을 변경하면서 ..

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

12851. 숨바꼭질 2

https://www.acmicpc.net/problem/12851 이해 N에서 K까지 가는 길을 완전탐색을 통해 해결 완전 탐색을 하면서 최소가 되는 시점에만 값을 변경, 이후 같은 값이 나오면 카운트 ++ 구현 방문 확인용 배열 및 후보 과정을 담을 배열 생성 만약 N == K인 경우 최솟값을 저장하고 다음 과정을 수행 만약 N != K인 경우 다음 경로로 갈 수 있는 곳을 탐색하여 후보 과정 배열에 추가 코드 # 46944KB380ms # 12851 숨바꼭질 2 import sys from collections import deque input = sys.stdin.readline def solution(): N, K = map(int, input().split()) que = deque([(0, ..

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

1697. 숨바꼭질

https://www.acmicpc.net/problem/1697 이해 N에서 K까지 가는 길을 완전탐색을 통해 해결 다익스트라를 통해 해결도 가능할 것 같아 풀어봄 방문 확인용 배열에 최솟값을 저장해 가지치기를 할 수 있음 N == K 인 경우, 조건문을 통해 배열에 넣고, 빼는 시간을 줄임 구현 방문 확인용 배열 및 후보 과정을 담을 배열 생성 만약 N == K인 경우 최솟값을 저장하고 다음 과정을 수행 만약 N != K인 경우 다음 경로로 갈 수 있는 곳을 탐색하여 후보 과정 배열에 추가 코드 너비우선탐색 # 35388KB140ms import sys from collections import deque N, K = map(int, sys.stdin.readline().strip().split())..

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

9935. 문자열 폭발

https://www.acmicpc.net/problem/9935 이해 문자열을 완전 탐색을 통해 더했다가 뺐다가 할 수 있지만, 최대 길이가 1,000,000 이므로 뺄때, 붙일 때 길이만큼 탐색하고, 제거/더해줌 반복되므로 시간 초과가 날 수 있음 Stack 구조의 append/pop 연산을 통해 중복되는 반복을 제거하고, 최대 폭발 문자열의 길이만큼만 반복하게 하여 시간을 줄일 수 있음 구현 Stack으로 이용할 리스트 생성 Stack에 문자열 하나씩 저장하며, 길이가 폭발 문자열 길이 보다 길어졌을 때부터 폭발 문자열이 stack 내부에 있는지 확인 → 마지막 길이만큼만 확인하면 모두를 확인할 수 있음 만약 폭발 문자열이 있다면 pop 연산을 통해 제거 없다면 계속해서 append 연산을 통해 S..

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