현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘📕 문제 1. N과 M (1)자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열- 해결 아이디어비어있는 리스트에서 시작해 수를 하나씩 추가하면서 길이가 M인 수열이 완성되면 출력 - e.g. N: 4, M: 2 == 1부터 4까지 자연수 중 중복없이 2개를 고른 수열import sysinput = sys.stdin.readlineN, M = map(int, input().split())answer = [0] * Mvisited = [False] * (N+1)def backtrack(k): # k번째 인덱스에 값을 넣는 함수 ..

스택의 대표적인 활용 사례수식의 괄호 쌍전위/중위/후외 표기법DFSFlood Fill수식의 괄호 쌍이란?주어진 괄호 문자열이 올바른지 판단하는 문제.여는 괄호의 갯수와 닫는 괄호의 갯수가 같아야 함. (단, 괄호의 종류가 2개 이상일 경우에는 여는 괄호와 닫는 괄호의 갯수만으로 판별 불가)문자열을 순회하며 닫는 괄호가 나오면 직전의 여는 괄호와 매칭되는지 확인e.g. 아래의 괄호 문자열이 올바른지 확인하고, 그 이유에 대해 설명하시오.( ( ) ) ( ) ( ) - O. 여는 괄호와 닫는 괄호가 대칭됨.) ) ( ( ) - X. 닫는 괄호와 대칭되는 여는 괄호가 없음.( ) ( ) ) ( ( ) - X. 닫는 괄호와 대칭되는 여는 괄호가 없음.📕 문제 1. ( { ) }순회를 하며 닫는 괄호가 나오면 ..

여러 개의 하위 문제를 먼저 푼 후, 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘문제를 해결하기 위한 점화식을 먼저 찾아낸 후, 점화식의 항을 밑에서부터 차례로 구해나가면서 답을 알아내는 알고리즘풀이 과정테이블 정의하기점화식 찾기초기값 정하기📕 문제 1. 피보나치 수열재귀에서의 피보나치 수열은 중복된 연산이 계속 발생.e.g. fibo(5) = fibo(4) + fibo(3) = fibo(3) + fibo(2) + fibo(3) = ...이미 구했던 값을 계속 연산하기 때문에 O(1.1618^N)의 시간복잡도를 가짐def fibo(n): if n 피보나치 수열 문제를 DP로도 해결할 수 있음.미리 배열을 만들어두고 인덱스를 채워나가는 방식으로 해결 가능시간복잡도 O(N)def fibo(n): a..

1차원 배열에서 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터를 사용하여 O(N)에 해결하는 알고리즘연속된 구간의 원소들을 처리하거나 정렬된 배열에서의 작업을 구현할 때 시도📕 문제 1. 다음의 배열에서 원소들의 합이 x인 연속 부분 배열의 개수를 구하라.arr = [1, 3, 6, 5, 2, 7, 9], x = 9시작 시점을 한 칸씩 전진해나가면서 구간의 합을 구해야함. 📕 문제 2. 다음의 배열에서 두 개의 원소의 합이 x와 같은지를 확인하고, 같다면 각 원소의 인덱스를 반환하라.arr = [10, 4, 15, 11, 7, 5], x = 15이전 문제처럼 배열을 그대로 두고 st와 en 두 포인터를 0으로 잡으면 답을 찾을 수 없음.배열이 정렬되어 있지 않으면 다음에 올 값이 이전..