자료구조&알고리즘/백준

https://www.acmicpc.net/problem/1655 매번 정렬은 너무 느리다“새로운 수가 들어올 때마다 지금까지의 리스트를 정렬한 후 중간값을 꺼내자”→ 한 번 정렬에 O(N log N), 전체 N번이면 O(N² log N)… N=10만에 절대 안 된다.중간값만 빠르게 뽑을 수는 없을까?우리가 필요한 건 전체를 정렬된 상태로 유지할 필요 없이 “지금 중간값이 뭐냐?”만 알면 된다.삽입과 중간값 조회를 모두 O(log N) 안에 해결할 수 있는 자료구조를 찾아보자.한쪽 힙만으로는 부족하다최소 힙(min-heap)이나 최대 힙(max-heap) 하나만 있으면,삽입은 O(log N) OK그러나 중간값(“k번째 원소”) 조회는 지원하지 않는다.작은 절반 vs 큰 절반, 두 개의 힙!작은 절반은 ..

https://www.acmicpc.net/problem/2461 구간 내 모든반이 한명이상 포함되는 조건에서,능력치 최대-최소 차이를 구한다. 슬라이딩 윈도우의 정석같은 문제. 조건을 만족하는 연속된 구간중 최소 or 최댓값을 구하는문제. 풀이left와 right 두 포인터로 구간을 설정한다.이 구간(left ~ right) 안에 모든 반이 최소 한 명씩 포함되어 있다면, → left를 오른쪽으로 이동시키며 구간을 좁혀가고,그때마다 능력치의 차이(최댓값 - 최솟값)를 계산해 최솟값을 갱신한다.반대로, 모든 반이 포함되지 않았다면 → right를 오른쪽으로 이동시켜 구간을 확장한다.import sysfrom collections import defaultdictinput = sys.stdin.readli..

✔ 문제 8320 직사각형을 만드는 방법 문제 바로가기 💨 8320번: 직사각형을 만드는 방법 상근이는 변의 길이가 1인 정사각형 n개를 가지고 있다. 이 정사각형을 이용해서 만들 수 있는 직사각형의 개수는 총 몇 개일까? 두 직사각형 A와 B가 있을 때, A를 이동, 회전시켜서 B를 만들 수 www.acmicpc.net 핵심 아이디어 PYTHON # 방법1. 가로 세로 탐색 N = int(input()) ans = 0 for i in range(1, N + 1): for j in range(i, N + 1): if i*j

✔ 문제 10163 색종이 문제 바로가기 💨 10163번: 색종이 평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓여진다. 이때 색종이가 비스듬하게 놓이는 경우는 없다. 즉, 모든 색종이의 변은 서로 평행하거나, 서로 수직이거나 둘 www.acmicpc.net 핵심 아이디어 먼저 색종이 번호를 해당하는 색종이 영역에 표시한다. 그리고 count를 이용해 빈도수를 세어준다. 이때 풀이시간을 단축하고 코드를 최적화해보자.먼저 빈도수 체크를 할때 처음에는 for 각 번호들에 대해, 전체 배열에서 각 번호수를 count했다.하지만 빈도수 체크 배열을 만들면 전체 배열 탐색을 한번만 탐색해도 된다. 또한,배열 초기화를 for j (sj, sj + w) : arr[i][j] = [n] * w..

✔ 문제 15649 N과 M(1) 문제 바로가기 💨 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 핵심 아이디어 백트래킹을 사용하여 N개의 자연수 중에서 M개를 고르는 모든 경우의 수를 출력해야 한다. 백트래킹은 가능한 모든 해를 탐색하는 알고리즘 중 하나로, DFS(깊이 우선 탐색)를 기반으로 한다. dfs 함수는 현재 선택한 숫자의 개수를 나타내는 n과 현재까지 선택된 숫자들의 리스트 lst를 인자로 받는다. 종료조건을 먼저보자. n이 M과 같아지면, 즉, M개의 숫자조합을 모두 선택했을 때는 lst를 ..

✔ 문제 2501 약수 구하기 문제 바로가기 💨 2501번: 약수 구하기 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. www.acmicpc.net PYTHON n, k = map(int, input().split()) div = [] for i in range(1, int(n**(1/2)) + 1): if n % i == 0: div.append(i) if i != n // i: # 중복을 피하기 위함 div.append(n // i) sorted_div = sorted(div) if k

✔ 문제 2567 색종이-2 문제 바로가기 💨 2567번: 색종이 - 2 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 핵심 아이디어 먼저 2차원배열에 1로 색종이를 표시한다. 둘레 탐색은 두가지 방법이 있다. 1. 전체순회를 하며, 1을 만나면 해당 위치를 기준으로 4방향을 탐색해 0의 개수를 센다. 2. 함수를 가로,세로 방향으로 쭉 탐색하며 0>1,1>0 이 바뀌는 경계개수를 센다. 풀이에선 두번째 방법을 이용했다. +) 파이썬에서 전치를 할때는 zip(*list)를 이용했다. 예를들어, [ [1, 2, 3], [4, 5, 6], ..

✔ 문제 2563 색종이 문제 바로가기 💨 핵심 아이디어 2차원 배열로 저장 및 처리한다.시작점 좌표를 기준으로 해당 사각형크기만큼 배열에 1을 표시한다. PYTHON N = int(input()) arr = [[0]*102 for _ in range(102)] for _ in range(N): # [1] 해당 영역을 1로 표시 sj, si = map(int, input().split()) for i in range(si,si + 10): for j in range(sj, sj + 10): arr[i][j] = 1 # [2] 1의 개수를 cnt => 넓이 ans = 0 for lst in arr: ans += sum(lst) print(ans) JAVA import java.io.*; import jav..

✔ 문제 2798 블랙잭 문제 바로가기 💨 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 핵심 아이디어 브루트 포스로 완전탐색한다. ans = 0 으로 초기값을 두고, 모든 경우의 수를 탐색하며 ans보다 크고 범위내 숫자라면 갱신한다. PYTHON N, M = map(int, input().split()) lst = list(map(int, input().split())) ans = 0 for i in range(N-2): for j in range(i+1, N-1): fo..

✔ 문제 1463 1로 만들기 문제 바로가기 💨 핵심 아이디어 꽤나 헤맸던 문제이다... dp 너무 어렵다 ㅠㅠ정복하겠어!!! 일단 주어진 숫자의 최소 연산값을 구할때, 이전숫자는 -1,//2,//3중하나이다. 이때, 만약 주어진 N이 6이라 가정해보자. 그럼 6 이전의 계산값은 5,3,2 중하나일 것이다. 그러면 5,3,2중의 최소연산값중 가장 작은 최소연산값에 + 1을하면, 6의 최소연산값이 된다. 문제는 이러한 아이디어에서 착안한다. N까지의 숫자의 최소연산값을 구한다.배열 인덱스를 두고, 이전 연산을 바탕으로 -1을했을때,//2 했을때, //3 했을때의 최소연산값을 계속 구해 나간다. PYTHON N = int(input()) dp = [0] * (N+1) # dp[1]=0 초기값 설정 for i..