https://www.acmicpc.net/problem/1966 본 글에서는 백준 1966번 프린터 큐 문제의 풀이를 설명하며, 문항 정보는 상단의 백준 링크를 통해 확인할 수 있다.  1. 문제 분석이 문제의 핵심은 문서의 중요도에 따라 큐의 원소를 재배치하는 것이다. 이를 해결하기 위해 본인은 다음과 같은 두 가지 자료구조를 사용하였다:프린트할 순서를 저장하는 큐문서의 중요도를 저장하는 우선순위 큐이 두 가지 큐를 통해 문서의 중요도에 따라 적절한 순서로 문서가 프린트되도록 구현하였다. 2. 코드 설명import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStrea..

1. 개념1.1. 정의연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드의 위치를 나타내는 포인터를 가지며, 이를 통해 연결된 방식으로 데이터를 저장하는 자료구조이다. 1.1.1. 관련 용어노드(Node)데이터 덩어리. 데이터와 포인터로 구성ArrayList와의 가장 큰 차이점포인터(Pointer)다음(혹은 이전) 노드의 위치를 나타냄헤드(Head)링크드 리스트의 첫 번째 노드테일(Tail)링크드 리스트의 마지막 노드링크드 리스트의 마지막 노드에는 null을 가리키는 포인터가 포함되어 이를 확인함으로써 해당 노드가 테일임을 알 수 있음  1.2. 특징1.2.1. 포인터를 통해 연결각 노드에 다음 노드의 주소를 가리키는 포인터를 갖고 있어 모든 요소가 연결된다.배열처럼 요소를 추가, 탐색,..

1. 개념1.1. 정의힙(Heap) 혹은 힙 트리(Heap Tree)는 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 이진트리의 자료구조를 의미한다.영단어 힙(heap)은 "무엇인가를 차곡차곡 쌓아올린 더미"를 의미1.2. 특징A가 B의 부모노드일 시 A의 키값과 B의 키값 사이에 대소관계가 성립한다(형제 관계에서는 성립X)힙은 항상 완전 이진 트리의 형태이기 때문완전 이진 트리 : 트리의 위부터 아래, 오른쪽부터 왼쪽의 순서로 차있는 이진 트리이런 성질 덕분에 최댓값 혹은 최솟값을 O(1) 안에 찾을 수 있음(루트 노드의 값)삽입과 삭제 연산 시 힙 성질 유지 위해 힙 정렬 수행을 수행한다. 1.3. 종류최대힙부모 노드의 값이 자식 노드의 값보다 크거나 같음최소힙부모 노드의 값이 자식 노..

1. 정의1.1. 정의트리(tree)는 계층적인 비선형 자료구조로, 노드(Node)와 그 노드들을 연결하는 간선(Edge)으로 구성된다.트리는 다음과 같은 구조적 특징을 가진다.노드루트 노드(Root Node) : 트리의 시작점. 부모가 없는 최상위 노드자식 노드(Child Node) : 부모 노드에서 뻗어 나온 하위 노드 부모 노드(Parent Node) : 다른 노드를 자식으로 거지는 노드리프 노드(Leaf Node) : 자식이 없는 최하위 노드(말단 노드)이처럼 루트 노드를 중심으로 뻗어나가는 모습이 마치 나무의 구조와 유사하다고 하여 '트리'라는 이름이 붙였다고 한다. 특징노드 간 관계가 부모-자식 관계로 연결되는 계층 구조순환이 없음(자식 노드의 자식이 부모로 연결되지 않음) 1.2. 관련 용어..

1. Queue의 정의1.1. 큐의 정의큐는 자료구조에 삽입(enqueue)된 데이터가 제일 먼저 삭제(dequeue)되는 선입선출(First In First Out; FIFO) 방식의 자료구조이다. 영단어 queue는 본디 표 같은 것을 구매하기 위한 대기열을 의미하는데, 표를 사기 위해 줄을 서는 사람들을 연상하면서 하단의 내용과 그림을 보면 어떤 형태의 자료구조인지 파악하기 쉬울 것이다. 앞서 살펴본 스택과는 달리 먼저 들어온 데이터가 먼저 나가기 때문에 삽입과 삭제가 양방향에서 이루어지는 특성이 있다.1.2. 관련 용어위치rear : 값이 삽입되는 위치(큐의 가장 뒤쪽)front : 값이 제거되는 위치(큐의 가장 앞쪽)주요 연산add : rear 부분에 새로운 데이터를 삽입하는 연산poll : f..

프로그래밍에서 Stack은 두 가지 의미를 가지고 있다:프로그램 실행 시 사용되는 메모리 영역프로그램 실행 중 함수 호출이나 변수 저장을 위해 사용되는 메모리 스택 영역.자료구조로서의 스택후입선출(Last-In, First-Out) 방식으로 데이터를 관리하는 자료구조.본 글에서는 두 번째 의미인 자료구조로서의 스택에 대해 다루고자 한다.  1. Stack의 정의1.1. 스택의 정의 스택은 배열이나 연결 리스트를 사용해서 구현할 수 있는 선형 자료구조로, 삽입과 삭제가 한쪽 끝(top)에서만 이루어진 후입선출(Last-in First-out; LIFO)의 자료구조를 의미한다. 즉, 마지막에 삽입된 데이터가 가장 먼저 삭제되는 형태이다.  1.2. 관련 용어 위치top : 삽입과 삭제가 일어나는 위치(또는 ..

1. 왜 자료구조를 알아야 하는가 알고리즘은 컴퓨터가 무슨 일을 해야 할지 지시하고, 자료구조는 컴퓨터에게 알고리즘에서 사용하는 자료를 어떻게 저장할지 지시하는 것이라고 할 수 있다. 즉, 프로그래밍이란 알고리즘을 작성하고, 그에 맞는 자료구조를 선택하는 것이라고도 할 수 있다. 이런 시각에서 자료구조를 충분하게 이해하지 못한 개발자는 결코 좋은 개발자가 될 수 없다고도 할 수 있을 것이다. 동일선상에서 프로그래밍 언어 중 하나인 Pascal을 개발한 스위스의 컴퓨터 과학자 니클라우스 비르트( Niklaus Emil Wirth; 1934 ~ 2024)는 Algorithms + Data Structures = Programs(1976)>  라는 저서를 지을 정도로 자료구조의 중요성을 강조한 바 있다. 자료..

스프링의 시작 https://yangpro8549.tistory.com/58 객체 지향 설계와 스프링 https://yangpro8549.tistory.com/59?category=1185843 본 정리는 김영한님의 인프런 강의 을 바탕으로 작성하였습니다. 0.  들어가기 전에  예컨대 할인 정책에 관한 로직을 정액 할인에서 정률 할인으로 변경하고자 할 때 우리는 아래와 같은 흐름에 따라 코드를 수정할 수 있다.   public class OrderServiceImpl implements OrderService {// private final DiscountPolicy discountPolicy = new FixDiscountPolicy(); private final DiscountPolicy disco..