본문 바로가기

코테 (안함)43

이진탐색LIS ( 최장 증가 부분 수열 ) 알고리즘 파헤치기 # 백준 12015번 from bisect import bisect_left n = int(input()) arr = list(map(int,input().split())) x = [arr[0]] d = [1] * n for i in range(1,n): if x[-1] < arr[i]: x.append(arr[i]) d.append(d[-1]+1) else: idx = bisect_left(x,arr[i]) x[idx] = arr[i] print(max(d)) 위에는 백준 12015번 문제의 답이다. 전형적인 이진탐색LIS 예제이기에 올려본다. 기존에 2중 for문으로 구현한 LIS와는 달리 for문을 한번만 사용하여 계산속도를 올려주는 방식이다. 이진탐색은 for문을 하나로 없에준다. 방식은 dp를 .. 2022. 11. 25.
백준 2491번 - 수열 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int,input().split())) d1,d2 = [1]* n, [1]*n for i in range(1,n): if arr[i] = arr[i-1]: d2[i] = max(d2[i],d2[i-1]+1) print(max(max(d1),max(d2))) # 연속된 상황이 끊기면 다시 1부터 카운트를 시작한다. # d[i]에는 i번째에 도달했을 때 i번째가 수열의 마지막 수인 수열의 집합 중 # 가장 긴 수열의 길이가 저장되어있다. 처음엔 기존의 lis의 2중 for 문 방식으로 작성을 하려 했으나 시간초과가 떴다. 그래서 for문을 하나만 쓰는 이진탐색법으로 구현을 하려다가 닭.. 2022. 11. 25.
프로그래머스 - 숫자 카드 나누기 import math def solution(arrayA,arrayB): tempA = arrayA[0] tempB = arrayB[0] answer = 0 for _ in arrayA: tempA = math.gcd(tempA,_) # 철수 카드의 최소공배수 for _ in arrayB: tempB = math.gcd(tempB,_) # 영희 카드의 최소공배수 for _ in arrayA: if _ % tempB == 0: # 영희 카드의 최소공배수가 철수카드의 # 숫자를 나눌 수 있다면 조건 부적합 tempB = 0 break for _ in arrayB: if _ % tempA == 0: # 철수 카드의 최소공배수가 영희카드의 # 숫자를 나눌 수 있다면 조건 부적합 tempA = 0 break an.. 2022. 11. 16.
백준 1743번 - 음식물 피하기 from collections import deque N,M,K = map(int,input().split()) graph = [[0] * M for _ in range(N)] visited = [[0] * M for _ in range(N)] for _ in range(K): x,y = map(int,input().split()) graph[x-1][y-1] = 1 dx = [-1,1,0,0] dy = [0,0,-1,1] BFS로 문제를 해결 할 예정이다. 제일 먼저 자주 쓰이는 양식으로 각각 그래프와 방문그래프 그리고 방향설정 등을 구현해준다. def BFS(i,j): q = deque([(i,j)]) visited[i][j] = 1 count = 1 while q: x,y = q.popleft() .. 2022. 11. 10.
백준 1260번 - DFS와 BFS from collections import deque N,M,V = map(int,input().split()) graph = [[] for i in range(N+1)] visited = [0] * (N+1) for i in range(M): a,b = map(int,input().split()) graph[a] += [b] graph[b] += [a] 제일 먼저 입력변수들을 저장하고 그래프를 형성한다. for i in range(N+1): graph[i].sort() DFS = [] BFS = [] 정점을 방문할 때 항상 작은 순으로 우선 방문하기에 sort를 해준다. DFS / BFS는 각각 방문했던 정점을 순서대로 저장해준다. 마지막에 출력할 때 참고한다. # DFS 시작 def dfs(v): D.. 2022. 11. 10.
프로그래머스 - 과일로 만든 아이스크림 고르기 SELECT LEFT.FLAVOR FROM FIRST_HALF LEFT,ICECREAM_INFO RIGHT WHERE LEFT.TOTAL_ORDER >3000 AND RIGHT.INGREDIENT_TYPE = 'fruit_based' AND LEFT.FLAVOR = RIGHT.FLAVOR ORDER BY LEFT.TOTAL_ORDER DESC 오라클에서 JOIN을 하는 방식은 여러개 있는데, 크게는 ANSI JOIN과 ORACLE JOIN으로 나뉘고 세세하게는 INNER JOIN / OUTER JOIN / CROSS JOIN / FULL OUTER JOIN이 있다. 그 중 INNER JOIN / OUTER JOIN은 자주 쓰여서 꼭 알아두면 좋다. 2022. 11. 5.

티스토리툴바