Toy 문제 4

문제 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 버블 정렬(bubble sort)은 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다. 해석(수도코드) 버블 정렬 알고리즘은 아래와 같습니다. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap) 두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap) 1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교) 1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다. 1~3의 과정을 첫 요소부터 다시 반복합니다. 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 ..

→2021.06.20

코테/코드스테이츠[JS]

Toy 문제3

문제 두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 boolean 타입으로 리턴해야 합니다. base, sample 내에 중복되는 요소는 없다고 가정합니다. let base = [1, 2, 3, 4, 5]; let sample = [1, 3]; let output = isSubsetOf(base, sample); console.log(output); // --> true 해석(수도코드) 단순히 비교 분석만 한다면 굉장히 쉬운 문제이지만 '효율'을 생각해보았을 때에 조금 더 복잡 해지는 것 같습니다. sort 메서드를 사용하여 각 배열의 숫자를 정렬을 합니다. 그렇게 되면 비교하는 횟수를 줄일 수 있으며 좀 더 효율적으로 비교가 가능합니다. sample 요소 하나를..

→2021.06.20

코테/코드스테이츠[JS]

Toy 문제2

문제 재귀함수를 사용하여 피보나치 수열 나타내기 반복문 사용 금지 해석(수도코드) 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 보통 첫 번째는 0, 두 번째는 1로 고정이 되어있고. n>=2 이라면 (n-1)(n-2) 공식이 성립되는 식입니다. 하지만 무작정 재귀 함수를 사용하여 피보나치수열을 나타내게 되면 // let fibonacci = function (n) { // if (n { if (result[n] !== undefined) return result[n]; result[n] = fibo(n - 1) + fibo(n - ..

→2021.06.20

코테/코드스테이츠[JS]

Toy 문제 1

문제 숫자 N 숫자 N의 경우의 수를 나열하였을 때 K가 몇 번째 위치한 경우의 수 인지 찾아야 합니다. 모든 경우의 수가 담긴 배열은 번호가 작을수록 앞에 위치한다고 가정합니다. ex) N = 3일경우, [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 해석 (수도코드) N이 작은 값일 때에는 모든 경우의 수를 구하는 것을 펙토리얼로 구하는 것이 나쁘지 않을 수 있지만, 12!는 약 4억 8천만에 해당하며, 일반적인 수행 속도 상한(약 1억)을 훨씬 상회하므로 순열을 전부 생성하는 것은 올바른 접근 방법이 아닙니다. 그렇기 때문에 배열 번호가 작을수록 앞에 위치해야 한다는 점을 펙토리얼과 함께 활용 해야 합니다. 숫자 N을 5 K가 [3, 2, 1, 4, 5] 라..

→2021.06.20

코테/자료구조, 알고리즘

[알고리즘] Graph / Tree / BST

1. Graph 컴퓨터 공학에서 이야기 하는 자료구조 그래프는 전혀 다른 모습을 가지고 있습니다. 자료구조의 그래프는 마치 거미줄처럼 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크 망과 같은 모습을 가지고 있습니다. 그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조입니다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다. 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어집니다. 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge) 이라고 합니다. 알아둬야 할 그래프 용어들 무(방)향그래프(undirected graph): 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는것도 가능합니다. 단방향(directed) ..

→2021.06.19

코테/자료구조, 알고리즘

[자료구조] 자료구조 기초 Stack, Queue

자료구조? 자료구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것입니다. 자료구조는 자료의 집합을 구조화하고, 이를 표현하는 데에 초점이 맞춰져 있습니다. 이미 자료구조를 알게 모르게 많이 접했습니다. 사람이 사용하기에 편리하려고, 사용하기 좋으려고 만들어진 것이 자료구조입니다. 자주 등장하는 네 가지의 자료구조 Stack, Queue, Tree, Graph 대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있습니다. 따라서 많은 자료구조를 알아두면, 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있습니다. 이것은 문제 해결력을 필요로하는 알고리즘 테스트(코딩 테스트)와 굉장히 밀접한 연관성이 있습니다. 특정 문제를 해결하는 데에..

→2021.06.17

코테/자료구조, 알고리즘

[자료구조/알고리즘] JSON, Tree UI, 재귀함수 과제

JSON의 탄생 배경 JSON은 JavaScript Object Notation의 줄임말로, 데이터 교환을 위해 만들어진 객체 형태의 포맷입니다. 네트워크를 통해, 어떤 객체 내용을 다른 프로그램에게 전송한다고 가정하겠습니다. 이 객체 내용을 일종의 메신저 혹은 채팅 프로그램에서 쓰는 하나의 메시지 입니다. const message = { sender: "김코딩", receiver: "박해커", message: "해커야 오늘 저녁 같이 먹을래?", createdAt: "2021-01-12 10:10:10" } 메시지 객체가 전송 가능하려면, 메시지를 보내는 발신자와 메시지를 받는 수신자가 같은 프로그램을 사용하거나, 문자열처럼 범용적으로 읽을 수 있는 형태여야 합니다. 전송가능한 조건 (transfera..

→2021.06.16

코테/자료구조, 알고리즘

[알고리즘] 재귀함수

재귀는 재귀 (원래의 자리로 되돌아가거나 되돌아옴) 어떻게 보면은 무한 반복문과 굉장히 비슷합니다. 살면서 재귀라는 말을 듣기 어려운거 같은데 쉽게 생각하면 반복문과 다를게 없습니다. 특히 무한 반복문 while이나 재귀함수나 탈출 조건을 if문으로 설정 해주어야 하는 것 처럼.. 항상 느끼는 거지만, 어렵게 생각하면 한없이 어려운 것 같습니다. 그렇기 때문에 많이 해보아야 해결 되는 문제인듯 합니다. 재귀를 사용할 때 1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우 2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우 ex) 펙토리얼 재귀함수 function fac(n){ if(n===1){ // 탈출 조건 return 1; } re..

→2021.06.15

티스토리툴바