오늘 학습한 자료구조 🧐
-
🦁 Linked List
: 자바의 Linked List는 ArrayList와 같이 인덱스로 접근하여 조회, 삽입이 가능하지만
내부 구조는 완전히 다르게 구성되어 있다는 점이 특징이다. Linked List는 노드(객체)
끼리의 주소 포인터를 서로 가리키며 링크(참조)함으로써 이어지는 구조로 되어 있다.: Linked List의 종류에는 단방향 연결 리스트, 양방향 연결 리스트, 양방향 원형 연결
리스트가 있지만 나는 "단방향 연결 리스트" 를 코드로 구현해봤다.// ✅ 노드 클래스 생성 public class Node { Integer data; Node next; public Node(Integer data, Node next) { this.data = data; this.next = next; } }
// ✅ LikedList 클래스 생성 public class LinkedList { Node head; // 맨 처음 노드 Node current; // 현재 위치 노드 // 생성자 public LinkedList() { this.current = null; this.head = null; } // ✅ 데이터를 맨처음에 추가하는 기능 public void insertFirst(Integer data) { if(this.head == null) { Node node1 = new Node(data, null); this.head = node1; } else { Node node1 = new Node(data, this.head); this.head = node1; } } // ✅ 데이터를 맨 마지막에 추가하는 기능 public void insertLast(Integer data) { current = head; if(current == null) { this.insertFirst(data); } else { while (true) { if (current.next == null) { Node node2 = new Node(data, null); current.next = node2; current = current.next; break; } else { current = current.next; } } } } // ✅ 데이터를 원하는 순서에 추가하는 기능 public void insertIndex(Integer data, Integer index) { current = head; for(int i=0; i<index-2; i++) { current = current.next; } Node node3 = new Node(data, current.next); current.next = node3; node3.next = current.next.next; } // ✅ 맨 처음 노드를 삭제하는 기능 public void removeFirst() { if(head != null) { head = head.next; } } // ✅ 맨 마지막 노드를 삭제하는 기능 public void removeLast() { if(head != null) { current = head; while(true) { if(current.next.next == null) { current.next = null; break; } current = current.next; } } } // ✅ 원하는 순서의 노드를 삭제하는 기능 public void removeIndex(Integer index) { if(head != null) { current = head; for(int i=0; i<index-2; i++) { current = current.next; } current.next = current.next.next; } } // ✅ 출력 기능 public void display() { current = head; while (current != null) { System.out.print(current.data); if(current.next != null) { System.out.print(" -> "); } current = current.next; } System.out.println(); } }
-
작성한 코드를 출력해보면 위와 같이 서로 연결된 Liked List 형태의 결과가 나오는 것을 볼 수 있었다.
-
Liked List를 코드로 구현하면서 가장 중요했던 것은 노드와 노드 사이의 연결이었던 것 같다. 연결을 어떻게 설정해 줄 것인지와 연결을 끊고 다른 노드로 연결을 해주는 등 그 부분을 이해하면 코드로 구현하는것은 크게 어렵지 않았다.
-
🐱 이진 탐색 트리
: 이진 탐색 트리는 이진 트리에서 자료의 탐색, 삽입, 삭제를 효율적으로 하기 위해 만들어진 트리이다.: 이진 탐색 트리에서의 탐색 연산은 루트 노드를 기점으로 찾고자 하는 값의 크기에 따라
왼쪽 서브 트리나 오른쪽 서브 트리로 이동하여 노드를 탐색한다. 예를 들어, 현재
노드의 값보다 찾는 값이 크면 오른쪽 서브 트리에서 탐색을 진행하고 값이 작다면
왼쪽 서브 트리에서 검색을 진행한다.: 검색은 재귀적인 방법과 반복적인 방법으로 구현이 가능하며 나는 반복문을 사용하여
구현해봤다. 동작순서는 아래의 그림과 같다.
// ✅ 노드 클래스 생성
public class Node {
Integer data;
Node left;
Node right;
public Node(Integer data) {
this.data = data;
this.left = null;
this.right = null;
}
}// ✅ 이진탐색트리 클래스 생성
public class BinarySearchTree {
// 이진 탐색 트리 구현
// 추가할 데이터가 기존 데이터 보다 크면 오른쪽, 작으면 왼쪽에 추가
Node root; // 루트 노드
Node current; // 현재 노드
public BinarySearchTree() {
this.root = null;
}
// ✅ 데이터 추가 기능
public void add(Integer data) {
current = root;
if(root == null) {
Node node = new Node(data);
root = node;
} else {
Node node = new Node(data);
// current가 null 이 아닐때까지 반복한다
while(current != null) {
// 만약 추가하려는 data가 current 데이터보다 크다면
if(data > current.data) {
// 만약 이동한 current에 데이터가 없으면
if(current.right == null) {
// current의 오른쪽에 새로운 node를 추가한다.
current.right = node;
break;
// 그렇지 않다면
} else {
// current를 오른쪽으로 이동시킨다.
current = current.right;
}
}
// 만약 추가하려는 data가 current 데이터보다 작다면
else if(data < current.data) {
// 만약 이동한 current에 데이터가 없으면
if(current.left == null) {
// current의 왼쪽에 새로운 node를 추가한다.
current.left = node;
break;
// 그렇지 않다면
} else {
// current를 왼쪽으로 이동시킨다.
current = current.left;
}
}
}
}
}
}-
일단 데이터를 추가하는 기능만 오늘은 구현해봤는데, 내일 수업 시 추가적으로 다른 기능들고 구현할 예정이다.
-
여기서 중요했던것은 반복문을 돌때의 조건이었다. 처음에 조건을
current != null이라고 부여했었는데, 제대로 데이터가 추가되지 않았었다. 그 이유를 생각해보니current가 아니라current.right또는current.left가 null 이 아닌것으로 해야 조건이 성립된다는것을 깨달았다. -
데이터가 추가된 뒤 출력하는 것은 내일 추가하여 올릴 예정이다. 일단 디버깅으로 확인한 결과 이진 탐색 트리와 동일하게 데이터가 추가된 것까지는 확인할 수 있었다.
다시 시작한 코딩 테스트 대비 학습 💻
-
자격증 시험이 끝나고 다시 프로그래머스 코딩 테스트 문제들을 풀기 시작했다. 저번에 1주일간 실시한 매일 5개 챌린지는 학원 종료 후 스프링 학습으로 인해 실시하지 못하여, 학원에서 쉬는시간 및 점심 시간 등을 활용하여 매일 풀 수 있는 만큼 풀어보려고 한다.
🐮 시저 암호
어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 한다. 예를 들어 "AB"는 1만큼 밀면 "BC"가 되고, 3만큼 밀면 "DE"가 됩니다. "z"는 1만큼 밀면 "a"가 될때 문자열 s와 거리 n을 입력받아 s를 n만큼 민 암호문을 만드는 함수, solution을 완성하라.class Solution { public String solution(String s, int n) { String answer = ""; char[] arr = s.toCharArray(); for(int i=0; i<s.length(); i++) { if(arr[i] == ' ') { arr[i] = ' '; } else if ( (int)arr[i] >= 65 & (int)arr[i] <= 90) { if( (int)arr[i] + n > 90 ) { arr[i] = (char)((int)arr[i] + n - 26); } else { arr[i] = (char)((int)arr[i] + n); } } else if( (int)arr[i] >= 97 & (int)arr[i] <= 122) { if( (int)arr[i] + n > 122 ) { arr[i] = (char)((int)arr[i] + n - 26); } else { arr[i] = (char)((int)arr[i] + n); } } answer += arr[i]; } return answer; } } -
이 문제는 문자의 아스키 코드 숫자를 이용하여 풀어 봤다. 아스키 코드 값을 비교하여 대문자와 소문자로 나눠 반복문을 돌렸다.
🐼 숫자 문자열과 영단어
네오와 프로도가 숫자놀이를 하고 있다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임이다.
다음은 숫자의 일부 자릿수를 영단어로 바꾸는 예시이다.
1478 → "one4seveneight"
234567 → "23four5six7"
10203 → "1zerotwozero3"
이렇게 숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어질때, s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성하라.class Solution { public int solution(String s) { Integer answer = 0; String[] str = {"zero", "one", "two", "three", "four", "five", "six", "seven","eight","nine"}; for(int i=0; i<10; i++) { s = s.replace(str[i], Integer.toString(i)); } answer = Integer.valueOf(s); return answer; } } -
이 문제는 배열을 이용하여 손쉽게 풀 수 있었다. 문자열의 "replace" 메서드와 자료형 타입 변경 하는 "valueOf" 메서드 등을 활용해봤다.
🐨 가장 가까운 같은 글자
문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶다.
예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있다.
b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현.
a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현.
n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현.
a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현.
n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현.
a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현.
따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2] 가 된다.
문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성하라.class Solution { public int[] solution(String s) { int[] answer = new int[s.length()]; char[] arr = s.toCharArray(); answer[0] = -1; int diff = -1; for(int i=1; i<arr.length; i++) { for(int j=0; j<i; j++) { if(arr[i] == arr[j]) { diff = j; } } if(diff != -1) { answer[i] = i-diff; diff = -1; } else if(diff == -1) { answer[i] = -1; diff = -1; } } return answer; } }
-
이 문제는 이중 for 문을 이용하여 손쉽게 풀 수 있었다. 이 문제만 봐도 나오는 문제들이 레벨1 기준으로는 방식이 거의 비슷하다는것을 조금씩 느끼고 있다. 대부분의 문제들이 문자열에서 사용할 수 있는 메서드와 배열, 반복문, 리스트로 풀 수 있었다.
-
가장 중요한 것은 풀어나갈때 내가 사용할 메서드를 기억하고 있어야 되는 것 같다. 지금은 아직 써야할 메서드를 생각은 하지만 완벽히 암기를 못하고 있어 문법 정리한 파일을 볼때가 많은데, 코딩 테스트를 위해서는 자주 쓰는 문법들은 암기를 조금씩이라도 해놔야 겠다.
오늘의 느낀점 👀
-
오늘은 자료구조 2일차 되는 날이다. Linked List 와 Tree 에 대해서 코드로 구현을 해봤는데, 하면 할 수록 객체지향 개념과 코딩 개념이 조금씩 잡혀가는 것 같다. 특히 조금 헤매는 것이 있을때 옆자리 짝꿍이 내가 올바른 길로 생각할 수 있도록 조금씩 도움을 주는데 그것또한 나에게는 큰 도움이 되고 있다.
-
오늘 실시한 실습들도 나혼자서 구현을 해낼 수 있었고, 코드 자체는 복잡할 수 있어도 구현해냈단 거에 의의를 두려고 한다.
-
앞으로 6일 정도 남았는데, 이 시간동안 코딩 실력을 많이 길러야 겠다고 생각이 든다.
