corin

다이나믹 프로그래밍 메모리공간을 사용하여 연산속도를 비약적으로 증가시킬 수 있는 방법 다이나믹 프로그래밍을 이용하여 해결할 수 있는 대표적 예시 피보나치 수열(그냥 재귀함수로 풀 수 있으나 시간이 매우 많이 듦 > 때문에 이 기법 사용) 만약 완전탐색 알고리즘으로 풀었을때 너무 오래걸리고, 해결하고자 하는 문제에 중복부분이 있다면 다이나믹 프로그램을 사용하는 것을 생각해볼 수 있음 사용하기 위한 전제조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 탑다운/보텀업 방식 - 탑다운 방식: 재귀함수를 이용한 방법으로 큰 문제를 해결하기 위해 작은 문제를 호출 - 보텀업 방식: 단순히 반복문을 이용하여 소스코드를 작성하는 경우로 작은문제부터 차근차근..

이진탐색 : 리스트 내에서 데이터를 매우 빠르게 탐색하는 탐색 알고리즘 개념 순차탐색 : 앞에서부터 타겟을 찾는 방법 시간복잡도 = O(N) let count = 0 ; for (let i = 0 ; i < input.length ; i++ ){ if (input[i] == target ) { count++ } } 이진탐색 : 타겟과 중간점 데이터를 반복적으로 비교해서 데이터를 찾는 방법. 정렬되지 않은 arr에는 사용할 수 없음. 시간복잡도 = O(log N) 이진탐색 구현방법 2가지(재귀함수/반복문) **//재귀함수** let arr = [1,4,5,9,11,15,25,33,54,82,100,111,130,157,168,219,200,224,253,298,300] ; let target = 298; ..

코딩테스트에서 정렬알고리즘이 사용되는 경우는 일반적으로 3가지 문제유형 정렬 라이브러리로 풀 수 있는 문제 정렬 알고리즘의 원리에 대해서 물어보는 문제 더 빠른 정렬이 필요한 문제 개념 선택정렬 : 가장 작은 수를 선택하여 index[0]과 교환 시간복잡도 O(n*n) for (let i = 0 ; i < arr.length-1 ; i++) { let min = Math.min(...arr.slice(i,)) ; let min_Spot = arr.indexOf(min) ; let change = arr[i]; arr[i] = min ; arr[min_Spot] = change ; } 삽입정렬 : 첫번째 수가 정렬 완료라는 가정하에 수가 앞에서부터 작으면 왼쪽, 크면 오른쪽에 삽입 시간복잡도 O(n*n) ..

[예제문제] 음료수 얼려먹기(DFS) N, M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. let input = require('fs').readFileSync('input.txt').toString().trim().split("\n"); let [n,m] =input.shift().split(" ").map(Number) ; //m = 행의 갯수(y) , n = 열의 갯수(x) ; let grid = input.map(x=>x.split("")); let..

예제문제_게임 개발 장소는 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향을 회전만 수행하고 1단계로 돌아간다. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤..