컴공생의 개인공부일지

패리티 비트 정보 전달 과정에서 오류가 생겼는 지 검사하기 위해 추가하는 비트를 말한다. 전송하고자 하는 데이터의 각 문자에 1비트를 더하여 전송한다. 종류 : 짝수 패리티(Even Parity), 홀수 패리티(Odd Parity) 패리티 예시 7비트 데이터 짝수 홀수 0000000 (0) 00000000 10000000 1010001 (3) 11010001 01010001 1101001 (4) 01101101 11101001 1111111 (7) 11111111 01111111 짝수 패리티 전체 비트에서 1의 개수가 짝수가 되도록 패리티 비트를 정하는 것이다. Ex.) 데이터 비트에서 1의 개수가 홀수면 패리티 비트를 1로 정한다. 홀수 패리티 전체 비트에서 1의 개수가 홀수가 되도록 패리티 비트를 정..

정의 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법 비트 연산자 A B ~A ~B A & B A | B A ^ B 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 0 1 1 0 NOT(~) : 비트 값을 반전하여 변환 AND(&) : 대응하는 두 비트가 모두 1일 때, 1 반환 OR(|) : 대응하는 두 비트 중 모두 1이거나 하나라도 1일 때, 1 반환 XOR(^) : 대응하는 두 비트가 서로 다를 때, 1 반환 SHIFT(>>, 0100 -> 1000 : 1 -> 2 -> 4 -> 8 오른쪽 시프트 : 1000 -> 0100 -> 0010 -> 0001 : 8 -> 4 -> 2 -> 1 비트 마스크의 집합의 활용 다..

정의 완전이진트리를 기본으로 하는 힙 자료구조를 기반으로한 정렬 방식 동작 과정 1. 정렬할 N개의 원소로 최대 힙 구성 2. 최대 힙의 루트 노드와 마지막 원소 위치 교환 3. 새 루트 노드에 대해 최대 힙 구성 4. 원소 개수만큼 2와 3을 반복 수행 시간복잡도 최선일 경우 O(nlogn), 평균일 때 O(nlogn), 최악일 경우에도 O(nlogn)이다. 과정 1로 build heap 과정으로 O(nlogn)의 시간 복잡도를 가진다. 과정 2와 3은 최대 힙에서 원소를 하나 삭제한 다음 heapify를 진행하는 것과 같으므로 O(logn)이 걸리고 원소 개수만큼 반복되므로 O(nlogn)이 된다. 따라서 O(nlogn) + O(nlogn) = O(nlogn)의 시간복잡도를 가진다. 공간복잡도 추가적..

정의 정렬되어 있는(이분 탐색의 주요 조건) 배열에서 데이터를 찾으려 시도할 때, 순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라 탐색 범위를 절반씩 줄여가며 찾아가는 탐색 방법이다. 시간 복잡도 전체 탐색 : O(N) 이분 탐색 : O(logN) 동작 과정 우선 정렬을 한다. left와 right로 mid 값을 설정한다. mid와 내가 구하고자 하는 값과 비교한다. 구할 값이 mid보다 :left = mid + 1 구할 값이 mid보다 낮으면 :right = mid - 1 left > right가 될 때까지 계속 반복하기 소스 코드 Java public static int solution(int[] arr, int M) { // arr 배열에서 M을 찾자 Arrays...

정의 하나의 배열을 두개로 균등한 배열로 분할하고 분할된 배열을 각각 정렬한 다음, 이를 다시 합하여 정렬을 완성하는 알고리즘이다. 분할 정복의 일종으로, 하나의 큰 문제를 두 개의 작은 문제로 분할하여 해결한 다음, 결과를 모아서 문제를 완전히 해결하는 전략이다. 동작과정 리스트의 길이가 1 이하이면 이미 정렬된 것으로 보고 그대로 데이터 리턴. 그렇지 않은 경우에는 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 시간복잡도 최선의 경우 O(nlogn), 평균의 경우 O(nlogn), ..

정의 상태를 가지고 있는 주체 객체 및 상태의 변경을 알아야 하는 관찰 객체 주제 객체와 상태 변경을 알아야 하는 관찰 객체가 존재하며 1 대 1 or 1 대 N 관계이고 다른 객체의 상태가 변경될 때마다 어떤 이벤트를 실행하고 싶을 때 사용된다. 인터페이스를 연결하여 느슨한 결합성을 유지하여 Publisher와 Observer 인터페이스를 적용한다. 주로 분산 이벤트 핸들링 시스템을 구현하는데 사용된다. 추가로 MVC(Model-View Controller)패턴에 자주 사용된다. 느슨한 결합성 두 객체가 상호작용을 하지만 서로에 대해서 잘 모른다는 것을 의미한다. 옵저버는 언제든지 추가할 수 있고, 주제와 옵저버는 서로 독립적으로 재사용할 수 있고, 서로한테 영향을 미치지 않는다. 즉, 변경 사항이 생..

객체를 생성할 떄 어떤 클래스의 인스턴스를 만들 지 서브 클래스에서 결정하게되는 것 인스턴스 생성을 서브 클래스에게 위임한다. 팩토리 메소드 구조 팩토리 메소드 패턴 예시 Robot(추상 클래스) - SuperRobot - PowerRobot RobotFactory(추상 클래스) - SuperRobotFactory- ModifiedSuperRobotFactory # Robot이라는 클래스에서 RobotFactory에서 생성한다. RobotFactory 클래스 생성 public abstract class RobotFactory { abstract Robot createRobot(String name); } SuperRobotFactory 클래스 생성 public class SuperRobotFactory ..

어떤 작업을 처리하는 일부분을 서브 클래스로 캡슐화해 전체 일을 수행하는 구조는 바꾸지 않으면서 특정 단계에서 수행하는 내역을 바꾸는 패턴 전체적으로는 동일하면서 부분적으로 다른 구문으로 구성된 메소드의 코드 중복을 최소화 할 때 유용하다. 구조 예제 // AbstractClass.java public abstract class AbstractClass { protected abstract void hook1(); protected abstract void hook2(); public void templateMethod() { hook1(); hook2(); } } // ConcreteClass.java public class ConcreteClass extends AbstractClass { @Over..

애플리케이션이 시작될 때, 어떤 클래스가 최초 한 번만 메모리를 할당하고 해당 메모리에 인스턴스르 만들어 사용하는 패턴 하나의 인스턴스만 생성하여 사용하는 디자인 패턴 생성자가 여러번 호출되도, 실제로 생성되는 객체는 하나이며 최초로 생성된 이후에 호출된 생성자는 이미 생성한 객체를 반환시키도록 만드는 것이다 (java에서는 생성자를 private으로 선언해 다른 곳에서 생성하지 못하도록 만들고, getInstance() 메소드를 통해 받아서 사용하도록 구현한다) 사용 이유 한번에 new 연산자를 통해 고정된 메모리 영역을 사용하기에 추후 해당 객체에 접근할 때 메모리 낭비를 방지할 수 있다. 메모리 측면에서 이득을 볼 수 있기 때문이다. 싱글톤으로 구현한 인스턴스는 '전역'이므로, 다른 클래스의 인스턴..

코드를 재사용하기 위해 구조를 변경하는 패턴 사용 방법 : 상속 호환되지 않은 인터페이스를 사용하는 클라이언트 그대로 활용 가능 향후 인터페이스가 바뀌더라도, 변경 내역은 어댑터에 캡슐화 되므로 클라이언트가 바뀔필요가 없다. 기능상 문제없이 동작하는 코드가 단지 인터페이스 차이 때문에 사용할 수 없는 경우 많이 응용되는 패턴이다. 또한 기존 코드에 오류가 있거나 보정 작업이 필요한 경우에도 유용하다. 어댑터 객체 어댑터, 클래스 어댑터 클래스 어댑터 패턴 쓰려면 다중 상속이 필요, 자바에서는 다중 상속이 불가능 밑 그림과 같이 클래스 어댑터에서는 어댑터를 만들 때 타겟과 어댑터 모두의 서브 클래스로 만들고,객체 어댑터 에서는 구성을 통해서 어댑티에 요청을 전달한다는 점을 제외하면 별다른 차이점이 없다. ..