데이터들을 Node로 관리 (Node : data, 다음 노드의 주소값으로 이루어져 있음)
리스트는 데이터의 저장 순서를 유지해야하는 자료구조가 아님
Node
리스트의 구성
필요한 Node들 head : 리스트의 머리를 가리킴 tail : 리스트의 꼬리를 가리킴 cur : 데이터의 조회에 사용됨
head에 데이터 추가 시 장점 : tail 노드가 불필요 단점 : 저장 순서가 유지되지 않음
tail에 데이터 추가 시 장점 : 저장 순서가 유지됨 단점 : tail 노드가 필요
데이터 추가 tail 또는 head쪽에 데이터 추가 후 tail 또는 head가 가리키는 값 변경 ex) tail에 데이터 추가 시
데이터 조회 cur Node를 이용해 조회 ex) data2 조회
데이터 삭제 삭제할 노드를 가리키고 있는 노드의 next 값을 삭제할 노드가 가진 next 값으로 변경
추상 자료형 (ADT)
자료형
반환값
내용
initialize()
void
리스트 초기화
insert(Node)
boolean
리스트에 데이터 저장
next()
Node
현재 가리키고 있는 노드의 다음 노드
remove()
Node
현재 가리키고 있는 노드를 삭제
count()
int
현재 리스트에 있는 데이터의 개수
구현
디렉토리 구조
인터페이스 구현 다형성을 위해 List관련 메소드를 인터페이스로 구현
package List;
// 다형성을 위해 List를 인터페이스로 생성
public interface List {
// 리스트 초기화
void initialize();
// 리스트에 데이터 삽입 (어떤 값이 올 지 모르므로 Object를 인자로 받음)
boolean insert(Object data);
// 첫 번째 데이터를 가리키도록 하며 값을 반환
Object first();
// 현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
Object next();
// 현재 참조하고 있는 데이터를 지움
Object remove();
// 리스트에 저장된 데이터의 개수를 반환
int count();
}
단일 연결 리스트 구현 실제 단일 연결 리스트 구현
package List.LinkedList.Single;
import List.List;
public class SingleLinkedList implements List {
public class Node {
Object data;
Node nextNode;
public Node(Object data, Node nextNode){
this.data = data;
this.nextNode = nextNode;
}
public Node() {
this.data = null;
this.nextNode = null;
}
}
Node head = null;
Node tail = null;
Node cur = null;
Node newNode = null;
int dataCount = 0;
@Override
public void initialize() {
head = null;
tail = null;
cur = null;
newNode = null;
}
@Override
public boolean insert(Object data) {
try {
newNode = new Node(data, null);
if (head == null) {
head = newNode;
} else {
tail.nextNode = newNode;
}
tail = newNode;
dataCount++;
return true;
}catch (Exception ex){
return false;
}
}
@Override
public Object first() {
try {
if (head == null) {
return null;
}
cur = head;
return cur.data;
}catch (Exception ex){
return null;
}
}
@Override
public Object next() {
try{
if (head == null){
return null;
}
if (cur.nextNode == null){
System.out.println("마지막 노드입니다.");
return null;
}
cur = cur.nextNode;
return cur.data;
}catch (Exception ex) {
return null;
}
}
@Override
public Object remove() {
try{
if (head == null){
return null;
}
Node tmpNode = head;
while(tmpNode.nextNode != cur){
tmpNode = tmpNode.nextNode;
}
tmpNode.nextNode = cur.nextNode;
dataCount--;
return cur;
}catch (Exception ex){
return null;
}
}
@Override
public int count() {
return dataCount;
}
}
메인 구현 데이터 삽입, 삭제 및 조회 기능 테스트
package List.LinkedList.Single;
public class SingleLinkedListMain {
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
// 리스트 초기화
linkedList.initialize();
// 리스트에 데이터 삽입
linkedList.insert(1); linkedList.insert(2);
linkedList.insert(3); linkedList.insert(4);
linkedList.insert(5); linkedList.insert(6);
// 첫번째 노드로 설정 및 데이터 가져오기
Object data = linkedList.first();
System.out.println(data);
// data가 null이 될 때까지 반복
while((data = linkedList.next()) != null) {
System.out.println(data);
}
// 데이터 삭제
Object remove = null;
data = linkedList.first();
if ((int)data == 4){
remove = linkedList.remove();
System.out.println((int)data + "가 삭제되었습니다.");
remove = null;
}
while((data = linkedList.next()) != null){
if ((int)data == 4){
remove = linkedList.remove();
System.out.println((int)data + "가 삭제되었습니다.");
remove = null;
}
}
// 첫번째 노드로 설정 및 데이터 가져오기
data = linkedList.first();
System.out.println(data);
// data가 null이 될 때까지 반복
while((data = linkedList.next()) != null) {
System.out.println(data);
}
}
}
더미노드를 이용한 단순 연결 리스트
기존 연결 리스트에서는 head가 첫 번째 노드를 가리키고 있음 Dummy Node 이용 시 head가 더미 노드를 가리키고 있음
노드들을 추가/삭제 및 조회 시 첫 번째 노드와 두 번째 이후의 노드간 차이가 있음 - 첫번째 노드를 먼저 가져와서 처리한 후 next 메소드로 다음 노드를 참조하는 방식
순열 함수가 종료됐을 때 배열의 값을 다시 원상복구 해주어야 함 (그 다음 수와 다시 순열을 계산해야 하므로)
구현 주석으로 설명했으나, 제일 빠른건 직접 디버깅하면서 확인해보면 된다.
public static void swapPermutation(int[] arr, int depth, int n, int r) {
// depth와 r이 같으면 다 뽑았다는 것이므로
if (depth == r){
for(int i=0; i<r; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
return;
}
else {
/*
1, 2, 3 세 개의 숫자를 순열로 구한다고 했을 때,
재귀의 특성 상
depth가 0일 경우 1XX, 2XX, 3XX을 구해야 함
depth가 1일 경우 12X, 13X 를 구해야 함
depth가 2일 경우 123, 132 를 구해야 함
depth == r에서 return 되면서 배열을 원상복구 시킨 후
depth가 0일 경우 2XX, 3XX 를 구하는 과정을 반복
*/
for(int i=depth; i<n; i++){
swap(arr, i, depth);
swapPermutation(arr, depth + 1, n, r);
swap(arr, i, depth);
}
}
}
public static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
visited을 이용한 순열
방문했는지 확인할 수 있는 visited 배열과, 결과를 저장할 수 있는 result 배열이 필요함
Depth를 이용한 풀이
Depth와 r의 값이 같으면 모두 다 뽑았다는 것이므로 결과값 출력
visited를 통해 result에 데이터 저장 시 중복값이 들어가지 않도록 함
구현
public static void visitedPermutation(int[] arr, boolean[] visited, int[] result, int depth, int n, int r) {
if (depth == r){
for(int i : result){
System.out.print(i + " ");
}
System.out.println();
return;
}
else {
for(int i=0; i<n; i++){
if (!visited[i]){
visited[i] = true;
result[depth] = arr[i];
visitedPermutation(arr, visited, result, depth + 1, n, r);
visited[i] = false;
}
}
}
}
결과비교
결과를 살펴보면 아래와 같다.
swap을 이용한 순열과 visited를 이용한 순열의 데이터를 비교해보면,
swap에서는 3, 2, 1 / 3, 1, 2 순으로 출력이 되는데 visited에서는 3, 1, 2 / 3, 2, 1 순으로 출력이 된다.
따라서 swap을 이용해서 순열을 구했을 때는 순서대로 순열이 구해지지 않는다는 차이점을 발견할 수 있다.
단점 1) 배열의 길이가 사전에 정의되어야 함 2) 중간 데이터 삭제 시 해당 인덱스 이후의 값들은 한 칸씩 이동이 발생
설명
삽입 - 보통 배열의 마지막에 데이터가 삽입되며, 삽입 시 배열의 크기도 고려해야 함 - 배열의 중간에 데이터를 삽입하기 위해서는 배열의 길이가 충분한지 확인해야 하며, 삽입된 위치 뒤에 존재하는 모든 데이터들이 한 칸씩 뒤로 이동해야 하므로 중간에 데이터 삽입 시 비효율적 - 시간 복잡도 : O(n)
삭제 - 배열의 중간에 위치한 데이터를 삭제할 경우 해당 위치의 뒤 데이터들은 한 칸씩 앞으로 이동해야 하므로 배열의 크기가 크고 삭제가 빈번할수록 비효율적 - 시간복잡도 : O(n)
조회(검색) - 배열에 존재하는 데이터에 대한 인덱스 값들이 고정되어 있기 때문에 조회가 간편함 - 시간복잡도 : O(n) [찾으려는 값이 없을 경우]
접근 - 배열의 인덱스로 데이터에 바로 접근할 수 있음 - 시간복잡도 : O(1)
추상 자료형 (ADT)
자료형
반환값
내용
initialize()
void
리스트 초기화
insert(Object data)
boolean
리스트에 데이터 저장
first()
Object
첫 번째 데이터를 가리키도록 하며 값을 반환
next()
Object
현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
remove()
Object
현재 참조하고 있는 데이터를 지움
count()
int
리스트에 저장된 데이터의 개수를 반환
구현
디렉토리 구조
인터페이스 구현 다형성을 위해 List관련 메소드를 인터페이스로 구현
package List;
// 다형성을 위해 List를 인터페이스로 생성
public interface List {
// 리스트 초기화
void initialize();
// 리스트에 데이터 삽입 (어떤 값이 올 지 모르므로 Object를 인자로 받음)
boolean insert(Object data);
// 첫 번째 데이터를 가리키도록 하며 값을 반환
Object first();
// 현재 참조하고 있는 데이터의 다음 데이터를 가리키도록 하며 값을 반환
Object next();
// 현재 참조하고 있는 데이터를 지움
Object remove();
// 리스트에 저장된 데이터의 개수를 반환
int count();
}
순차 리스트 구현 실제 리스트 코드 작성
package List.ArrayList;
import List.List;
public class ArrayList implements List {
// 리스트 최대 개수를 10으로 지정
final int MAX_LIST_COUNT = 10;
Object[] list = new Object[MAX_LIST_COUNT];
// 현재 위치 저장 변수 (아무것도 참조하고 있지 않으므로 -1)
int curPosition = -1;
// 리스트에 저장된 데이터 개수
int countOfData = 0;
@Override
public void initialize() {
curPosition = -1;
countOfData = 0;
for(int i=0; i<MAX_LIST_COUNT; i++){
list[i] = null;
}
}
@Override
public boolean insert(Object data) {
if (data == null){
System.out.println("null 값을 추가할 수 없습니다.");
return false;
}
if (countOfData >= 100){
System.out.println("더이상 데이터를 추가할 수 없습니다.");
return false;
}
// 리스트에 데이터 저장
list[countOfData++] = data;
return true;
}
@Override
public Object first() {
if (countOfData == 0){
System.out.println("데이터가 없습니다.");
return null;
}
// 첫 번째를 가리키도록 설정
curPosition = 0;
// 첫 번째 데이터 반환
return list[curPosition];
}
@Override
public Object next() {
if (curPosition >= countOfData - 1){
System.out.println("데이터가 없습니다.");
return null;
}
curPosition++;
return list[curPosition];
}
@Override
public Object remove() {
if (countOfData == 0){
System.out.println("데이터가 없습니다.");
return null;
}
// 현재 참조된 데이터를 제거하기 위해 변수에 할당
Object rData = list[curPosition];
// 한 칸씩 당기기 위한 반복문
for(int i=curPosition; i<countOfData - 1; i++){
list[i] = list[i+1];
}
// 데이터가 제거됐으므로 개수와 위치를 하나씩 감소
countOfData--;
curPosition--;
return rData;
}
@Override
public int count() {
return countOfData;
}
}
메인 구현 데이터 삽입, 삭제 및 조회 기능 테스트
package List.ArrayList;
public class Main {
public static void main(String[] args) {
ArrayList list = new ArrayList();
// 리스트 초기화
list.initialize();
// 리스트 데이터 추가
list.insert(1); list.insert(2);
list.insert(3); list.insert(4);
list.insert(5); list.insert(6);
// 첫 번째 인덱스를 가리키도록 설정
Object data = list.first();
System.out.println(data);
// data가 null이 아닐때까지 반복
while((data = list.next()) != null){
System.out.println(data);
}
// data 삭제
Object rData = null;
data = list.first();
if ((int)data == 4){
rData = list.remove();
System.out.println(rData + " 데이터가 삭제되었습니다.");
rData = null;
}
while((data = list.next()) != null){
if ((int)data == 4){
rData = list.remove();
System.out.println(rData + " 데이터가 삭제되었습니다.");
rData = null;
}
}
// 삭제 후 재출력
data = list.first();
System.out.println(data);
// data가 null이 아닐때까지 반복
while((data = list.next()) != null){
System.out.println(data);
}
}
}
package Greedy;
public class ActivitySelectionProblem {
public static void main(String[] args) {
int[] start = {1, 3, 5, 7, 9, 13};
int[] finish = {4, 5, 7, 9, 12, 15};
// 활동 개수
int n = start.length;
int i=0;
int count=0;
// 다음 활동 시작 시간이 이전 활동의 끝나는 시간보다 클 경우를 구해야 하므로 j=1
for(int j=1; j<n; j++){
if (start[j] >= finish[i]){
System.out.println(String.format("%d~%d", start[i], finish[i]));
i = j;
count++;
}
}
// 마지막 시간은 반복문에서 제외됨
if (start[i] >= finish[i-1]){
System.out.println(String.format("%d~%d", start[i], finish[i]));
count+=1;
}
System.out.println("최대 활동 개수 : " + count);
}
}
오른쪽으로 가는것을 기준으로 잡고 풀었다. 좌, 우 이동만 가지고 얘기하자면, 현재 위치를 기준으로 왼쪽/오른쪽 거리를 계산했을 때, 한 번이라도 왼쪽 거리가 짧을 경우 name의 끝에서부터 빼면서 계산했다. 다른 사람의 풀이를 보면 엄청 쉽게 구현하던데 신기하다...
탐욕법은 매 순간마다 최적의 값을 찾는다. 탐욕법은 탐욕스러운 선택 조건과 최적 부분 구조 조건을 가지는 특징이 있는데, 탐욕스러운 선택 조건은 앞에서 내가 선택한 것이 이후의 선택에 어떠한 영향을 미치지 않는다는 조건이고 최적 부분 구조 조건은 문제에 대한 최적해가 부분 문제에 대해서도 최적해여야 한다는 특징이 있다.
이 문제에서는 인덱스 0 위치에서 왼쪽으로 갈 경우 문자열의 끝에 갈 수 있지만 문자열의 끝에서 오른쪽으로 갈 경우 인덱스 0위치로 갈 수 없다. 그래서 아래와 같은 결과가 나오게 된다.
ABAAAABAAAAAAAAAAAAB => 최적해 (13) / 실제 계산한 해 (19)
탐욕법 자체가 이미 지나온 길을 되돌아갈 수 없다고 하면 탐욕법이 맞는거 같기도하고.. 아리송하다.
public int solution(String name) {
int answer = 0;
int notA_Count = 0;
int curCount = 0;
int lastIndex = 0;
char curChar = 'A';
boolean leftSmallerThanRight = false;
// A가 아닌 개수 및 A가 아닌 마지막 인덱스 구하기
for(int i=0; i<name.length(); i++){
if (name.charAt(i) != 'A'){
lastIndex = i;
notA_Count++;
}
}
// 오른쪽으로 갈 수 있는 최대 구하기
// 인덱스 0을 기준으로 왼쪽으로 갔을 때 몇번째 값이 A가 아닌지 확인 (0의 위치에서 왼쪽으로 갈 경우 거리값이 +1이 되어야 함)
int leftCount = name.length() - lastIndex;
int rightCount = 0;
int curPos = 0;
int upDownCount = 0;
for(int i=0; i<name.length(); i++){
curChar = name.charAt(i);
if (curChar == 'A'){
continue;
}
// i 위치에서 현재 위치를 빼면 오른쪽으로 몇 번 가야 A가 아닌 문자가 나오는지 알 수 있음
rightCount = i - curPos;
// A가 아닌 문자를 만나기 위해 오른쪽으로 간 횟수와 왼쪽으로 간 횟수를 비교
// 왼쪽으로 간 횟수가 더 적을 경우 빠져나와 맨 오른쪽에서 왼쪽으로 진행하기 위해 빠져나옴
if (rightCount > leftCount + curPos){
leftSmallerThanRight = true;
break;
}
else{
answer += rightCount;
}
// 알파벳 구하기
upDownCount = (curChar - 'A' > 'Z' - curChar + 1)? 'Z' - curChar + 1 : curChar - 'A';
answer += upDownCount;
// 현재 위치를 i번째로 옮김
curPos = i;
rightCount = 0;
curCount++;
}
// 현재 위치에서 왼쪽으로 가는게 더 빠른 경우가 있을 때
// 현재 위치부터 왼쪽으로 구해야 하니까 leftCount는 curPos 값으로 변경
leftCount = curPos;
if (leftSmallerThanRight){
for(int i=name.length() - 1; i>=0; i--){
if (notA_Count == curCount){
break;
}
curChar = name.charAt(i);
// A면 한 칸 이동
if (curChar == 'A'){
leftCount++;
continue;
}
leftCount++;
upDownCount = (curChar - 'A' > 'Z' - curChar + 1)? 'Z' - curChar + 1 : curChar - 'A';
answer += upDownCount;
answer += leftCount;
leftCount = 0;
curCount++;
}
}
return answer;
}
문제는 위와 같은데 단순히 10진수를 124 나라에서 사용하는 숫자로 바꾸는 문제이다. 1,2,4 세 개만 사용한다 했으니 10진수를 3진법으로 변환해봤다.
10진법
3진법
10진법
3진법
1
1
11
102
2
2
12
110
3
10
13
111
4
11
14
112
5
12
15
120
6
20
16
121
7
21
17
122
8
22
18
200
9
100
19
201
10
101
20
202
그리고 3진법과 124나라의 숫자를 비교해봤다.
3진법
124나라
3진법
124나라
1
1
102
42
2
2
110
44
10
4
111
111
11
11
112
112
12
12
120
114
20
14
121
121
21
21
122
122
22
22
200
124
100
24
201
141
101
41
202
142
10진수 6을 3진법으로 변환 시 20이 되는데 이 20는 결국 124 나라의 14라는 숫자가 되어야 한다. 3진법에 의해 10진수 6이 3진수 20이 되었으니 결국 3진법으로 표현하면 13이 될 수 있다는 뜻이다. (3진수 13은 결국 3진수 20이 되므로) 이렇게 되면 3진수 20에서 2는 1이 되어야 하므로 -1 해주고 0은 3으로 바꿔야 한다. 하지만 124 나라에서는 1, 2, 4만 사용하기 때문에 결국 0은 4로 바꿔줘야 124 나라의 숫자가 된다.
풀이순서
1. 전달받은 숫자를 3으로 나눈다.
2. 나머지가 0일 경우 4로 치환하고 몫을 -1 하고 나머지 값을 추가한다.
2-1. 나머지가 0이 아닐 경우 그대로 값을 추가한다.
3. 1번과 2번을 반복해서 숫자가 0이 될 때까지 반복한다.
public String solution(int n) {
StringBuilder sb = new StringBuilder();
int rest = 0;
while(n > 0){
rest = n % 3;
n /= 3;
if (rest == 0){
n -= 1;
rest = 4;
}
sb.insert(0, rest);
}
return sb.toString();
}
