'DataStructure/List' 카테고리의 글 목록

2023. 3. 17. 17:48 DataStructure/List

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 초기에 저장되어 있는 위치를 기준으로 내가 원하는 문서를 잡아야 한다. 따라서 초기 상태의 인덱스와 해당 데이터의 우선순위를 하나의 클래스로 묶어 관리하면 편리하다. 이후에는 리스트를 순회하면서 맨 처음에 있는 요소보다 더 큰 우선순위를 가진 요소가 존재한다면 뒷쪽으로 보내고 그렇지 않다면 poll 한다. 이때 인덱스가 내가 원하는 인덱스인지 검사하면 끝이..

LinkedList/Queue의 활용 - BOJ 1158 요세푸스 문제

2023. 3. 17. 16:58 DataStructure/List

문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 접근 원형으로 돌아가 K만큼 떨어진 사람을 계속해서 빼내어 모든 인원이 빠질 때 까지 반복한다. 이때 빼낸 사람들을 순차적으로 출력한 것이 요세푸스 순열이다. 해당 문제는 Queue 문제이지만, LinkedList로도 풀 수 있는 문제이다. 애초에 Java에서 Queue의 구현체로 LinkedList를 사용했으니 사용하는 메서드만 다르지 동작을 동일하게 할 수 있다. 답안 코드 import java.io.BufferedReader; import java.io.IOExceptio..

배열의 정의와 예제 문제

2023. 3. 15. 18:07 DataStructure/List

배열의 정의 배열(Array)는 동일한 자료형들을 하나로 묶어 관리할 수 있게 하는 자료구조이다. 일반적으로 배열은 인접한 메모리로 이어져 있다 가령 예를 들자면 0x10 부터 시작하여 5개의 int형 요소들을 가지고 있는 배열 array을 만든다면 시작 주소는 0x10이고 마지막 주소는 0x23이 된다. C/C++ 에서 포인터에 대한 개념을 알고 있다면 이해하기 쉬울 것이다. 그렇다면 배열을 선언한 배열 변수는 해당 배열의 첫 주소를 가리키고 있는 참조변수가 된다. 즉, array는 0x10메모리를 가리키고 있다는 것이다. 이렇게 인접한 메모리로 이어짐으로 인하여, 색인(index)를 사용한 임의 접근(RandomAccess)가 가능하고, 색인을 사용하여 데이터를 조회, 수정, 삽입, 삭제를 하는데 O..

Queue의 활용 - Programmers 기능개발

