스택(Stack) 영역과 힙(Heap) 영역은 프로그램에서 사용하는 데이터를 관리하기 위한 메모리 영역에 속하며 각 영역의 주요 차이점은 프로그램에서 메모리를 할당하는 방식과 사용하는 방식에 존재한다. 스택(Stack) 영역 스택 영역은 컴파일할 때 크기가 정해지며 함수를 호출할 때 메모리가 쌓이고 함수에 정의된 데이터를 담아두는 영역으로 후입선출(LIFO, Last In First Out)의 특성을 가진다. 함수를 호출할 때 스택 프레임이 생기고 그 안에 호출된 함수의 매개변수, 지역변수, 리턴 값 등을 담아 두며 함수가 종료되면 메모리도 해제된다. 스택 영역의 크기는 제한이 있기 때문에 함수를 너무 많이 반복하여 사용하게 되면 오버플로우가 발생하여 예기치 않은 동작이 발생할 수 있고 이를 최소화할 방..
SOLID의 실질적인 내용은 Robert C. Martin이 처음 소개했는데, SOLID라는 약자는 Michael Flaters에 의해 나중에 소개되었다. SOLID는 개발자가 프로젝트를 만들 때 좋지 않은 코드를 만들지 않으면서 가독성을 높이고 테스트하기 쉬운 코드를 만들 수 있도록 하여 프로젝트의 개발, 유지보수 그리고 확장하기 쉽도록 개발하는 데 도움 되는 원칙들이다. S : 단일 책임 원칙(Single Responsibility Principle, SRP)하나의 클래스는 하나의 일만 해야 한다.즉, 하나의 클래스를 변경하는 이유 또한 하나여야 하는 것이다. 여러 일을 하나의 클래스에서 처리하도록 모아둔다면 여러 개발자가 협업할 때 각각의 개발자가 각각의 이유로 하나의 클래스를 동시에 수정하는 문제..
최장 공통부분 수열은(LCS, Longest Common Subsequence) 여러 개의 수열이 주어졌을 때 두 수열의 부분 수열이 되는 수열 중 가장 긴 수열을 찾는 방법이다. 구하는 방법은 하나의 수열을 순서대로 다른 수열의 모든 문자와 비교하여 같은지 비교하는데, 동적 계획법(DP)을 활용하여 문제를 푼다. 1. 만약 같다면 현재 비교하고 있는 [n][n] 번 위치의 문자 이전에 매치됐던 [n-1][n-1] 번 위치에 있는 문자에 더한다. 2. 만약 다르다면 비교하기 이전에 나왔던 가장 긴 길이를 갖도록 하기 위해서 [n][n-1] 위치의 값과 [n-1][n] 위치의 값을 비교하여 큰 값을 가진다. 3. 배열의 최종 위치의 숫자는 가장 긴 수열의 길이를 갖게 된다. 예시: ABCD, BZDCD =..
객체 지향 프로그래밍(Object-Oriented Programming, OOP)은 프로그래밍의 패러다임 중 하나로써 만들고자 하는 현실을 추상화하여 독립된 상태와 행위를 가지는 객체를 만들고 각 객체가 상호 작용할 수 있도록 개발하는 것이다. 객체 지향 프로그래밍은 독립적인 여러 객체를 가지고 개발하는 것이기 때문에 코드의 재사용이 쉽고 모듈화하기 용이하기 때문에 기존에 만들어 둔 코드나 오픈 소스 등을 활용하기 좋고 더 좋은 코드를 찾으면 대체하는 것 또한 쉽기에 대규모 프로젝트를 만드는 데 사용하기 좋고 유지 보수하는 데도 좋다. 다만 추상화하는 과정이 어렵고 추상화하는 과정 중에 문제가 있으면 구현할 때 어려움이 발생할 가능성이 높다. 객체 지향 프로그래밍의 기본 구성 요소와 특징은 아래와 같다...
데이터를 입력받은 후 데이터에서 가야하는 거리를 구한다. 가야하는 거리를 이동하는 최소값은 규칙이 있다. 이 규칙은 1부터 하나씩 최소값을 찾아보면 규칙이 보이고 규칙은 다음과 같다. 1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 8 9 ... 와 같은 증가 형식을 띄게 된다. 이를 구현한 코드는 아래와 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new In..
총 데이터의 개수가 주어졌을 때 10 대의 컴퓨터에 차례로 총 데이터를 분산시켰을 때 마지막 데이터의 위치를 구하는 문제이다. 입력 데이터는 테스트 횟수와 테스트 데이터가 순서대로 입력된다. 테스트 데이터는 "A B"와 같은 형식으로 입력된다. 데이터의 총 수는 A에 B승한 것과 같다. (EX: "3 7"은 "3 * 3 * 3 * 3 * 3 * 3 * 3" 와 같고 계산했을 때 "2187"이 나오게 된다.) 데이터의 총 갯수가 몇이던지 10개의 컴퓨터에 분산하여 배분하기 때문에 10으로 나누었을 때 나머지값이 정답이다. 다만 데이터의 총 개수를 먼저 구하게되면 데이터의 수가 많아질 경우 실패하게 된다. 따라서 데이터의 총 개수를 먼저 구하는 것이 아니라 A * A 의 위치를 구한 후 해당 위치의 다음 컴..
인터프린터 언어 인터프린터 언어는 개발자가 작성한 코드를 기계어로 변환(컴파일)하는 과정 없이 명령어를 바로 해석하여 실행하는 언어를 뜻한다. 여기에는 R, Python, Javascript 같은 언어들이 있다. 컴파일 언어 컴파일 언어는 개발자가 작성한 코드 전체를 한 번에 검사하여 해석한 후 기계어로 변환하고 변환한 내용을 기반으로 실행하는 언어를 뜻한다. 여기에는 C, Java, Scala 같은 언어들이 있다. 인터프린터 언어 vs 컴파일 언어 두 언어의 차이점은 개발자가 작성한 코드의 해석과 실행을 같이 하느냐 하지 않으냐이다. 인터프린터 언어는 실행할 때 해석하면서 실행하기 때문에 컴파일 언어보다 느리다는 단점이 있다. 그러나 개발자가 작성한 코드를 기계어로 변환(컴파일)하는 과정이 없기 때문에..
AVL 트리는 값을 추가하거나 삭제할 때 스스로 균형을 잡는 이진 탐색 트리이다. 이 트리는 두 자식 트리의 높이가 항상 최대 1만큼 차이나야 하며 차이가 1보다 커지면 스스로 트리를 회전하여 균형을 잡으며 삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있다. 검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(log n)의 시간 복잡도가 걸린다. 회전 트리의 자식 노드 간 차수의 차가 1보다 커지게 되면 균형이 맞지 않다고 보고 트리를 재구성하는데 이 작업을 회전이라 한다. 회전하는 모양에 따라서 LL 회전, LR 회전, RR 회전, RL 회전이라고 할 수 있다. 각 회전을 구분하는 방법은 회전하는 노드가 왼쪽 자식 노드, 왼쪽 자식 노드이면 LL, 오른쪽 자식 노드, 오른쪽 자식 노드이..
이진 탐색 트리(Binary Search Tree)는 다음과 같은 속성을 가진다. 1. 노드의 왼쪽 서브 트리는 노드의 값보다 작은 값으로 이루어진다. 2. 노드의 오른쪽 서브 트리는 노드의 값보다 큰 값으로 이루어진다. 3. 노드의 좌우 서브 트리는 모두 이진 탐색 트리여야 한다. 4. 중복되는 노드가 없어야 한다. 이진 탐색 트리의 시간 복잡도는 최악일 경우 O(n)이며 최선일 경우 O(log n)이다. 최악의 경우 5 / 4 / 3 / 2 / 1 최선의 경우 10 / ＼ 5 15 / ＼ / ＼ 2 7 12 17 삽입 1. 검색을 수행한다. 2. 검색 중 중복되는 노드가 있는지 확인 3. 검색 중 하위 노드에 노드가 없는 경우 노드를 삽입 삭제 삭제하려는 노드의 자식 수에 따라 방식이 달라진다. 1...
여러 개의 값 중 가장 크거나 작은 값을 빠르게 찾기 위한 완전 이진 트리 형식의 트리로 부모 노드의 값이 항상 자식 노드의 값보다 크거나 작도록 만들어 대소관계를 가지도록 만든다. 따라서 루트 노드는 항상 가장 크거나 가장 작은 값을 가지게되며 최댓값(또는 최솟값)을 바로 찾을 수 있게 된다.( O(1) ) * 루트 노드가 가장 클 때는 최대힙, 가장 작을 때는 최소힙이라고 한다. 노드 간 값의 대소관계는 오로지 부모 노드와 자식 노드 사이에만 성립하며 형제 노드 사이에서는 관계없다. 즉 아래와 같은 트리가 있으면 A와 B(혹은 C) 간에는 대소관계가 성립되어야 하며 B와 C 간에는 성립되지 않아도 된다. A / ＼ B C 노드 추가 방법 트리의 가장 마지막에 노드 추가 추가한 노드와 추가한 노드의 부..