WOONY's 인사이트

6장 - 객체와 자료 구조 변수를 비공개로 정의하는 이유가 있다. 남들이 변수에 의존하지 않게 만들고 싶어서다. 그런데 어째서 수많은 프로그래머가 조회(get) 함수와 설정(set) 함수를 당연하게 public으로 설정해 비공개 변수를 외부에 노출할까? 자료 추상화 자료를 세세하게 공개하기보다는 추상적인 개념으로 표현하는 것이 좋다. 똑같이 2차원 점을 표현하는 두 클래스를 예시로 살펴보자. // 구체적인 Point 클래스 public class Point { // 필드값이 public으로 오픈 public double x; public double y; } // 추상적인 Point 클래스 public interface Point { // 필드값이 외부로 노출되어 있지 않고 오직 getter / sett..

Java Solution class Solution { public int maxSubArray(int[] nums) { //Solution 1: my solution /** Runtime: 9 ms, faster than 5.84% of Java online submissions for Maximum Subarray. Memory Usage: 74.1 MB, less than 41.86% of Java online submissions for Maximum Subarray. 시간복잡도: O(n) - 아래 나올 Solution 2와 동일한 시간복잡도이나 매번 dp 값을 갱신하기 위해 참조해야 하는 점에서 중간에 품이 들어가는 듯. 공간복잡도: O(n) - dp array를 n개 원소만큼 생성해야 함 */..

오늘부로 정글이 끝났다. 소회글도 한 번 적었어야 했는데, 여기에 개발 글 외에 다른 글을 쓰기가 부담스러워지는 바람에...나중에 회사 합격하고 한 번에 쓰는 걸로 할 예정이다. 당분간은 딴소리 없이 공부 관련 내용만 올릴 생각! 바로 가보자. -- 알고리즘 공부를 다시 시작하면서 프로그래머스 고득점 kit을 풀기 시작했다. 가장 먼저 나오는 단원인 해시부터 호기롭게 시작했건만 Level 2부터 턱 막혀버리는..게 아닌가. 그래서 내리 연달아 2문제를 공부하고 나서 관련 개념을 정리했다. 해시(Hash table) Hash table: key를 value에 매핑하는 array 형태의 자료구조 우리가 흔히 해시라고 부르는 자료구조는 엄밀히 말하면 해시 테이블(Hash table), 또는 해시 맵(Hash ..

malloc: Dynamic memory allocation(동적 메모리 할당) Dynamic Memory Allocator 우리는 왜 동적 메모리 할당을 이용할까? C언어에서는 배열을 만들 때, 반드시 그 사이즈를 미리 선언해줘야 한다. 예컨대 2학년 3반 학생 수가 32명인데 이를 배열로 담는다고 하자. 그러면 정확히 size = 32라고 선언해줘야 한다. 그런데 2학년 모든 반에 대해 각각 배열을 만들어준다고 하면, 우리는 각 반 학생 수에 맞게 일일이 배열을 선언해줘야 한다. 이는 굉장히 비효율적이다. 일일이 타자를 치고 있는 상황을 생각해보라. 이런 낭비를 막기 위해, 학년 별 학생 수를 담고 있는 배열에서 숫자를 받아와 그 학생 수만큼 배열을 자체적으로 그때그때 생성할 수 있다면 프로그래머가 ..

지금 시간은 3시 3분..자그마치 6명의 집단 지성이 힘을 합쳐 겨우 디버깅을 완료하고 모든 테스트 케이스 통과!! 삭제 기능에 대해 빠르게 로직 정리하고 집 가야겠다.. 삭제(Deletion) 옮기거나 삭제하는 노드의 원래 색을 기억해뒀다가 옮기거나 지우려는 노드 색이 검정인 경우에만(=이중 흑색 노드) 트리를 고친다. 지우려는 노드 z 혹은 옮기려는 노드가 빨간색이면 rb트리 특성을 위반하지 않으니 고칠 필요가 없다. 지우려나 옮기려는 노드가 검정일 때는 경로 상의 검정 노드 개수가 변하므로 트리 특성을 위반한다. 이 경우에는 fixup 함수로 수정한다. 삭제 기능은 세 가지 케이스로 나눠서 구현한다. 1. 삭제하려는 노드(=z)의 왼쪽 자식만 있는 경우 (=오른쪽 자식이 NIL인 경우) 이때는 왼쪽..

요 며칠간 끊임없이 고통을 안겨줬던 레드블랙 트리(이하 RB트리)..그래도 계속 보다 보니까 얼추 감이 잡히기 시작한다. 아직 가장 큰 관문인 삭제가 남아있지만 그래도 삽입 구현 완료! RB트리 개념부터 시작해서 삽입까지 빠르게 정리하고 마무리할 예정. 오늘 풀었던 알고리즘 문제는 따로 포스팅해야겠다. Red-Black Tree(레드블랙 트리) 1. RB트리 정의 rb트리는 균형 이진 탐색 트리의 여러 버전 중 하나이다. 균형 이진 탐색 트리란, 이진 탐색 트리에 노드를 삽입/삭제하는 과정에서 어느 한 쪽으로 노드가 쏠리는 것을 방지하기 위해 규칙을 추가한 심화 버전 이진 탐색 트리라고 보면 되겠다. 왜 이런 짓을 하냐? 이진 탐색 트리를 만드는 이유는 특정 노드를 검색하는데 드는 시간 복잡도가 O(lo..

0. 목차 1. 아침 산책 풀이 2. 위상 정렬 점점 말이 없어진다.. 바로 풀이로 가자. 1. 아침 산책 (#21606) 먼저 문제 링크. 문제 풀이의 논리는 아래와 같다. 문제에서는 실내 노드에서 출발해 실내 노드로 도착한다고 설명한다. 그래서 실내를 기준으로 생각하게 되나, 이 문제는 실외 노드를 중심에 놓고 인접한 실내 노드를 세는 방식이 훨씬 편하다. 먼저 실외 노드를 기준으로 인접해있는 실내 노드 수를 count한다. 실외 노드를 가운데 놓고 인접한 실내 점 n개가 붙어있을 때, 갈 수 있는 경로의 수는 n * n-1 (n개의 실내 점 중 하나 고르는 경우의 수 X 실외 점 1개 고르는 경우의 수 1 X 앞에서 고른 1개의 실내 점 제외한 n-1개 점 중 하나 고르는 경우의 수) for문 돌면..

0. 목차 1. 트리 순회 - Preorder / Inorder / Postorder 2. 이진 검색 트리 - 재귀를 활용해 검색하는 방법 3. 서로소 집합 구조 & 유니온 파인드 & 크루스칼 알고리즘: 서로소인 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 1. 이진 검색 트리 & 데이터 탐색 방법: 트리 순회 - Preorder / Inorder / Postorder 개념 정리부터 먼저 하고 넘어가자. 이진 트리란, 부모 노드가 왼쪽/오른쪽 자식 이렇게 두 개의 자식 노드만을 갖는 트리를 말한다. 이때, 왼쪽/오른쪽 자식을 구분한다. 이진 트리에 대한 보다 자세한 정리는 아래 챕터에서 하기로 하고, 여기서는 곧바로 문제를 보면서 이진 트리에서 데이터를 탐색하는 방법인 트리 순회에 대해..