2023. 3. 14. 17:04 DataStructure/List

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42586?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 뒤쪽 진행도가 100이 되더라도, 앞쪽 진행도가 100이 되지 않는다면 억류되어야 한다. import java.util.*; class Work{ int curProgress; int speed; Work(int curProgress, int speed){ this.curProgress = curProgress; this.speed = speed; } pu..

Queue의 활용 - BOJ 1021 회전하는 큐

2023. 3. 14. 16:42 DataStructure/List

문제 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 접근 방법 양방향으로 데이터가 삽입 삭제가 가능한 큐를 이용하여 회전이 최소화되도록 요소들을 빼는 문제이다. 문제에서 자료구조의 첫 번째 원소를 가지고 뺄지 말지를 판단하는 것에서 큐라는 자료구조가 생각날 수 있으나 회전의 관점에서 큐를 사용하여 회전시키는 건 조금 귀찮을 여지가 있다(역방향 회전에서 특히) 따라서 해당 문제에 사용할 자료구조는 큐보단 덱이 조금 더 구현하기가 깔끔하다. ..

Stack의 활용 - Programmers 같은 숫자는 싫어

2023. 3. 13. 17:22 DataStructure/List

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12906?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 동일한 숫자를 제거하는 동시에 순서를 유지해야한다. 따라서 HashSet을 통해 중복을 제거하는 꼼수를 사용하기는 힘들어지게 된다. 앞에서 나온 데이터가 스택 또는 큐의 top과 동일하면 push하지 않고, 다르면 push하는 방식으로 구현함으로서 순서를 유지하며 중복을 제거할 수 있는 방법이 된다. 답안 구현 stack으로 작성할 경우에 나중에 답을 내기..

Stack의 활용 문제 - BOJ 25556번 포스택

2023. 3. 13. 17:06 DataStructure/List

문제 https://www.acmicpc.net/problem/25556 25556번: 포스택 포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다. www.acmicpc.net 문제 접근 순열의 "청소"의 정의는 문제에 정의되어있는 일련의 순서를 진행하였을 때 순열의 전체적인 모습이 오름차순으로 정렬될 수 있는가를 묻는다. 스택은 LIFO로 나중에 들어오는 수가 먼저 나가기 때문에 문제의 과정 중 3번을 살펴보면 스택의 내부가 오름차순으로 되어 있어야 한다. 다음의 TC를 보자 10 4 3 6 7 8 9 10 2 1 5 만약 어떤 스택에 4가 먼저 들어온 뒤, 그 스택에 3을 넣는다고 생각해보자. 후입선출의 원리에 의해 스택에서 3이 먼저 나가게 되고 4가 그 이후에 나가게 된다. 하..

Stack의 활용 - VPS

2023. 3. 6. 20:45 DataStructure/List

들어가며 VPS는 기본 문자열 쌍으로 괄호가 올바르게 배치되어 있는가를 확인하는 문제이다. 이때 올바르게 배치되었다 라는 상태의 정의는 괄호의 ( 과 ) 가 쌍을 이룰 수 있도록 배치되어 있는 상태를 말한다. 예시를 들어 (())라는 괄호 쌍은 올바르게 배치되었다. ( 와 )가 쌍을 잘 이루고 있기 때문이다. 다른 예시로 (())((는 올바르지 않은 배치이다. 뒤의 ((의 쌍이 존재하지 않기 때문이다. 다른 예시로 )(는 올바르지 않은 배치이다. 닫힌 괄호가 먼저 나와있기 때문이다. String 배열로 문자열들이 들어온다. 문자열들은 모두 ( 또는 )로 이루어져 있으며 다른 입력이 들어오는 경우는 존재하지 않는다. 이때 각 문자열들이 VPS로 올바르게 배치되었는지 확인하여 그 결과를 배열로 반환하는 함수..

덱(deque)의 정의와 구현

2023. 2. 23. 15:53 DataStructure/List

덱(deque)의 정의 덱 또는 데큐(deque)는 양 방향에서 모두 데이터의 삽입과 삭제가 일어나는 자료구조이다. 양 방향에서 데이터의 삽입 삭제가 발생하기 때문에 데큐는 양방향 연결 리스트로 구현하는 것이 효율이 좋다. 덱(deque)의 연산과 구현 위에도 말했듯 덱은 양방향 연결 리스트로 구현하는 것이 효율적이다. 해당 자료구조는 이미 이전에 큐를 구현하며 같이 구현하였다. 큐에서 데이터의 삽입이 tail에서 이루어졌고 삭제가 head에서 이루어졌다. 덱을 구현하기 위해서는 tail에서의 데이터 삭제와 head에서의 데이터 삽입을 추가적으로 구현하기만 하면 된다. class Node{ int data; Node prev; Node next; Node(int data){ this.data = data..

큐(Queue)의 정의와 구현

2023. 2. 23. 15:25 DataStructure/List

큐의 정의와 구현 Queue는 여러 게임(특히 대표적으로 롤)을 하면서 접할 수 있는 선착순의 개념이 적용된 자료구조이다. 즉 먼저 온 데이터가 먼저 나가는 FIFO(First-In-First-Out)의 구조를 가지고 있다. 이전에 배웠던 Stack이 tail에서 데이터의 삽입과 삭제가 수행되었다면, Queue는 데이터의 삽입은 Tail에서 이루어지고 삭제는 head에서 이루어진다. Queue 역시 배열과 연결 리스트로 구현이 가능하다. 일반적으로 배열보다는 연결 리스트를 더 선호하며 필자도 연결리스트로 구현하려고 한다. 큐의 연산과 그 구현 Queue의 연산들은 다음과 같다. 데이터의 삽입 데이터의 삭제 데이터의 조회(head 부분만) 큐의 상태와 길이 필자는 연결 리스트로 구현하기 때문에 Node 클..

티스토리툴바