Algorithm (25) 썸네일형 리스트형 [코딩테스트] minSubArrayLen, 슬라이딩 윈도우 알고리즘 문제. 슬라이딩 알고리즘 - MinSubArrayLen 위 문제는 주어진 배열의 합이 숫자랑 같거나 큰 경우, 해당 배열합의 최소 길이를 반환하는 문제이다. 즉, array와 sum이 주어지면 array 요소의 합이 sum보다 크거나 같은 최소 길이를 반환하면 된다.이때 array 요소는 인접한 요소여야 한다. 슬라이딩 윈도우 알고리즘을 통해 해결해야 하며, 시간복잡도는 O(n) 공간복잡도는 O(1)이여야 한다. 처음에 어떻게 풀어야 할지 감이 안왔다. while문을 이용해서 한 칸씩 늘려가야 겠다는 생각을 하긴 했는데, 어떻게 늘려가야 하지? 라는 고민이 계속 들었다. 결국 시간이 지나도 문제를 맞추지 못해서 답안을 확인했다. *슬라이딩 윈도우 알고리즘 : 배열의 한 부분을 정의하고, 이 부분을.. [2주만에 통과하는 알고리즘] 파이썬 입력과 출력 / 반복문과 조건문 1. 입력과 출력 #입력 #input() = 사용자한테 입력 받은것을 출력함 #case1 : 단순 정수 number = int(input()) #case2 : 단순 문자 #input default type = 문자열 타입 string = input() #출력 print(number + number) #24 print(string + string) #1212 파이썬에서 input은 기본적으로 string으로 받아오기 때문에 input()만 사용하면 string type이 된다. 만일 정수를 받아오고 싶다면 input을 int로 감싸줘야 한다. > int(input()) 숫자와 숫자를 더하면 두 값을 합한 값이 출력되지만, 문자열을 더하면 두 값을 나열한 형태로 출력된다. 1) map, split #map .. [코딩테스트] 수열 추측하기, 순열 & 이항계수 응용 1. 문제 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다. 3 1 2 4 4 3 6 7 9 16 N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하 시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다. - 첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다. - 첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫.. [코딩테스트] 조합의 경우의 수(메모이제이션) 1. 문제. 우선 nCr = n-1Cr-1 + n-1Cr 공식이 어떻게 성립하는지부터 알아보자. n개의 서로 다른 원소 중 r개를 선택하는 경우의 수를 찾을 땐, 두 가지 경우가 발생한다. 하나는 선택된 원소를 포함하는 경우이고, 하나는 포함하지 않는 경우이다. 특정 원소를 이미 선택했다고 가정하면, 남은 n-1개의 원소 중, r-1개를 더 선택해야 하므로 경우의 수는 n-1Cr-1이 된다. 반대로 선택하지 않은 경우라면, n-1개의 원소 중, r개를 선택해야 하므로 경우의 수는 n-1Cr이 된다. 따라서 n개의 원소 중 r개를 선택하는 경우의 수는, 두 경우의 수를 합한 n-1Cr-1 + n-1Cr가 된다. 2. 문제 풀이 function solution(n, r){ let answer; let dy=.. [알고리즘] 경우의 수, 순열 중복순열 조합 개념정리 코딩테스트 하는데 경우의 수 부분이 너무 헷갈려서 정리하려고 따로 포스팅한다. 내가 이 나이 먹고 중2수학 보면서 경우의 수 공부하고 있을 줄은,, 근데 개념을 모르면 다음으로 넘어가질 못하겠는데 어째ㅠ 1. 순열 순열은 원소들의 집합에서 일부 원소를 순서대로 나열하는 방법을 말한다. 이름 그대로 '순서대로 줄을 세운다'라고 이해하면 된다. 순열은 영어로 Permutation이라 첫 글자를 따서 P로 명명한다. 따라서 'n 개 중 r개를 뽑아서 줄을 세운다'는 짧게 nPr로 요약 가능하다. 1) 공식 순열의 공식은 위와 같다. 예를 들어, 1부터 10까지의 자연수 중, 2개를 뽑아 일렬로 나열하는 경우의 수를 찾는 문제가 있다. 우선 여기서 숫자 두 개를 각각 {a, b}에 집어넣는다고 가정해 보자. a.. [코딩테스트] 재귀로 팩토리얼 구현하기 1. 문제 자연수 N을 입력하면, N! 값이 출력되도록 만드시오. 1) 팩토리얼 팩토리얼은 n이 자연수일 때, 1부터 n까지의 자연수의 곱을 의미한다. n!으로 표시한다. 예를 들어, 5! = 5*4*3*2*1 = 120이다. 이는 5! = n*(n-1)*(n-2)... 이런 식으로 나타낼 수 있다. 위 식을 활용하면 재귀함수를 통해 간단하게 팩토리얼을 구현할 수 있다. 2. 풀이 function solution(n) { let answer; function DFS(n) { if (n === 1) return 1 else return n * (DFS(n - 1)); } answer = DFS(n); return answer } console.log(solution(5)); 팩토리얼 만드는 방법은 간단하다.. [코딩테스트] 재귀로 순열 구하기 1. 문제 : 순열 구하기 10 이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 순열은 주어진 집합에서 일부 원소를 순서대로 나열하는 것을 말한다. 중복 순열과 달리, 집합에서 각 원소들이 겹치면 안 된다. 2. 풀이 function solution(m, arr) { let answer = []; const n = arr.length; const ch = Array.from({ length: n }, () => 0); let tmp = []; function DFS(l) { if (l === m) { answer.push(tmp.slice()); } else { for (let i = 0; i < n; i++) { if (ch[i] === 0) { ch[i] .. [코딩테스트] 중복순열 구하기 (feat. javascript) 1. 문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 첫 번째 줄에 자연수 N(3 이전 1 2 3 4 다음
