코딩테스트 (21) 썸네일형 리스트형 [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 [인프런 코딩테스트] 이진트리(깊이 우선 탐색)로 부분집합 구하기, DFS 1. 문제 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 단, 공집합은 출력하지 않습니다. 1) 부분집합과 공집합 우선 문제를 풀기 전에, 부분집합에 대해서 알아보자. 부분집합은 한 집합의 일부를 나타내는 것으로, 집합 A의 모든 원소가 집합 B에 포함될 때 A를 B의 부분 집합이라고 한다. 공집합은 원소를 하나도 가지고 있지 않은 집합으로, 부분집합에 포함된다. 만일 { 1, 2, 3 }이라는 집합이 있다고 해보자. 이때 부분집합을 구하기 위해서는 각 원소들이 집합에 포함되는지 확인해야 한다. 1이 포함되는 경우와 그렇지 않은 경우, 2가 포함되는 경우와 그렇지 않은 경우, 3이 포함되는 경우와 그렇지 않은 경우. 이를 트리로 표현하면 위와 같.. 이전 1 2 3 다음
