본문 바로가기
[Algorithm] 백준 BOJ 1074 Z python 파이썬 분할정복 실버1 Private 난이도 : ♥♥♥♡♡ 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 시간초과 코드 n,r,c=map(int,input().split(' ')) size=2**n graph=[[0 for _ in range(size)] for _ in range(size)] cnt=0 dr=[0,0,1,1] dc=[0,1,0,1] def divide(r,c,size): global cnt if size==2: for i in range(len(dr)): graph[r+dr[i]][c+dc[i]]=cnt..
이분탐색 : 이진탐색 : Binary Search 틀/템플릿 # mid 라는 값으로 주어진 문제를 해결할 수 있는지 확인 def is_possible(mid): pass # 이분탐색을 진행할 구간 지정 lo = 0 hi = 1e9 answer = lo # 이분탐색 start # 1] 최대중에 최소 찾기 -> 가능하면 범위를 낮춰가기 while lo 가능하면 범위를 높혀가기 while lo
입력의 갯수에 따른 시간복잡도 한계 : 시간초과 계산 BigO 시간 N n**2 1000 ~ 5000 nlogn ~10만 n ~1000만 이분탐색 ~100억 Python은 1초에 2000만번정도 연산 한다고 생각하면 된다 n이 천만 ~ 1억 단위 => O(N) 으로 풀어라. N이 만 ~ 천만 단위 => O(NLOGN)으로 풀어라. N이 천 단위 => O(N^2) 으로 풀어라. N이 백 단위 => O(N^3)~ O(N^4) 진짜 이상하게만 하지 말고 풀어라. N 이 10~30 => 브루트포스해라(다 돌리면 됨)
최단경로 : 다익스트라 : dijkstra : 방향가중치그래프 유형은 DP+그리디 가 합쳐진 느낌이다 A노드에서 B노드로 간다는 방향이 있는 그래프에서 사용한다. 근데 그렇게 이동하는데 비용이 각각 다르다. 다익스트라는가중치가 음수인 경우에는 사용할 수 없다. GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소 github.com 이 자료들로 공부했다 가장 거리가 짧은 노드부터 탐색하는 이유 while q: # 큐가 비어있지 않다..
그래프 : DFS/BFS : 깊이우선탐색/너비우선탐색 DFS 재귀 함수 사용 종료조건 스택 list : append, pop 재귀를 쓰지 않아도 가능하다 def dfs(graph, start_node): need_visited, visited = list(), list() need_visited.append(start_node) while need_visited: node = need_visited.pop() if node not in visited: visited.append(node) for i in range(len(graph[node])-1,-1,-1) : need_visited.append(graph[node][i]) return visited BFS direction=[[0,1,0,-1],[1,0,-1,0]] def bfs(x,y,graph,vi..
DP : Dynamic Programming : 동적 계획법 : 동적 프로그래밍 : 다이나믹 프로그래밍개념 정리/template/상향식 하향식 비교 Bottom up Top down 상향식 하향식 for로 구현 재귀함수로 구현 작은 문제를 모아 큰 문제 해결 큰 문제를 해결하기 위해 작은 재귀 함수 호출 점화식 필요 점화식 필요 메모이제이션 없음 메모이제이션=캐싱 결과 저장용 리스트나 사전을 DP 테이블이라 함. 오버헤드를 줄일 수 있다. 일반적으로 성능이 더 좋다. 오버헤드 가능성이 있다. # 상향식 dp_table[1] = 1 dp_table[2] = 1 for i in range(3, n+1): dp_table[i] = dp_table[i - 1] + dp_table[i - 2] # 점화식 # 하향식 def dp(n): # 종료조건 if n == 1: return 1 elif n == 2: return 1 # 메모이제이션 if dp_table[..
[Algorithm] 백준 BOJ 1463 1로 만들기 : python 파이썬 DP 실버 3 Private 난이도 : ♥♥♥♡♡ 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net n=int(input()) d=[0]*(n+1) d[1]=0 for i in range(2,n+1): d[i]=d[i-1]+1 if i%3==0: d[i]=min(d[i], d[i//3]+1) if i%2==0: d[i]=min(d[i], d[i//2]+1) print(d[n]) 백준 제출 버전 설명 3가지 방법중 1) 1을 빼는 방법 2) 3으로 나누는 방법 3)2로 나누는 방법 으로 이미 계산했던 작은 수들에 대한 결과를 활용하므로써 더 큰 숫자들의 결과를 알 수 있다. 1,2,3 번 방법 모두 그 전 숫자의 결과에 연산을 한 번만 더 ..
[Algorithm] 백준 BOJ 11000 강의실 배정 : python 파이썬 그리디 골드 5 Private 난이도 : ♥♥♥♥♡ 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si 0: # 수업이 겹침 ->강의실 추가 contin..

티스토리툴바