본문 바로가기

Algorithm475

[파이썬] 백준 12015 : 가장 긴 증가하는 부분 수열2 (골드2) [파이썬] 백준 12015 : 가장 긴 증가하는 부분 수열2 (골드2)https://www.acmicpc.net/problem/12015풀이방향성 생각배열 크기가 10^6이라 N^2 DP풀이로는 불가능.LIS의 길이를 구하는 NlogN으로 풀이 전체코드import sysinput = sys.stdin.readlineN = int(input())LIS = []for val in map(int,input().split()): if not LIS or val > LIS[-1]: LIS.append(val) continue l,r = -1,len(LIS) while l+1코멘트bisect 쓰는 코드가 확실히 더 빠른듯.이분탐색에서는 항상 배열의 모든 구간을 탐색할 수 있.. 2025. 4. 10.
[파이썬] SWEA 4013 : 특이한 자석 (test) [파이썬] SWEA 4013 : 특이한 자석 (test)SWEA 4013 : 특이한 자석 풀이방향성 생각리스트 내부에 큐 넣어서 구현하기.인접 톱니끼리는 반대의 회전방향을 가진다.현재 톱니를 돌리고 옆 톱니를 돌리는 과정에서, 이전에 돌렸던 톱니를 다시 돌리지 않기 위해 방문처리한다.BFS로 이웃 톱니를 회전시키기 (톱니의 극성이 일치하면 반대방향으로 회전시켜주기)회전량은 V에 부호로 방향을, 값으로 회전수를 저장한다 전체코드from collections import dequeinside = lambda x : 0코멘트회전량이 많은 경우에는 모듈러 연산을 통해서 줄일 수 있다.자바에서는 음수 모듈러가 안돼서 후보정을 해줘야한다. 2025. 4. 10.
[자바] SWEA 5656 : 벽돌 깨기 (test) [자바] SWEA 5656 : 벽돌 깨기 (test)SWEA 5656 : 벽돌 깨기풀이방향성 생각맵 사이즈 작다 -> 완탐최적화가 필요하면 프루닝으로 좀 잘라내기제거하는 컬럼 선택 -> 중복순열 DFS로 구현터뜨리는 로직 -> BFS로 구현중력 구현 -> 순회하기기본적으로 배열을 수정해야하니, 배열을 copy해서 각 케이스다 copy array를 수정하기 전체코드import java.io.*;import java.util.*;public class Solution { static int N,H,W; static int[][] arr,temp; static int[] selects; static int[][] dires = {{1,0},{0,1},{-1,0},{0,-1}}; st.. 2025. 4. 10.
[파이썬] 백준 2613 : 숫자구슬 (골드2) [파이썬] 백준 2613 : 숫자구슬 (골드2)https://www.acmicpc.net/problem/2613풀이방향성 생각현재 배열에서 분할 횟수가 remain번 남았을 때, [s,e] 구간을 [s,m] [s,m+1]로 분할하기.배열 크기는 N^3이라 2700만이다.혹은 2차원으로 줄여서 풀이 가능.group을 g개로 분할했을 때, 인덱스 x까지 탐색했을때 그룹의 최대값을 dp에 저장역추적은 LCS에서 역추적하는 것 처럼 추적해주기.최소값을 갱신할 때, 이전 인덱스 변화를 저장해주기. 파이썬N,M = map(int,input().split())arr = list(map(int,input().split()))INF = float('inf')cumsum = [0]for a in arr: cumsum.. 2025. 4. 10.

티스토리툴바