[백준] 스택 수열_1874_자바개발/DS&Algorithms / 2022. 6. 11.스택 수열 (1874) 이번 포스팅은 백준의 1874번 문제 [스택 수열]에 대해서 다루려고 합니다. 이름에서도 알 수 있듯이 문제의 분류는 스택에 해당합니다. 아래에 해당 문제에 대한 내용이 적혀있는데요. 상당히 애매하게 적혀있습니다. 그래서인지 문제를 이해하는데 어려움을 느낄 수 있습니다. 아래 풀이에서 자세하게 알아보도록 하겠습니다. https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. ww..
[자료구조] 힙(Heap) 알아보기개발/DS&Algorithms / 2022. 4. 14.안녕하세요😊 오늘은 힙(Heap)에 대해서 포스팅하도록 하겠습니다. 힙(Heap) 힙(Heap) 자료구조는 완전 이진트리를 기초로 하며, 우선순위 큐를 위해 만들어진 자료구조입니다. 힙 자료구조를 사용하면 최댓값과 최솟값을 빠르게 찾을 수 있습니다. 보통 배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(N)이 걸립니다. 하지만 Heap은 O(logN)만 발생하게 됩니다. 자세한 것은 뒤에서 알아보도록 하겠습니다. 배열을 통해 [최댓값과 최솟값을 구하는 알고리즘]은 아래 링크를 참고해주세요. https://kang-james.tistory.com/entry/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-JAVA%EB%A1%9C-%ED%91%B8%EB%8A%94-%E..
[자료구조] 트리(Tree) 알아보기 (feat.이진 탐색 트리)개발/DS&Algorithms / 2022. 4. 13.안녕하세요 이번 게시글에서는 자료 구조 트리(Tree)에 대해서 알아보도록 하겠습니다. 트리(Tree) 트리(Tree)란, 노드들이 나무 가지처럼 연결된 비선형 계층형 자료구조입니다. 아래 그림과 같이 트리 자료구조는 나무를 뒤집은 모양과 유사합니다. 따라서 가장 위에 있는 노드를 Root(뿌리) 노드라고 합니다. 이러한 트리는 탐색(검색) 알고리즘 구현을 위해 많이 사용됩니다. 01. 트리의 종류 02. 알아둘 용어 Node : 트리에서 데이터를 저장하는 기본 요소 (노드에는 다른 연결된 노드에 대한 Branch 정보가 포함) Branch : 간선(edge)라고도 하며, 노드와 노드를 연결하는 선 Root Node : 트리에서 가장 위에 있는 노드 Level : 최상위 노드를 Level 0이라고 했을 ..
[자료구조] 해시(HASH) 알아보기개발/DS&Algorithms / 2022. 4. 7.안녕하세요!? 이번 게시글에서는 자료구조 중 해시에 대해서 정리하도록 하겠습니다. 해시는 저장 또는 검색 등에서 자주 활용되는 자료구조입니다. 정확하게는 특정한 함수(알고리즘)를 통해서 값을 추출하고 활용하는 것인데요. 함수(알고리즘)를 어떻게 구현하는지에 따라 사용 용도와 성능이 달라집니다. 이러한 해시는 더 나아가서 암호, 블록체인, 메시지 인증 코드 등에서도 활용됩니다. 해시(Hash) 해시(Hash)는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 말합니다. 다른 말로는 '해시 값(Hash value), 해시 코드, 체크섬' 이라고도 합니다. 이러한 해시는 뒤에서 알아볼 '해시 함수'에 의해서 얻게 됩니다. 간단하게 말하자면, 데이터의 KEY 값이 해시 함수를 통해서 변환된 간단한 정수입니다...
[자료구조] 연결 리스트(Linked List) 알아보기개발/DS&Algorithms / 2022. 4. 1.이번 게시글에서는 연결 리스트에 대해서 알아보도록 하겠습니다. 또 다른 말로는 링크드 리스트라고도 합니다. 이러한 연결 리스트에는 단일 연결 리스트와 이중 연결 리스트로 두 가지 방식이 있는데요. 단일 연결 리스트의 단점을 보완하기 위해 이중 연결 리스트가 나왔다고 생각해도 좋습니다. 이제 자세하게 알아보도록 하겠습니다. 01. 단일 연결 리스트(Single Linked List) 링크드 리스트는 데이터들을 저장하기 위해 사용되는 자료구조입니다. 배열과 다르게 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 구조입니다. 그 중 단일 연결 리스트 또는 Single Linked List는 데이트들이 한쪽 방향으로만 연결되어 있습니다. 1) 기본 구조와 용어 노드 (Node) : 데이터 저장 단위(데..
[자료구조] 큐(Queue)와 스택(Stack) 알아보기개발/DS&Algorithms / 2022. 3. 30.이번 게시글에서는 큐와 스택에 대해서 알아보도록 하겠습니다. 01. 큐(Queue) 큐(Queue)는 자료 구조의 한 가지로, 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In, First Out) 구조로 저장하는 형식을 말합니다. 또 다르게 큐는 줄을 서는 행위와 유사하다고 할 수 있습니다. FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식 1) Queue의 기능 Enqueue : 큐에 데이터를 넣는 기능 Dequeue : 큐에서 데이터를 꺼내는 기능 2) Queue의 메서드 메서드 설명 boolean add(Object o) 지정된 객체를 Queue에 추가 - 성공하면 true 반환 - 저장공간이 부족하면 IllegalStateExcepti..
[백준] 스택 수열_1874_자바
개발/DS&Algorithms
/ 2022. 6. 11.
스택 수열 (1874) 이번 포스팅은 백준의 1874번 문제 [스택 수열]에 대해서 다루려고 합니다. 이름에서도 알 수 있듯이 문제의 분류는 스택에 해당합니다. 아래에 해당 문제에 대한 내용이 적혀있는데요. 상당히 애매하게 적혀있습니다. 그래서인지 문제를 이해하는데 어려움을 느낄 수 있습니다. 아래 풀이에서 자세하게 알아보도록 하겠습니다. https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. ww..
[자료구조] 힙(Heap) 알아보기
개발/DS&Algorithms
/ 2022. 4. 14.
안녕하세요😊 오늘은 힙(Heap)에 대해서 포스팅하도록 하겠습니다. 힙(Heap) 힙(Heap) 자료구조는 완전 이진트리를 기초로 하며, 우선순위 큐를 위해 만들어진 자료구조입니다. 힙 자료구조를 사용하면 최댓값과 최솟값을 빠르게 찾을 수 있습니다. 보통 배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(N)이 걸립니다. 하지만 Heap은 O(logN)만 발생하게 됩니다. 자세한 것은 뒤에서 알아보도록 하겠습니다. 배열을 통해 [최댓값과 최솟값을 구하는 알고리즘]은 아래 링크를 참고해주세요. https://kang-james.tistory.com/entry/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-JAVA%EB%A1%9C-%ED%91%B8%EB%8A%94-%E..
[자료구조] 트리(Tree) 알아보기 (feat.이진 탐색 트리)
개발/DS&Algorithms
/ 2022. 4. 13.
안녕하세요 이번 게시글에서는 자료 구조 트리(Tree)에 대해서 알아보도록 하겠습니다. 트리(Tree) 트리(Tree)란, 노드들이 나무 가지처럼 연결된 비선형 계층형 자료구조입니다. 아래 그림과 같이 트리 자료구조는 나무를 뒤집은 모양과 유사합니다. 따라서 가장 위에 있는 노드를 Root(뿌리) 노드라고 합니다. 이러한 트리는 탐색(검색) 알고리즘 구현을 위해 많이 사용됩니다. 01. 트리의 종류 02. 알아둘 용어 Node : 트리에서 데이터를 저장하는 기본 요소 (노드에는 다른 연결된 노드에 대한 Branch 정보가 포함) Branch : 간선(edge)라고도 하며, 노드와 노드를 연결하는 선 Root Node : 트리에서 가장 위에 있는 노드 Level : 최상위 노드를 Level 0이라고 했을 ..
[자료구조] 해시(HASH) 알아보기
개발/DS&Algorithms
/ 2022. 4. 7.
안녕하세요!? 이번 게시글에서는 자료구조 중 해시에 대해서 정리하도록 하겠습니다. 해시는 저장 또는 검색 등에서 자주 활용되는 자료구조입니다. 정확하게는 특정한 함수(알고리즘)를 통해서 값을 추출하고 활용하는 것인데요. 함수(알고리즘)를 어떻게 구현하는지에 따라 사용 용도와 성능이 달라집니다. 이러한 해시는 더 나아가서 암호, 블록체인, 메시지 인증 코드 등에서도 활용됩니다. 해시(Hash) 해시(Hash)는 입력 데이터를 고정된 길이의 데이터로 변환된 값을 말합니다. 다른 말로는 '해시 값(Hash value), 해시 코드, 체크섬' 이라고도 합니다. 이러한 해시는 뒤에서 알아볼 '해시 함수'에 의해서 얻게 됩니다. 간단하게 말하자면, 데이터의 KEY 값이 해시 함수를 통해서 변환된 간단한 정수입니다...
[자료구조] 연결 리스트(Linked List) 알아보기
개발/DS&Algorithms
/ 2022. 4. 1.
이번 게시글에서는 연결 리스트에 대해서 알아보도록 하겠습니다. 또 다른 말로는 링크드 리스트라고도 합니다. 이러한 연결 리스트에는 단일 연결 리스트와 이중 연결 리스트로 두 가지 방식이 있는데요. 단일 연결 리스트의 단점을 보완하기 위해 이중 연결 리스트가 나왔다고 생각해도 좋습니다. 이제 자세하게 알아보도록 하겠습니다. 01. 단일 연결 리스트(Single Linked List) 링크드 리스트는 데이터들을 저장하기 위해 사용되는 자료구조입니다. 배열과 다르게 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 구조입니다. 그 중 단일 연결 리스트 또는 Single Linked List는 데이트들이 한쪽 방향으로만 연결되어 있습니다. 1) 기본 구조와 용어 노드 (Node) : 데이터 저장 단위(데..
[자료구조] 큐(Queue)와 스택(Stack) 알아보기
개발/DS&Algorithms
/ 2022. 3. 30.
이번 게시글에서는 큐와 스택에 대해서 알아보도록 하겠습니다. 01. 큐(Queue) 큐(Queue)는 자료 구조의 한 가지로, 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In, First Out) 구조로 저장하는 형식을 말합니다. 또 다르게 큐는 줄을 서는 행위와 유사하다고 할 수 있습니다. FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식 1) Queue의 기능 Enqueue : 큐에 데이터를 넣는 기능 Dequeue : 큐에서 데이터를 꺼내는 기능 2) Queue의 메서드 메서드 설명 boolean add(Object o) 지정된 객체를 Queue에 추가 - 성공하면 true 반환 - 저장공간이 부족하면 IllegalStateExcepti..