'DataStructure' 카테고리의 글 목록

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..

HashMap의 원리와 설명

2023. 3. 16. 16:48 DataStructure/Hash, map, set

기본적인 용어의 정의 Map부터 알아보자. 기본적으로 Map은 어떠한 데이터를 저장할 때 key와 value 쌍을 저장하는 자료구조로, 데이터를 Map 내부에서 탐색하거나 값을 참조하기 위해서는 key를 통해 접근해야 한다. 이를 조금 더 이해하기 쉽도록 생각하자면 배열에서 색인(index)을 통해 요소에 접근하는것 처럼, Map에서는 key를 통해 요소에 접근한다. 즉 기존 정수로만 제한되어 있던 색인을 정수 뿐만이 아닌 여러 타입으로 확장하였다고 생각하면 이해하기가 쉬울 것이다. Map의 특징으로는 key의 중복을 허용하지 않으며 대신 value의 중복은 허용된다. 또한 key를 통해 데이터의 접근, 탐색에 $O(1)$라는 강력한 성능을 가지는 것도 특징이다. Hash는 어떠한 데이터를 입력받은 후 ..

프로그래머스 - 위장

2023. 3. 16. 15:59 DataStructure/Hash, map, set

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 해시맵을 사용하는 문제이지만 기본적으론 경우의 수를 구하는 문제이다. 만약 얼굴을 동그란 안경, 검정 선글라스로 상의를 파란색 티셔츠, 하의를 청바지, 겉옷을 긴 코트로 한다면 해당 부위를 입지 않는 경우의 수까지 포함하여 곱의 경우의 수를 계산해야 한다. 그렇다면 동그란 안경 - 파란색 티셔츠 - 청바지 - 겉옷, 동그란 안경 - 파란색 티셔츠 - 없음 - 겉옷 등으로 경우의 수..

BOJ 26008 해시해킹

2023. 3. 16. 15:54 DataStructure/Hash, map, set

문제 https://www.acmicpc.net/problem/26008 26008번: 해시 해킹 첫째 줄에 비밀번호의 길이 $N$과 문자 종류의 개수 $M$, 정수 $A$가 주어진다. ($1 \le N, M, A \le 5\,000\,000$) 둘째 줄에 재현이가 알아낸 해시값 정수 $H$가 주어진다. ($0 \le H < M$) www.acmicpc.net 문제 접근 해당 문제는 해싱에 대해 묻고 있다. 주목해야 할 점은 해싱하는데 사용하는 해시 함수 h(P)에 대해서이다. 문제에서 제시한 해시 함수는 아래와 같다. $$ h(P) = (P_0 \ast A^0 + P_1 \ast A^1 + \cdots + P_{N-1} \ast A^{N-1}) mod M $$ 이때 $P_0$ 을 보자 $A^0$ 이 1..

배열의 정의와 예제 문제

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

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

Programmers - 압축

2023. 3. 14. 20:04 DataStructure/Hash, map, set

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17684 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 LZW 압축의 동작을 그대로 구현하는 것이다. 이때 단어가 세팅된 사전에 존재하는지를 체크하고 없다면 그 단어를 사전에 넣고, 존재한다면 해당 색인(index)를 넣음으로서 압축을 할 수 있다. 나이브하게 접근하면 사전을 순회하면서 현재 단어가 사전에 존재하는지 비교를 하며 존재한다면 인덱스를 반환하고 존재하지 않는다면 사전에 포함시키는 동작을 구현하면 된다. 하지만 이는 단어가 ..

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으로 작성할 경우에 나중에 답을 내기..

티스토리툴바