문제 재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀 함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15) a, b, c가 주어졌을 때, w(a, b, c)를 출..

이번 포스팅에선 큐(Queue)의 개념과 코드 구현을 할 것이다. 만약 스택(Stack) 개념을 알지 못한다면 이전 포스팅을 보고 오자. [이전 포스팅 URL: https://mengu.tistory.com/29] [자료구조] 스택(Stack) 개념 및 코드 구현 자료구조 중 하나인 스택(Stack)에 대해 알아보고, 직접 코드로 구현해보자. 배열 구현과 연결 리스트 구현 모두 해볼 것이다. 들어가자. 스택(Stack) 개념 가장 나중에 넣은 데이터를 가장 먼저 빼 mengu.tistory.com 들어가보자! 큐(Queue) 개념 큐(Queue)는 FIFO(First In First Out) 방식의 자료구조이다. 먼저 들어온 요소가 가장 먼저 나간다. 큐(Queue)의 제일 앞 요소를 front, 제일 ..

#15652번 - N과 M (4) 통과 Code import sys n, m = map(int, sys.stdin.readline().split()) a = [] def solution(): if len(a) == m : return print(' '.join(map(str, a))) for i in range(1, n+1): if len(a) > 0: if i < a[-1]: continue a.append(i) solution() a.pop() solution() 시간 복잡도 : O(n^m) 공간 복잡도 : O(1)

# 15651번 - N과 M (3) 통과 Code import sys n, m = map(int, sys.stdin.readline().split()) a = [] def solution(): if len(a) == m : return print(' '.join(map(str, a))) for i in range(1, n+1): a.append(i) solution() a.pop() solution() 시간 복잡도 : O(n^m) 공간 복잡도 : O(1)

'알고리즘을 효율적을 짠다 = 시간과 공간을 최소화한다' 알고리즘의 효율성을 판단할 때, 시간 복잡도(Time complexity)와 공간 복잡도(Space complexity)를 따진다. 백준, 프로그래머스에서도 알고리즘을 평가할 때 시간과 메모리 제한을 두는 것도 다 이런 이유에서다. 시간 복잡도(Time complexity) 개념와 예시 '입력값의 증가에 대한 연산 횟수 증가분' 시간 복잡도는 그저 실행 시간을 측정하는 것이 아니다. 실행 시간은 측정을 위한 프로그램이 필요할뿐더러 수행 환경에 따라 실행 시간이 달라질 수 있다. 이에 따라 입력값이 증가함에 따라 연산 횟수가 어떤 비율로 증가하는가에 초점을 두고 시간 복잡도를 측정한다. 시간 복잡도는 Worst Case, 즉 가장 최악으로 시간이 걸..

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()