본문 바로가기

Algorithm/etc111

[파이썬] 백준 12738 : 가장 긴 증가하는 부분 수열3 (골드2) [파이썬] 백준 12738 : 가장 긴 증가하는 부분 수열3 (골드2)https://www.acmicpc.net/problem/12738풀이방향성 생각배열 크기가 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.
[파이썬] 백준 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 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.
[자바] SWEA 2117 : 홈 방범 서비스 (test) [자바] SWEA 2117 : 홈 방범 서비스 (test)SWEA 2117 : 홈 방범 서비스풀이방향성 생각완탐마름모 모양은 맨해튼 거리의 abs에 제한되는 경우이다. 전체코드import java.io.*;import java.util.*;public class Solution { static int N,M; static int[][] arr; public static boolean inside(int x, int y) { return 0 = cost) { answer = Math.max(answer, cnt); } } } .. 2025. 4. 5.

티스토리툴바