[JAVA]

들어가기 전. Stack 이나 Queue 는 이전 자료구조 수업에서 설명한 바가 있으니 가볍게 넘어가겠습니다.2024.04.11 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 5 - Queue and Stack 0. Stack 스택은 컴퓨터에서 아주 많이 사용되는 자료구조입니다. 예를 들어, 웹 사이트의 "뒤로 가기" 기능, 가까이는 IDE 에서 Undo 기능 또한 스택으로 구현됩니다. 스택은 말 그대로 쌓아놓은 더미를 뜻합니다. 쉽게 이해하자면 벽돌을 쌓는 것과 유사합니다. 가장 먼저 쌓는 벽돌은 가장 아래에 위치할 것이고, 가장 나중에 들어온 벽돌은 가장 위에 위치할 것입니다. 벽돌을 다 쌓은 후 벽돌을 치운다고 했을 때, 가장 먼저 치워야 하는것은 가장 위에 있는 벽돌, 즉 가장 마지막에 올..

0. 이중 연결 리스트 단일 연결리스트는 다음 노드를 가르키는 포인터 변수를 가지고 있었다면 이중 연결 리스트는 다음 노드 뿐만 아니라 이전 노드를 가르키는 포인터 변수까지 가지고 있는 노드로 이루어져있습니다. 즉 양방향으로 연결 된 리스트를 LinkedList 중에서도 Doubly LinkedList 라고 합니다.  이렇게 되면 단일 연결 노드보다 검색의 성능이 좋아집니다. 만약 10개의 노드가 있고, 9번째 노드를 검색하고 싶다면 단일 연결 노드에서는 head 노드부터 시작하여 거의 모든 노드를 거쳐서 가야합니다. 하지만 이중 연결 리스트는 10번, 9번 노드 단 두 번만에 검색할 수 있습니다.  1. Node 클래스 이전까지 사용되었던 Node 클래스와 달리 이전 노드를 가르키는 래퍼런스 변수 @p..

0. Singly LinkedList (단일 연결 리스트) 단일 연결 리스트는 LinkedList 의 한 종류입니다. 2024.04.19 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 7 - LinkedList 에서 설명한 LinkedList 와 동일한 자료구조입니다. 자세한 설명은 위 글을 보면 되고, 여기에 추가적인 메소드들을 더해 구현해보겠습니다.  1. Node public class Node { E data; Node next; // 다음 노드를 가르키는 래퍼런스 변수 Node(E data){ this.data = data; this.next = null; }}  2. Singly LinkedListimport Interface..

ArrayList ArrayList 는 List Interface 를 implements 하는 클래스입니다. 하지만 다른 List 자료구조들과 달리 배열에 기반을 두고 사용합니다.(다른 자료구조들은 주소를 통해 구현됩니다.) 또한 모든 자료구조는 '동적 할당' 을 전제로 합니다. 만약 ArrayList 를 사용하는데 리스트가 꽉찼다면 리스트의 길이를 늘려줘야 합니다. 이때 크기는 현재 크기의 2배씩 늘립니다.  ArrayList 구현 메소드 2024.04.26 - [자바[JAVA]/자바[JAVA] 자료구조 구현] - 자바[JAVA] 자료구조 구현 1 - List Interface에서 구현한 메소드들을 포함하여toArray() 와 clone() 을 추가해서 작성했습니다.해당 메소드들에 대한 설명은 코드 주..

0. Array and List 배열은 뭐고 리스트는 뭘까? 그리고 배열이 있는데 리스트를 써야하는 이유는 무엇일까?  0.1 Array 배열은 선형적인 자료구조 중의 하나로 데이터를 일렬로 늘여 놓은 형태의 자료구조입니다. 어떤 언어를 배우던 가장 기본적으로 배우게 되는 메모리 공간 형태이며, 자료형(Data Type)이 둘 이상의 값을 저장할 수 없습니다.(다만, Python 제외)  0.2 List 리스트도 배열과 마찬가지로 선형적인 자료구조 중의 하나입니다.  하지만 배열과 달리 길이가 가변적입니다. 이를 동적할당(Dynamic allocation)이라고 합니다. 또한 배열과 달리 메모리 공간상에 연속적으로 나열되어 할당되지 않고 주소(reference) 를 통해 데이터들이 연결되어있는 형태입니다..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 배열로 입력이 들어오고 하나 하나 찾아가는 느낌이 그래프와 BFS 로 풀면 되겠다고 생각했습니다. 토마토는 익은 토마토 주변 상하좌우로 안 익은 토마토들을 익게 만드는 것 또한 BFS 라고 생각했습니다. 여기에서 문제는 끝까지 탐색했을 때 모든 토마토가 안 익는 경우가 생기고 이를 어떻게 일반적인 경우와 구분할 것 인지 탐색이 끝까지 진행 되었을 때 며칠이 지났는지 어떻게 알 수 ..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 리스트를 만들어 요소들을 저장하고 각 명령에 맞게 리스트의 값들을 수정하는 문제입니다. 해당 문제에는 2 가지의 명령이 있습니다. R: 배열의 순서를 뒤집습니다. D: 가장 앞에 요소를 삭제합니다. 만약 배열에 요소가 없을 때, D 명령을 수행하려 하면 error 를 출력하고 아닐 경우는 결과 배열을 출력합니다. 특이한 점은 배열의 요소들을 입력해줄 때 [ ] 를 포함하여 입력해준다는 점 입니다. [ ] 처리를 잘 하는 것이 중요해보입니다. 또한 R 연..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2178 미로 찾기와 비슷한 input 이라서 "DFS BFS 를 활용하면 되지 않을까" 먼저 생각했습니다. 2178 번 문제와 비슷하게 시작하는 노드에서 부터 동 서 남 북으로 이동 가능한데, 한 번 방문한 곳은 더이상 방문하지 않는다. 0이 적혀있는 곳은 방문하지 않는다. 를 지켜가며 DFS 든 BFS 든 해서 노드의 개수를 구하는 방식으로 풀었습니다. 2178 번 문제와 달리 해당 문제에서는 ..