Computer Science

scores 배열안에 [8, 4, 2, 1, 3, 6, 7 ,9, 5] 라는 숫자들이 주어진다. 이 숫자들을 각각의 순위대로 나열하는 문제이다. 따라서, [8, 4, 2, 1, 3, 6, 7 ,9, 5] 의 점수 배열이 [4, 3, 2, 1, 2, 3, 4, 5, 1]으로 변화된다. 과정 8은 4 보다 크다. 4는 2 보다 크다. 2는 1 보다 크다. 따라서, 순위를 정하면 8 -> 4, 4-> 3, 2-> 2, 1-> 1으로 변화될 수 있다. [ 4, 3, 2, 1 ....] 3은 1보다 크다. 6은 3보다 크다. 7은 6보다 크다. 9는 7 보다 크다. 따라서, 위와같이 순위를 정하면 [4,3,2,1, 2, 3, 4, 5 ...] 이 된다. 마지막으로 5는 9보다 작으므로 [4,3,2,1, 2, 3,..

DataStructure and Algorithm 2021. 11. 20. 01:26

Array 관련 문제는 3가지가 있다. 1. Insert 2. Delete 3. Search + 4. In-Place Array Operations 1. Insert 1-1. Insert를 할때 첫번째 element에 insert하는것. 모든 Elements를 한칸씩 옮기고 첫번째 element에 value를 insert한다. 1-2. 마지막 element에 insert 하는것. array의 길이를 count하고 마지막 element에 insert한다. 1-3. 중간 element에 insert하는것. 중간에 지점을 지정하고, 그 뒤의 elements를 옮긴 후, 중간지점에 value를 insert한다. 2. Delete 2-1. Delete를 할때 첫번째 element를 delete 하는것. 첫번째 e..

DataStructure and Algorithm 2021. 1. 1. 10:09

위장 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다. 같은 이름을 가진 의상은 존재하지 않습니다. clothes의 ..

DataStructure and Algorithm 2020. 6. 20. 14:59

이진 트리 배열에서의 BFS 와 DFS (without stack and recursion) 이진 트리 배열에서의 BFS는 간단합니다. 이진 트리 배열에서 각 요소들이 레벨별로 배치되어 있고, BFS도 레벨별로 검사를 확인하기 때문에, 이진 트리 배열에서의 BFS는 Linear Search(선형검색)과 동일합니다. public int bfs(Predicate predicate) { for(int i = 0; i < array.length; i++) { if( array[i] != null && predicate.test(array[i])) return i; } return -1; } 깊이 우선 탐색(Depth-first Search)는 조금 더 어렵습니다. 스택 자료구조를 사용해서 DFS를 하게되면, 일..

DataStructure and Algorithm 2020. 5. 11. 12:41

BFS vs DFS 이진트리에 해당하는 검색 알고리즘은 2가지가 있다: 너비 우선 탐색(Breath-first Search), 깊이 우선 탐색 (Depth-first Search). BFS는 노드를 루트노드부터 시작하여 레벨단계로 검색합니다. 즉, 해당노드이 자식노드를 먼저 다 확인 한 후, 그 자식노드의 자식노드를 검색하는 형태입니다. 이 과정은 모든 노드들을 검색하거나, 검색 조건을 만족할때 까지 진행합니다. BFS : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 DFS는 다르게 행동합니다. DFS는 루트노드부터 시작하여 제일 왼쪽 리프를 우선적으로 확인하고, 오른쪽 노드를 확인합니다. DFS : 0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6 기본 이진 트리에 BFS를 Queu..

DataStructure and Algorithm 2020. 5. 10. 12:58

이번 글에서는 스택이나 재귀함수 없이 깊이 우선 탐색을 이진트리에 적용하려고 합니다. 이진 트리 배열 이것이 이진 트리입니다. 0 은 루트노트(root node). 0 은 두개의 자식노드(children node)를 가지고 있습니다: 왼쪽 1, 오른쪽 2 각각의 자식노드는 또다시 자신의 자식노드를 가지고 있습니다. 이러한 노드들을(3,4,5,6) 리프 노드(leaf nodes)라고 부릅니다. 루트와 리프노드 사이의 있는 간선(edges)의 갯수가 이진트리의 높이를 결정합니다. 위의 트리에서는 높이가 2입니다. 일반적인 이진트리의 접근법은 BinaryNode라는 클래스를 만들어줍니다. public class BinaryNode{ public T data; public BinaryNode left; publ..

DataStructure and Algorithm 2020. 5. 10. 08:41