교대최소제곱법

기본적으로 순열, 조합 문제는 DFS 재귀함수를 이용해서 해결 순열 조합 모두 "없으면 넣고 dfs()" 구조는 똑같지만 조합의 경우 start를 고려해줘야 하는 차이가 있었음 -> s에 넣고 빼고를 반복하면서 모든 경우의 수를 돌린다 + 왜 백트래킹 문제인가? s의 개수가 M이상이 되면 그 다음 경우의 수는 파악할 필요가 없기 때문에 백트래킹 문제인 것 순열 # 15649번 n,m = list(map(int,input().split())) s = [] def dfs(): if len(s)==m: print(' '.join(map(str,s))) return for i in range(1,n+1): if i not in s: s.append(i) dfs() s.pop() dfs() 조합 # 15650번 ..

분할정복 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 대표적으로 퀵소트, 머지소트 등이 있고 고속 푸리에 변환 문제 FFT 가 대표적 FFT? n차 다항식 두개를 곱할 때 시간을 줄이는 방법 O(n) → O(n log n) 다이나믹 프로그래밍 최적화 문제에 주로 사용 최적해 구조의 특징을 찾는다 재귀적으로 정의한다 바텀업 방식으로 접근한다 최적해를 구성한다 한 번 계산한 결과를 메모리 공간에 메모 리스트를 만들어서 값을 저장해놓고 계산하기전에 리스트를 체크하는 방식 *시간이 오래걸릴거 같으면 DP로 생각해보자 동적 프로그래밍은 시간-메모리 트레이드오프 관계를 가진다 그럼 다이나믹 프로그래밍을 언제 쓸 수 있을까? 최적 부분 구조 optimal substructure → 이는 그리디방..

다익스트라 알고리즘 하나의 정점에서 다른 “모든” 정점으로 가는 최단 경로를 측정하는 알고리즘 다시 다익스트라 구현 순서도 출발 노드 설정 출발 노드를 기준으로 각 노드의 최소비용 저장 방문하지 않은 노드 중에서 가장 비용이 적게드는 노드 선택 (이동한다는 개념을 가져야한다) 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소비용 갱신 3번 4번 과정 반복 어떻게 구현하나요? DP + heap을 활용한다 DP로 최단거리를 기억하고 heap을 통해 토탈 최단 거리를 구해 최단경로를 추적한다 힙을 쓰면 O(n log n), 안 쓰면 O(N**2) → 힙은 속도에 이점만 있을 뿐 다익스트라와는 관계가 없다 + 힙정렬은 불안정정렬이다 따라서 다익스트라에서도 같은 거리여도 어떤 값이 먼저 나올지는 정해지지..

DFS 깊이우선문제 sys를 import할 수 있다면 sys.setrecursionlimit(int(1e9))를 호출해야 에러가 안뜬다 사이클을 확인할때 사용 먹고 또 이동하고 먹고 또 이동하고를 나타낼때 그래프의 경우, 가중치 또는 특정 기준을 따라 탐색 방향의 우선순위를 결정한다 최대값 구할 때 "최대값보다 작으면" 이란 기준을 설정하고 찾는다 시간복잡도 N이 노드의 개수, E가 간선의 개수일 때 인접 리스트: O(N + E) 인접 행렬: O(N^2) 예제 풀이 프로세스 재귀함수를 사용 입력값 받기 방문여부를 남기는 그래프 만들기 탐색조건 시작점을 불러오고 방문했는지 여부확인하고 탐색 not visited[][] and graph[][] == 1 탐색 일단 방문기록 남기고 4방향으로 움직인다 조건에 ..

BFS 너비우선탐색 문제 최단거리를 구할때 사용 가장 먼저 찾아내는게 최단거리이다 -> BFS 사용이유 시간복잡도 N이 노드의 개수, E가 간선의 개수일 때 인접 리스트: O(N + E) 인접 행렬: O(N^2) 예제 풀이 프로세스 deque을 사용 입력값 받기 그래프크기 N, M = map(int, input().split()) 그래프 모양 board = [list(map(int,input().split())) for _ in range(N)] 볼 위치파악 for i for j append 구문으로 현위치를 파악하고 from collection import deque에 넣어놓는다 방문여부를 기억하려면 넣어두기 visited[i][j] = 1 이거로 장난 칠수도 있다 기억했다가 안했다가를 바꾸는 문제도 ..

시간복잡도 줄이는 법 최대 1억이 넘는가를 확인한다 1억 = 1초 순서대로 시간을 줄여보자 O(n) 탐색보다는 hashmap을 쓰자 단, hash도 저격당하면 O(n)임 -> 100점은 못 받는다고 보면 된다 (하지만 풀었죠?) 정렬이 되어 있다면 binary search 이진 탐색 -> O(log n) 정렬 -> O(NlogN) 투포인터 알고리즘 -> O(N) 리스트를 순차적으로 접근해야할 때 사용가능 ex) 연속 수열의 합 누적합 배열을 이용 -> O(N)으로 구현 가능 DP문제처럼 누적합 배열의 이전 값을 이용하면 O(N)으로 구현