오늘 학습한 자료구조 🧐
-
🐶 스택 (Stack)
: 스택은 가장 마지막에 저장된 데이터가 가장 먼저 삭제되는 후입선출(LIFO : List In First Out) 구조이다. 따라서 스택은 한쪽 방향에서만 데이터의 삽입과 삭제가 가능하다.: 스택에 데이터를 저장, 삭제하는 등의 기능을 아래와 같이 코드로 구현해봤다.
package stack;
public class Stack {
private int size; // 스택의 크기를 지정
private Integer[] stack; // null 값을 저장할 수 있는 Wrapper 클래스
public Stack(int size) {
this.size = size;
stack = new Integer[size]; // 입력받은 크기 만큼의 stack 배열 객체를 생성
}
private int top = -1; // 숫자를 어디까지 저장했는지 가리키는 변수 top 생성
boolean flag;
// ✅ 스택이 비어있는지 확인
boolean isEmpty() {
if(this.top == -1) {
flag = true;
System.out.println("스택이 비어있습니다.");
} else {
flag = false;
System.out.println("스택이 비어있지 않습니다.");
}
return flag;
}
// ✅ 스택이 꽉차 있는지 확인
boolean isFull() {
if(this.top == this.size-1) {
flag = true;
System.out.println("스택이 꽉차 있습니다.");
} else {
flag = false;
System.out.println("스택이 꽉차 있지 않습니다.");
}
return flag;
}
// ✅ 제일 마지막에 저장된 데이터 반환
int peek() {
return stack[this.top];
}
// ✅ 스택에 데이터를 저장 (push)
public void push(int data) {
if(this.top != size-1) {
this.top = this.top + 1;
stack[this.top] = data;
}
}
// ✅ 스택에 저장된 데이터를 삭제 (pop)
int removeNum;
int pop() {
if(this.top != -1) {
stack[this.top] = removeNum;
stack[this.top] = null;
this.top = top - 1;
}
return removeNum;
}
// ✅ 스택에 저장된 데이터를 출력
public void display() {
for(int i=0; i<this.size; i++) {
if(stack[i] != null) {
System.out.print("[" + stack[i] + "]");
} else {
System.out.print("[null]");
}
System.out.print(" ");
}
System.out.println();
}
}-
🐰 큐(Queue)
: 큐는 위에서 설명한 스택과는 달리 한쪽에서 데이터를 삽입하고, 다른쪽에서 데이터의 삭제가 이루어지는 선입선출(FIFO : First In First Out) 구조를 가지고 있다.: 큐에는 "우선순위 큐"와 "원형 큐"가 있는데, 아래에서 "원형 큐"를 코드로 구현해봤다.
package queue;
public class Queue {
private Integer[] queue; // 큐 객체 생성
private Integer front; // 큐의 가장 앞
private Integer rear; // 큐의 가장 뒤
private Integer num=0; // 큐에 저장된 데이터 수
public Queue(Integer size) {
this.queue = new Integer[size];
this.front = 0;
this.rear = 0;
}
// ✅ 큐가 비어있는지 확인
Boolean isEmpty() {
if(this.num == 0) {
return true;
} else {
return false;
}
}
// ✅ 큐가 가득찼는지 확인
Boolean isFull() {
if(this.num == this.queue.length) {
return true;
} else {
return false;
}
}
// ✅ 큐에 데이터를 저장하는 연산
// rear 값이 큐의 크기와 같으면 rear 를 0으로 초기화시켜준다.
public void enQueue(Integer data) {
if(isFull() == true) {
System.out.println("큐가 가득찼습니다.");
} else if (this.rear == this.queue.length) {
this.rear = 0;
this.queue[this.rear] = data;
this.rear = this.rear + 1;
this.num = this.num + 1;
} else {
this.queue[this.rear] = data;
this.rear = this.rear + 1;
this.num = this.num + 1;
}
}
// ✅ 큐에 저장된 데이터를 삭제하는 연산
// front 값이 큐의 크기와 같으면 front 를 0으로 초기화시켜준다.
public void deQueue() {
if(isEmpty() == true) {
System.out.println("큐가 비어있습니다.");
} else if(this.front == this.queue.length){
this.front = 0;
Integer removeNum = this.queue[this.front];
this.queue[this.front] = null;
this.front = this.front + 1;
this.num = this.num - 1;
} else {
Integer removeNum = this.queue[this.front];
this.queue[this.front] = null;
this.front = this.front + 1;
this.num = this.num - 1;
}
}
// ✅ 큐에 저장된 데이터를 출력
public void display() {
for(int i=0; i<this.queue.length; i++) {
if(this.queue[i] != null) {
System.out.print("[" + this.queue[i] + "]");
} else {
System.out.print("[null]");
}
System.out.print(" ");
}
System.out.println();
}
}-
🐸 유클리드 호제법 (Euclidean Algorithm)
: 유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘이다. 원리는 두 수 중에서 큰수를 작은수로 나누고,"나눈 나머지가 0이 아닐때"다시 작은수와 이전에서 나눈 나머지를 나누고를 반복하여,"나머지가 0일때"마지막에 나눌때 사용한 숫자가 두 수의 최대 공약수가 된다는 원리이다.: 이것을 재귀함수를 사용하여 아래와 같이 구현하였다.
package Factorial;
public class Factorial {
Integer result; // 최대공약수를 저장할 변수
public Integer euclid(Integer num1, Integer num2) {
if(num1 >= num2) {
if(num1 % num2 == 0 ) {
this.result = num2;
} else {
euclid(num2, num1%num2);
}
} else {
if(num2 % num1 == 0) {
this.result = num1;
} else {
euclid(num1, num2 % num1);
}
}
return result;
}
public void display() {
System.out.println(this.result);
}
}-
🐻 하노이의 탑
: 하노이의 탑은 프랑스 수학자 에두아르드가 처음으로 발표한 게임으로 3개의 기둥과
기둥에 꽂을 수 있는 N개의 원판으로 이루어져 있다.: 이 게임의 규칙은 아래와 같다.
1) 처음에 모든 원판은 1, 2, 3번 기둥 중 한개의 기둥에 꽂혀 있다.
2) 모든 원판의 지름은 다르다.
3) 이 원반은 세 개의 기둥 중 하나에 반드시 꽂혀야 한다.
4) 작은 원반 위에 큰 원반을 놓을 수 없다.
5) 한 번에 하나의 원판(가장 위에 있는 원판) 만을 옮길 수 있다.
6) 이 규칙을 만족하며 한개의 기둥에 있는 원반 N개를 모두 다른 한개의 기둥으로
옮기기 위해서 실행되어야 할 원반의 최소 이동 횟수를 구한다.: 나는 재귀함수를 이용하여 아래와 같이 코드를 구현할 수 있었다.
package hanoi;
public class Hanoi {
Integer cnt = 0; // 원반을 옮깃 횟수
// 이동(원반 번호와 몇번 기둥에서 몇번기둥으로 옮길지를 입력받는다.)
// 원반 번호가 1보다 크면 원반 번호 -1을 from에서 from과 to가 아닌 곳으로 이동
// 원반 번호를 from에서 to로 옮겼다고 출력
// 원반 번호가 1보다 크면 원반 번호 -1을 from과 to가 아닌 곳에서 to로 이동
public void move(Integer number, Integer from, Integer to) {
if(number > 1) {
move(number-1, from, 6-from-to);
this.cnt++;
}
System.out.println("["+number+"]번 원반을 "+from+"번 기둥에서 " +to +"번 기둥으로 옮김");
if(number > 1) {
move(number-1, 6-from-to, to);
this.cnt++;
}
}
// 원반을 옮긴 총 횟수를 출력
public void count() {
this.cnt++; // 원반번호가 1일때 옮긴 횟수를 1 더해줌
System.out.println("총 이동 횟수 : " + this.cnt);
}
}- 코드를 실행하면 아래와 같이 결과가 출력되는 것을 볼 수 있었다.
오늘의 느낀점 👀
-
오늘부터 8일간 자료구조와 알고리즘에 대해서 배우는 시간을 갖는다. 자료구조와 알고리즘은 사실상 코딩테스트를 위한 것이라고 생각한다. 얼마나 생각을 폭넓게 창의적으로 할 수 있는지도 문제를 해결하는데 있어서 중요하다고 생각한다.
-
사실상 코드로 구현하는데 복잡하게 작성할 필요도 없고, 어려운 문법을 사용하는것도 아니었다. 다만, 어떻게 구현할지에 대한 생각을 하는것이 90%를 차지하는것 같다.
-
코딩테스트도 취업에 있어서 중요한 요소라 생각하기 때문에 8일간 최대한 스스로 해결해보기 위해 노력할 예정이다.
-
저번주 토요일에 준비중이었던 자격증 시험이 끝났다. 이제는 부트캠프 수업, 그리고 백엔드 개발자로서의 공부에만 전념할 수 있게 된 만큼 더욱더 본격적으로 학습을 해나갈 계획이다.😎
