알고리즘10 그래프(Graph) 그래프(Graph)란? 정점(node 혹은 vertex)과 정점 사이를 잇는 간선(edge)으로 구성된 자료구조이다. SNS, 네비게이션, 추천 알고리즘 등 실생활에 많이 사용된다. 특징 정점들 사이 순서가 있는 경우엔 방향 그래프, 없는 경우엔 무방향 그래프라고 한다. 간선에 가중치(비용 등)가 주어지면 가중 그래프가 된다. 순환 혹은 비순환 구조를 이룬다. 노드 간에 2개 이상의 경로도 가능하다. 부모 - 자식 관계라는 개념이 없다. (네트워크 모델) 그래프와 트리의 비교 그래프 트리 관계 그래프 ⊃ 트리 방향성 방향, 무방향 모두 존재 방향만 존재 사이클 순환, 비순환 모두 존재 (자기 순환도 가능) 비순환만 존재 루트 노드 X O 부모 - 자식 X O 모델 네트워크 모델 계층 모델 간선의 수 자유.. 2023. 9. 26. 버블 정렬, 선택 정렬, 삽입 정렬 버블 정렬 (Bubble sort) 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않으면 자리를 교환하며 정렬하는 알고리즘. 오름차순의 경우 가장 큰 값을 가장 뒤로 보내며 정렬하고, 내림차순의 경우 가장 작은 값을 가장 뒤로 보내며 정렬한다. 버블 정렬이라는 이름은 원소의 이동이 가벼운 거품이 수면 위로 올라오는 모습과 닮아 붙여진 것이다. // 구현하기 function bubbleSort(arr){ for(let i = 0; i arr[j+1]){ // SWAP! // [arr[j], arr[j+1]] = [arr[j+1], arr[j]] let temp = arr[j];.. 2023. 9. 11. Daily Coding 16. isIsogram Q. (공백이 없는 알파벳) 문자열을 입력받아 아이소그램인지 여부(boolean 타입)를 리턴해야 합니다. 아이소그램(isogram)은 각 알파벳을 한번씩만 이용해서 만든 단어나 문구를 말합니다. //첫 번째 풀이 function isIsogram(str) { if(str === '') { //빈 문자열을 입력받은 경우, true를 리턴. return true; } for(let i = 0; i < str.length; i++) { for(let j = 0; j < str.length; j++) { if(i !== j && str[i].toUpperCase() === str[j].toUpperCase()){ //대소문자 구분 X return false; } else {return true;} } } } .. 2023. 2. 6. Daily Coding 15. modulo Q. 두 수(num1, num2 → 둘 다 0이상의 정수)를 입력받아, num1를 num2로 나눈 나머지를 리턴해야 합니다. ※ 나눗셈(/), 나머지(%) 연산자 사용은 금지 //나의 풀이 function modulo(num1, num2) { if(num1 === 0) { //0은 어떤 수로 나누어도 나머지가 0입니다. return 0; } if(num2 === 0) { //어떤 수도 0으로 나눌 수 없습니다. return 'Error: cannot divide by zero'; } if(num1 === num2) { return 0; } let a = 0; for(let i = 0; i = num2) { num1 = num1 - num2; } return num1; } 역시 훨씬 간단하게 풀 수 있는 .. 2023. 2. 3. Daily Coding 06. letterCapitalize Q. 문자열(공백이 있는 알파벳 문자열)을 입력받아 문자열을 구성하는 각 단어의 첫 글자가 대문자인 문자열을 리턴해야 합니다. ex.'hello world' → 'Hello World' //첫 번째 풀이 function letterCapitalize(str) { let arr = str.split(' '); let result = ''; for (let i = 0; i < arr.length; i++) { result = result + arr[i][0].toUpperCase() + arr[i].slice(1, arr[i].length) + ' '; } return result.slice(0, -1); } 처음에는 이렇게 풀었다. 그런데 이 방법으로는 공백만 입력되었을 때나 공백이 여러 번 입력 되었을 .. 2023. 1. 25. Daily Coding 05. firstReverse Q. 문자열을 입력받아 순서가 뒤집힌 문자열을 리턴해야 합니다. //첫 번째 풀이 function firstReverse(str) { let result = ''; for(let i = str.length-1; i >= 0; i--) { result = result + str[i]; } return result; } for 문을 이렇게 써 본 적이 없어서 긴가민가하며 테스트를 돌려 봤는데 모두 통과가 되었다. //두 번째 풀이 function firstReverse(str) { let splitString = str.split(''); return splitString.reverse().join(''); } 배열의 순서를 반전해 주는 reverse()라는 메서드를 발견해서 시도해 본 풀이. 마찬가지로 모.. 2023. 1. 25. Daily Coding 04. firstCharacter Q. 문자열을 입력받아 문자열을 구성하는 각 단어의 첫 글자로 이루어진 문자열을 리턴해야 합니다. //나의 풀이 function firstCharacter(str) { let arr = str.split(' '); //띄어쓰기 기준으로 잘라서 배열 만들기 let result = ''; for(let i = 0; i < arr.length; i++) { result = result + arr[i].slice(0, 1); //배열 각 요소의 첫 번째 글자만 골라 붙이기 } return result; } //레퍼런스 코드 function firstCharacter(str) { if (str === '') { return ''; } let words = str.split(' '); let result = '';.. 2023. 1. 24. Daily Coding 03. powerOfTwo Q. 수(number 타입의 정수 (num >= 1))를 입력받아 2의 거듭제곱인지 여부(boolean 타입)를 리턴해야 합니다. ※ Number.isInteger, Math.log2, Math.log 사용은 금지 function powerOfTwo(num) { if(num === 1){ //2의 0승은 1 return true; } let power = 2; while(power < num){ //반복문(while)문을 사용해야 함. power = power * 2; } if(power === num){ return true; }else return false; } 2023. 1. 24. 이전 1 2 다음
