Algorithm/개념 (14) 썸네일형 리스트형 [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 .. [알고리즘] 경우의 수, 순열 중복순열 조합 개념정리 코딩테스트 하는데 경우의 수 부분이 너무 헷갈려서 정리하려고 따로 포스팅한다. 내가 이 나이 먹고 중2수학 보면서 경우의 수 공부하고 있을 줄은,, 근데 개념을 모르면 다음으로 넘어가질 못하겠는데 어째ㅠ 1. 순열 순열은 원소들의 집합에서 일부 원소를 순서대로 나열하는 방법을 말한다. 이름 그대로 '순서대로 줄을 세운다'라고 이해하면 된다. 순열은 영어로 Permutation이라 첫 글자를 따서 P로 명명한다. 따라서 'n 개 중 r개를 뽑아서 줄을 세운다'는 짧게 nPr로 요약 가능하다. 1) 공식 순열의 공식은 위와 같다. 예를 들어, 1부터 10까지의 자연수 중, 2개를 뽑아 일렬로 나열하는 경우의 수를 찾는 문제가 있다. 우선 여기서 숫자 두 개를 각각 {a, b}에 집어넣는다고 가정해 보자. a.. [Algorithm] 깊이우선탐색 알고리즘 (DFS, Depth First Search Algorithm) 1. 깊이우선탐색(DFS, Depth First Search) 깊이 우선 탐색은 트리나 그래프를 탐색하는 방법 중 하나로, 깊이를 우선으로 하여 시작노드에서 자식노드까지 순서대로 탐색하는 알고리즘을 말한다. 부분집합, 미로 풀기, 그래프에서 연결된 구성 요소 찾기, 퍼즐 풀기 등에서 사용된다. 재귀함수와 스택으로 비교적 쉽게 구현할 수 있으며, 후에 배울 BFS에 비해 메모리를 덜 사용한다. 그러나 재귀함수와 스택 자료구조를 사용하기 때문에 스택을 적절하게 관리하지 않으면, stack overflow로 이어질 수 있다. 또한 항상 최적의 솔루션을 찾는 것은 아니다. * 트리구조 동그란 부분을 노드(node)라고 한다. * 스택 오버플로우(stack overflow) 지정한 스택 메모리 사이즈보다 더 많은.. [Algorithm] 재귀함수 개념과 동작방식 1. 재귀함수 재귀함수는 자기 자신을 호출하는 함수를 말한다. 반복문을 조금 더 간결한 코드로 풀어낼 때 사용한다. 스스로를 호출하는 함수이기 때문에 반드시 종료조건을 써줘야 하며, 무한루프 되지 않도록 주의해야 한다. 1) 재귀함수 구현(자바스크립트) 자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지 출력하는 프로그램을 작성하세요. function solution(n){ function DFS(L){ if(L === 0) return; else { DFS(L-1); conosle.log(L); } } } //1, 2, 3 자바스크립트에서 재귀함수를 구현하는 방법은 간단하다. 자기 자신을 호출하는 함수를 사용하면 된다. 위 예시를 살펴보면 DFS 함수 내에서 스스로를 호출한 것을 확인할 수 있다. .. [Algorithm] 이진탐색 알고리즘 (Binary Search Algorithm) 1. 이진탐색(Binary Search) 이분탐색이라고도 불리는 이진탐색 알고리즘은, 정렬된 배열 내에서 대상 값의 위치를 찾는 검색 알고리즘이다. 대상 값을 배열의 중간 요소와 비교한 후, 동일하지 않으면 절반을 제거하고 이를 성공할 때까지 반복한다. 정렬된 배열을 앞에서부터 하나하나 순차적으로 탐색하는 것을 순차탐색이라 하는데, 이러한 순차탐색보다 좀 더 빠르게 위치를 찾을 수 있다. 이진탐색의 시간복잡도는 O(log(n))이다. (순차탐색의 시간복잡도는 O(n)) 2. 이진탐색 구현 function solution(target, arr) { let answer; arr.sort((a, b) => a - b); //인덱스번호 let lt = 0, rt = arr.length - 1; while (lt.. [Algorithm] 탐욕 알고리즘 (Greedy Algorithm) 1. 탐욕 알고리즘(Greedy Algorithm) 탐욕 알고리즘은 선택의 순간마다 그 이후를 고려하지 않고, 현 시점에서 가장 최적인 방법을 선택하는 알고리즘을 말한다. 순간마다 최적인 방법을 선택하기 때문에 항상 최적의 결과값을 배출하진 않는다. 그러나 다른 알고리즘보다 평균적으로 속도가 빠르고, 어느 정도 최적에 근사한 답을 알려준다. 2. 문제 : 회의실 배정 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작.. [Algorithm] 삽입정렬 알고리즘 (Insertion Sort Algorithm) 1. 삽입정렬 (Insertion Sort) 삽입정렬은 배열의 모든 요소를 앞에서부터 차례로 비교하여 자신의 위치를 찾아 삽입하며 정렬하는 알고리즘이다. 앞에 있는 요소들과 비교해야 하기 때문에 두 번째 인덱스부터 시작한다. 평균적으로 O(n^2)의 시간복잡도를 갖는다. 2. 삽입정렬 구현 function solution(arr) { let answer = arr; for (let i = 1; i = 0; j--) { if (arr[j] > tmp) arr[j + 1] = arr[j]; else break; } arr[j + 1] = tmp; } return answer; } let arr = [.. [Algorithm] 버블정렬 알고리즘(Bubble Sort Algorithm) 1. 버블정렬(Bubble Sort) 버블정렬은 인접한 항목의 각 쌍을 비교하여 순서를 정렬하는 알고리즘이다. 6 5 3 1 8 7 2 4 > 6, 5 교환 5 6 3 1 8 7 2 4 > 6, 3 교환 5 3 6 1 8 7 2 4 > 6, 1 교환 5 3 1 6 8 7 2 4 > 6, 8 교환x 5 3 1 6 8 7 2 4 > 8, 7 교환 5 3 1 6 7 8 2 4 > 8, 2 교환 5 3 1 6 7 2 8 4 > 8, 4 교환 5 3 1 6 7 2 4 8 위처럼 한 번의 반복이 끝나면 가장 큰 숫자가 맨 마지막에 오게 된다.(오름차순 기준) 이를 모든 숫자를 서로 비교할때까지 반복하면 된다. O(n^2)의 시간복잡도를 갖으며, 매우 단순하지만 성능이 좋지 않기 때문에 잘 사용하지 않는다. 2. 버.. 이전 1 2 다음
