LALA's blog

벌써.. 3주차, 그리고 프리코스가 끝이 났다. 😱 이번 과제는 이전 과제들에 비해 난이도가 확실히 높아졌음을 느꼈고, 그만큼 더 많은 생각과 고민을 하며 과제를 진행하게 됐다. 과제는 난이도가 높아졌는데, 이번 과제 기간동안은 하필 시험, 병원, 일 등 때문에 너무 바빴어서 시간이 많이 부족해서 아쉬움이 너무 남는다. 그래도 과제가 끝나고 꼭 더 리팩토링하고 적용해봐야겠다! 어려웠던 점 설계 과정은 여전히 쉽지 않았다. 🙃 처음 보는 enum 클래스를 사용해야 했다. getter를 지양하고 객체에 메세지를 보내는 방식으로 구현했다. 비즈니스 로직과 UI 로직을 분리하려 노력했다. enum 클래스 이번 과제에서는 enum 클래스를 사용해서 구현해야하는 요구사항이 있었다. enum 은 단지 타입이 같은 값..

벌써 프리코스 2주 차도 끝이 났다. 😱 이번 과제에서 주신 피드백을 적용하기 위해 많은 고민을 하고, 조금이라도 더 확신이 드는 코드를 작성하기 위해 노력했다. 어려웠던 점 설계 과정은 여전히 쉽지 않았다. 🙃 클래스를 분리하고, 어떠한 책임을 부여할지 결정하는 부분이 어려웠다. 의도가 드러나는 변수, 클래스, 함수명을 짓는데 많은 고민을 했다. 1차보다 README.md 문서를 자세하게 작성하려고 노력했다. Stream을 적용해 보았다. 클래스 분리 JAVA에서 지향하는 OOP를 고려하여 클래스를 다음과 같이 설계했다. Car 이름과 위치를 저장한다. 전진 혹은 정지한다. 가장 앞선 위치에 있는지 체크한다. CarRepository 입력받은 차들을 저장한다. 난수를 발생시킨다. 우승자를 계산한다. G..

프리코스 1주 차를 끝마쳤다. 🥶 처음 과제를 봤을 땐 어렵지 않은 것 같다고 느꼈는데, 계속 수정해 나갈수록 부족함도 느끼고 어려움도 느꼈던 과정이었다. 부족했던 점 JAVA 개발이 처음이라 문법이나 IntelliJ 사용이 익숙하지 않아 삽질하는 시간이 꽤 있었다. 기능 구현 목록을 정할 때 눈에 보이는 것들만 작성하기 바빴다. 설계를 먼저 하지 않고 기능을 구현하는데 집중했다. 모든 코드를 class 하나에 다 넣었다. 즉, 모든 데이터와 입력, 출력, 계산 수행을 한 class에서 하도록 했다. 자료구조를 비교해보지 않고 선택했다. 아래 코드를 보시다시피 제일 처음 기능을 모두 완성했을 땐 한 Class에 모든 기능을 구현했다. 사실 최근에 알고리즘 문제를 많이 풀다 보니 해당 과제를 알고리즘 문제..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

이진 탐색 트리의 단점 이전에 공부했던 이진 탐색 트리는 검색, 삽입, 삭제 모두 O( h )의 시간복잡도를 보였다. h = 트리의 높이를 의미하며, 평균적으로 O( log n )이라고 할 수 있다. 하지만 최악의 경우? 이진 탐색 트리는 일반 이진트리 구조이다. 일반 이진트리는 2개 이하의 자식을 가지고 있다는 조건을 가졌을 뿐, Complete 이진트리처럼 균형 잡힌 트리 모양을 보장하지 않는다. 만약 입력 데이터가 [ 1, 2, 3, 4 ] 순으로 들어온다면 아래의 그림과 같이 한쪽으로 치우친 Skewed Tree 모양이 되어, 노드 n개일 때 O( n )의 시간복잡도를 보일 수 있다. 이진 트리에 1부터 N까지 랜덤한 숫자가 들어온다면 평균적으로 트리의 높이가 log n이라고 증명되어 있다. lo..

Dynamic Set이란? - 배열, 링크드 리스트, 트리 등등.. - 여러 개의 키(key) 저장 - 다음과 같은 연산을 지원하는 자료구조 ① INSERT - 새로운 키의 삽입 ② SEARCH - 키 탐색 ③ DELETE - 키의 삭제 다양한 방법들 - 정렬된 / 정렬되지 않은 배열 or 연결 리스트를 사용할 경우 INSERT, SEARCH, DELETE 중 적어도 하나는 O(n)이다. - 이진 탐색 트리(Binary Search Tree), 레드-블랙 트리, AVL-트리 - Direct Address Table, 해쉬 테이블 등 검색 트리란? - Dynamic set을 트리의 형태로 구현 - 일반적으로 INSERT, SEARCH, DELETE 연산이 트리의 높이(height)에 비례하는 시간복잡도를 ..

트리의 기본적인 성질 - 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다. - 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. - 또한 임의의 두 노드간의 경로도 유일하다. (같은 노드를 두 번 이상 방문하지 않는다는 조건하에). 이진 트리 (binary tree)란? - 이진 트리는 여러 개의 자식 노드를 가질 수 있는 일반 트리와 다르게, 최대 2개의 자식만을 가질 수 있다. - 즉, 0개, 1개, 2개의 자식 노드만 가질 수 있다. - 각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지가 지정된다. (자식이 한 명인 경우에도) 이진 트리 응용의 예 1) Expression Tree 2) 허프만 코드 각각의 알파벳에 부여된 이진 코드를 이런 트리의 형태로 표현할 수 있..

계수 정렬 원소의 종류가 K개, 즉 원소들의 범위가 0 ~ K-1일 때, 시간복잡도가 O(N + K)밖에 되지 않는 정렬법이다. 예를 들어, 원소가 1, 2, 3, 4, 5로 한정되어 있을 때 어떻게 정렬하면 좋을까? 각 원소가 몇 번 등장했는지 세면 간단하게 정렬할 수있다. [ 1 , 5 , 4 , 2 , 3 , 1 , 4 ] 의 경우 1 - 2번 2 - 1번 3 - 1번 4 - 2번 5 - 1번 등장한다. 그렇다면 작은 수부터 등장한 횟수만큼 [ 1 , 1 , 2 , 3 , 4 , 4 , 5 ] 로 쉽게 정렬할 수 있다. 가장 빠른 퀵정렬의 시간복잡도는 O(nlogn)이며 최악의 경우에는 O(N^2)이다. 그렇다면 항상 계수정렬이 더 빠른걸까? 만약 10개의 데이터 (N = 10)이고 가장 큰 수가 ..