삽입 두 개의 32비트 수 N과 M이 주어지고, 비트 위치 i와 j가 주어졌을 때, M을 N에 삽입하는 메서드를 구현하라. M은 N의 j번째 비트에서 시작하여 i번째 비트에서 끝난다. j번째 비트에서 i번째 비트까지에는 M을 담기 충분한 공간이 있다고 가정한다. 다시 말해, M=10011라면, j와 i사이에 적어도 다섯 비트가 있다고 가정해도 된다는 것이다. j=3이고 i=2인 경우처럼 M을 삽입할 수 없는 상황은 생기지 않는다고 봐도 된다. 이 문제의 핵심은 다음과 같다. 1. N의 j부터 i까지 비트를 0으로 만든다. 2. M을 시프트하여 j부터 i번 비트 자리에 오도록 만든다. 3. M과 N을 합한다. import java.io.BufferedReader; import java.io.IOExcept..
손으로 비트 조작 해보기 비트 조작에 익숙하지 않기 때문에 연습 문제를 풀어보면서 이해해보도록 하자 1. 0110 + 0110 2. 0100 * 0011 3. 1101 ^ (~1101) 4. 1101 & (~0 > 연산과 같다. 최상위 비트가 부호비트인 8비트 정수에 논리 우측 시프트를 적용하면 다음과 같다. 10110101 -> 01011010 (한 칸씩 이동하고, 왼쪽을 0으로 채움) 산술 우측 시프트는 비트를 오른쪽으로 옮기기는 하지만 부호비트는 바꾸지 않는다. 따라서 이 연산은 대략 값을 2로 나눈 효과가 있고, >> 연산과 같다. 10110101 -> 11011010 (한 칸씩 이동했지만, 부호비트는 변하지 않음) 다른 방법으로 살펴보자, 예를 들어 값이 존재하고 이를 계속적으로 시프트로 밀어낸..
한 개로 세 개 배열 한 개로 스택 세 개를 어떻게 구현할지 설명하라 이 문제는 스택이 해야 할 일을 얼마나 잘 지원하고 싶은가에 따라 난이도가 달라진다. 각 스택마다 고정된 크기를 할당하는 것으로 만족하고 싶으면 그렇게 해도 되지만, 그렇게 하면 다른 스택들은 전부 비어 있는데, 한 스택은 메모리가 거의 고갈되는 상황이 발생할 수 있다. 메모리 할당을 유연하게 할 수도 있는데, 이는 문제가 아주 많이 어려워진다고 할 수 있다. #1 고정 크기 할당 배열을 같은 크기의 세 부분으로 나누어 각각의 스택이 그 크기 내에서만 사용되도록 할 수 있다. 여기서 '['는 구간의 끝점을 포함시킨다는 의미이고, '('는 구간에 끝 점을 제외시킨다는 의미이다. class FixedMultiStack { private i..
▶ 중복 없애기 정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라. 필자는 Node 클래스를 따로 제작하여 이 문제를 풀기로 했다. class Node { int data; Node next = null; Node(int d) { data = d; } //node 추가 void append(int d) { Node end = new Node(d); Node n = this; while(n.next != null) { n = n.next; } n.next = end; } } 다음은 중복을 없애기 위해 node 클래스 안에 원소들을 추적하여 없애는 방법을 선택했다. prev는 앞서 설명했던 것 처럼 단방향일때 해당 지워야 하는 원소값을 찾을 경우 이전 노드와..
▶ 그래프 트리는 그래프의 한 종류이다. 그렇다고 모든 그래프가 트리는 아니다. 트리는 사이클이 없는 하나의 연결 그래프이다. 그래프는 단순히 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 것과 같다. - 그래프에는 방향성이 있을 수도 있고 없을 수도 있다. 방향성이 있는 간선은 일방통행, 방향성이 없는 간선은 양방향 통행 도로라고 생각하면 된다. - 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다. 모든 정점 쌍간에 경로가 존재하는 그래프는 연결 그래프라고 부른다. - 그래프에는 사이클이 존재할 수도 있고 존재하지 않을 수도 있다. 사이클이 없는 그래프는 '비순환 그래프'라고 부른다. 인접 리스트 인접 리스트는 그래프를 표현할 때 사용되는 가장 일반적인 방법이다. 모든 정점을 인접 리스트..
▶ 트리의 종류 트리를 이해하기 위한 좋은 방법 중 하나는 재귀적 설명법을 사용하는 것이다. 트리는 노드로 이루어진 자료구조이다. - 트리는 하나의 루트 노드를 갖는다. - 루트 노드는 0개 이상의 자식 노드를 갖고 있다. - 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다. 추가적으로, 트리에는 사이클이 존재하지 않는 점, 노드들은 특정 순서로 나열될 수도 있고, 그럴 수 없을 수도 있다는 점, 각 노드는 어떤 자료형으로도 표현 가능한 점, 각 노드는 부모 노드로의 연결이 있을 수도 있고, 없을 수도 있다는 점 등이 있다. Node클래스를 가장 간단하게 정의하면 다음과 같다. class Node { public String name; public Node[] child..
▶ 중복 없애기 정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라. // 일반적으로 사용하는 노드를 우리의 실습환경에 맞게 재구성 했다. class Node { int data; Node next = null; Node(int d) { data = d; } void append(int d) { Node end = new Node(d); Node n = this; while(n.next != null) { n = n.next; } n.next = end; } // 중복 제거 메소드 void deleteDups(Node n) { // Set의 장점은 데이터가 기억될 때에 순서를 저장하지 않는다는 점이다. // 즉, List와 Set의 차이 없이 분명히 두 개..
▶ 스택 구현하기 이전에는 연결리스트를 배웠다면, 이번에는 스택이다. 연결리스트는 하나의 노드를 다음 노드에 연결시켜 그 자료들을 관리하는 것이었다면, 스택은 말 그대로 데이터를 쌓아 올린다는 의미이다. 문제의 종류에 따라 배열보다 스택을 활용하는 것이 더 좋을 수 있기 때문에 분별하는 능력이 필요로 하다. 스택은, 가장 최근에 추가한 데이터 항목이 가장 먼저 제거되는 형식이다. 스택에서 가장 필수가 되는 연산을 살펴보자. pop() : 스택에서 가장 위에 있는 항목 제거 push(item) : item 하나를 스택의 가장 윗 부분에 추가 peek() : 스택의 가장 위에 있는 항목을 반환 isEmpty() : 스택이 비어 있을 때에 true를 반환 다음은 스택 예제코드이다. 스택은 같은 방향에서 아이템..
▶ 중복이 없는가 문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라. 유의점 - ASCII 문자열인지 유니코드 문자열인지 알아야 함 - 문자 집합에서 i번째 문자가 배열 내에 존재하는지 boolean 배열을 사용, 같은 원소에 두 번 접근하면 false를 리턴. package algorithm; public class Answer { public static void main(String[] args) { System.out.println(isUniqueChars("asdzxcqwe")); } public static boolean isUniqueChars(String str) { //AS..
▶ 연결리스트 차례로 연결된 노드를 표현해주는 자료구조이다. 두 가지의 형태로 나뉘는데, 단방향 연결리스트는 각 노드가 다음 노드를 가리키는 형태이며, 양방향 연결리스트에서는 각 노드는 다음노드와 이전 노드를 함께 가리킨다. 배열과 달리 연결리스트에서는 특정 인덱스를 상수 시간에 접근할 수 없다. 따라서, 배열과 같이 N번째 원소를 찾고 싶다면, 처음부터 N번 루프를 돌아야한다. 다음은 단방향 연결리스트를 구현한 코드이다. class Node { Node next = null; public Node(int d) { data = d; } void appendToTail(int d) { Node end = new Node(d); Node n = this; whild(n.next != null) { n = n..
▶ 해시테이블 효율적인 탐색을 위한 자료구조, 키를 값에 대응시킨다. 간단한 해시테이블을 구현하기 위해서는 연결리스트와 해시 코드 함수만 있으면 된다. 키와 값을 해시테이블에 넣을 때는 다음의 과정을 거친다. 1. 키의 해시코드를 계산한다. 키의 자료형은 보통 int 혹은 long이 된다. 키의 개수는 무한한데 반해 int의 개수는 유한하기 때문에 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있다는 사실을 명심하자. -> database의 키 값을 가져올 때 long을 많이 사용했었다. 2. hash(key) % array_length와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다. 물론 서로 다른 두 개의 해시코드가 같은 인덱스를 가리킬 수도 있다. 3. 배열의 각 인덱스에는 키와..
