0️⃣ Algorithm&자료구조(51)
-
[Algorithm] 시간 복잡도와 공간 복잡도
'알고리즘을 효율적을 짠다 = 시간과 공간을 최소화한다' 알고리즘의 효율성을 판단할 때, 시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)를 따진다. 백준, 프로그래머스에서도 알고리즘을 평가할 때 시간과 메모리 제한을 두는 것도 다 이런 이유에서다. 시간 복잡도(Time complexity) 개념와 예시 '입력값의 증가에 대한 연산 횟수 증가분' 시간 복잡도는 그저 실행 시간을 측정하는 것이 아니다. 실행 시간은 측정을 위한 프로그램이 필요할뿐더러 수행 환경에 따라 실행 시간이 달라질 수 있다. 이에 따라 입력값이 증가함에 따라 연산 횟수가 어떤 비율로 증가하는가에 초점을 두고 시간 복잡도를 측정한다. 시간 복잡도는 Worst Case, 즉 가장 최악으로 시간이 걸..
2022.04.16 -
[BOJ] # 15650 - N과 M (2)
BOJ # 15650 - N과 M (2) Back Tracking 문제이다. N과 M (1) 문제에서 살짝 변형된 것으로, (1) 문제를 풀 수 있다면 쉽게 통과할 수 있다. 통과 Code import sys n,m = map(int, sys.stdin.readline().split()) a = [] def solution(): if len(a) == m: print(' '.join(map(str, a))) for i in range(1, n+1): if i in a: continue elif len(a) >= 1 and i < max(a) : continue a.append(i) solution() a.pop() solution()
2022.04.15 -
[Algorithm] 백트레킹 개념, BOJ # 15649번
Back Tracking "가능한 모든 방법을 탐색하겠다." Back Tracking 이란? 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책 후보를 찾되, 가능성이 없는 경로는 사전에 차단(Purning)하여 효율을 높이는 알고리즘이다. 비슷한 알고리즘으론 DFS(완전 탐색 방법)가 있다. 하지만 이 알고리즘은 말 그대로 모든 경로를 정직하게 탐색하므로, 가능성이 없는 경로까지도 깊게 파고들어 가 효율이 떨어진다. 문제 Tip DFS로 경로를 탐색하던 과정에서, 조건문 등을 걸어 가지치기를 하는 방식으로 가야 한다. BOJ # 15649번 : N과 M (1) 백트레킹는 기본적으로 재귀 문제이다. 이를 잘 생각하며 풀어보길 바란다. 통과 예시 import sys n, m = map(int, sys..
2022.04.15