자료구조9 [Python] 자료구조 LinkedList 구현하기 ▏목적 ◦ 자료구조 Linked List 이해하기 ◦ Python으로 Linked List 구현하기 ▏자료구조 Linked List 란? Linked List (연결 리스트)란 크기 변경이 유연한 자료구조다. 때문에 데이터를 자유롭게 삽입 · 삭제할 수 있다는 장점이 있다. 집합의 단위를 List, 각 요소들의 단위를 Node 라고 부른다. LinkedList는 한 줄로 연결된 형태로, 리스트의 첫 번째 노드를 Head (헤드), 마지막 노드를 Tail (테일) 이라고 한다. 각 노드는 1. 데이터의 내용을 담는 부분 2. 다음 노드의 주소값을 지닌 포인터 변수 로 구성되어 있다. LinkedList를 배열과 비교하여 장단점을 살펴보자. 장점 - 삽입, 삭제의 용이성 배열은 index 로 크기가 정해져 .. 2023. 1. 12. LRU 알고리즘이란 무엇인가? ▏목적 ◦ LRU 알고리즘 이해하기 ▏시작하는 말 정처기 자격증 준비했을 때 이론을 공부했었다. 그런데 마침 오늘 프로그래머스에서 문제를 보는데 LRU를 사용해야 하는 문제였다. 그래서 오늘은 그 LRU알고리즘을 설명해보려고 한다. ▏LRU 란 무엇인가? LRU (Least Recently Used) : 가장 오랫동안 참조하지 않은 페이지를 교체하는 기법 페이지 교체 알고리즘들의 종류중 하나로 가장 최근에 사용되지 않은 페이지를 제거하는 알고리즘이다. 대표적인 방법으로 전에 포스팅했던 Queue 형식을 생각하면 된다. ▏원리 크기가 4인 배열이 있다고 가정했을 때, 처음 4번은 들어온 순서대로 넣어주면 된다. 하지만 오른쪽 처럼 숫자 5를 넣으려고 한다면 가장 먼저 넣었던 1 (오래된 데이터)를 제거하고.. 2021. 8. 20. 하노이의 탑이란 무엇인가? ▏목적 ◦ 하노이의 탑 알고리즘 이해하기 ◦ 하노이의 탑 알고리즘 JAVA로 구현하기 ▏시작하는 말 오늘은 하노이의 탑 을 공부해봤다. 이름이 새로워서 내가 모르는 것인 줄 알았으나 어릴적 다들 한 번씩은 해봤던 놀이였다. 가지고 놀았던 게임을 제대로 분석하고 공부해서 코드로 구현해보니 더 재미있고 신기했다. 그럼 이제 그 하노이의 탑을 설명해보도록 하겠다. ▏하노이의 탑 하노이의 탑 규칙은 큰 원반이 아래, 작은 원반이 위로가게 해서 원반을 3개의 기둥사이에서 옮기는 것 이다. 원반은 1번에 1개씩만 옮길 수 있고, 모든 원반은 크기가 다르며 큰 원반이 작은 원반 위로 가서는 안되는 규칙이 있다. 또 최소한의 이동으로 목표 기둥으로 옮겨야 한다. ▏원리 왼쪽 기둥부터 편의상 1, 2, 3번 기둥이라고 .. 2021. 7. 2. 유클리드 호제법 이란 무엇인가? ▏목적 ◦ 유클리드 호제법 알고리즘 이해하기 ◦ 유클리드 호제법 JAVA로 구현하기 ▏시작하는 말 요즘 팀 프로젝트 작업을 하고 있어 알고리즘 공부하는 것이 뜸했다. 그래서 오늘은 일찍부터 일어나 공부를 시작해봤다. 오늘 공부한 것은 유클리드 호제법이란 알고리즘으로 최대공약수를 재귀적으로 구하는 방법이다. 예전에 내가 최대공약수 문제를 풀 때 정사각형으로 만드는 방법을 얼핏 봤었는데 그것을 오늘 제대로 공부했고 이제 설명해보려고 한다. 오늘도 역시 직접 그림판으로 그린 것이라 비율이 정확히 맞지는 않는것을 유념하고 봐줬으면 좋겠다. ▏유클리드 호제법 각 변의 길이가 22 와 8인 직사각형으로 예를 들어 설명해보겠다. 위 도형에서 짧은 변(8)을 한 변으로 하는 정사각형으로 나누면 8 x 8 정사각형 2개.. 2021. 7. 1. 검색(탐색) 알고리즘 이란 무엇인가? ▏목적 ◦ 검색 알고리즘 이해하기 ▏시작하는 말 알고리즘 공부를 하기 위하여 프로그래머스 Lv 2문제들을 꾸준히 하루에 한 문제씩 풀어나가는 중이다. 나는 알고리즘을 따로 배워본 적 없이 JAVA의 기초 지식만 있었기 때문에 1 / 3 정도 풀고 나니 남은 문제들은 구현은 해도 효율성이 좋지 않거나 손쉽게 풀 수 없는 문제들만 남았다. 때문에 나는 제대로 된 알고리즘 개념부터 공부해야겠다는 생각을 했다. 그래서 오늘부터 알고리즘 하나씩 공부한 후 이 블로그에 정리해보려고 한다. 오늘 공부한 것은 검색알고리즘으로 선형 검색과 이진 검색이다. ▏정의 선형 검색 : 무작위로 늘어놓은 데이터 집합 일 때 적절한 검색 알고리즘 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합 일 때 적절한 검색 알고리즘 해시법.. 2021. 6. 18. 큐(Queue) 란 무엇인가? ▏큐(Queue) 큐는 스택과 반대로 FIFO(First-In-Last-Out) 즉, 선입선출 구조로 생각하면 된다. 다시 말하면, 한 쪽 끝에서 삽입이 이루어지고 반대쪽에서 삭제가 이루어지는 구조이다. 따라서 주로 데이터가 입력된 시간순대로 처리해야 할 경우에 사용된다. 큐에 값 추가 하는것을 Enqueue 라 하고, 값 삭제하는 것을 Dequeue 라 한다. ▏Queue연산 add() / offer() : 큐에 값을 추가한다. remove() : 큐에 가장 앞쪽에 있는 항목을 제거한다. poll() : 큐에 첫번째 값을 반환한 후 제거한다. (비어있다면 null) clear() : 큐에 모든 요소를 제거한다. isEmpty() : 큐가 비어있으면 True 아니면 False ▏참고자료 Queue를 활용.. 2021. 6. 1. 스택(Stack)이란 무엇인가? ▏목적 ◦ Stack 이해하기 ▏시작하는 말 스택 · 큐에 대한 개념을 알지 못하고 알고리즘 문제를 풀었던 적이 있었다. 도저히 해결법을 몰랐었는데 지인이 큐로 풀면 된다고 했었던 기억이 있다. 그 때 큐를 처음 알게 되었다. 하지만 정확한 개념을 이해하지 못한채로 넘어갔었다. 올 해 초, 정보처리산업기사 자격증을 취득하였고 그 과정에서 스택 · 큐 자료구조를 제대로 공부하게 되었다. 그래서 오늘 그 개념에 대해 설명해보려고 한다. 스택 · 큐 포스팅 모두 내가 직접 그림판에서 그린 것이라 그림들이 조금 엉성할 수 있다. ▏스택(Stack) 스택은 LIFO(Last-In-First-Out) 즉, 후입선출 구조로 생각하면 된다. 쉽게 말해서, 차곡차곡 쌓아올리는 개념으로 보면 된다. 삽입 삭제 모두 Top.. 2021. 5. 31. JAVA 로 다익스트라 구현하기 | 목적 ◦ 다익스트라 알고리즘 Java로 구현하기 | 시작하는 말 다익스트라의 개념, 순서가 이해가 안된다면 다익스트라란 무엇인가 이 포스트를 먼저 보고 오면 좋다. | 초기 설정 다익스트라를 만들기에 앞서 변수 두가지를 설정해줘야 한다. distance변수는 각 노드에 갈 수 있는 최단거리를 저장한다. visit변수는 해당 노드를 방문 했는지를 체크할 변수다. int distance[] = new int[N]; //최단거리들을 저장할 배열을 만든다. boolean visit[] = new boolean[N]; //해당노드 방문여부를 체크할 배열을 만든다. | 예제 (JAVA) public class Dijkstra { private static int n; private static int maps[.. 2021. 5. 13. 다익스트라(Dijkstra)란 무엇인가? ▏목적 ◦ 다익스트라 알고리즘 이해하기 ▏시작하는 말 프로그래머스에서 "배달"이라는 문제를 풀어보았는데, 이런 유형의 문제는 처음 접해봐서 그런지 어떻게 풀어야 할지 감조차 오지 않았다. 그래서 구글에서 여러 알고리즘들을 살펴보다 최단거리를 구하는 다익스트라를 알게 되었다. 이 방법이라면 이 문제를 해결 할 수 있을 것 같아 다익스트라를 충분히 이해하고, 다시 풀어보았는데 손쉽게 풀었다. 완벽히 다익스트라를 알게된 지금, 내가 직접 문제를 만들어 설명해보려 한다. ▏다익스트라(Dijkstra) 란 무엇인가? 다익스트라는 최단거리를 탐색하는 방법이다. 쉽게 말해 특정한 한 점에서 다른 모든 점까지 가는 경로의 최소를 구하는 것이다. 이것의 가장 큰 특징은 한 점 까지의 최단거리를 구할 때 그 전까지 구한 .. 2021. 5. 11. 이전 1 다음 반응형
