배열의 정의와 예제 문제
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으로 작성할 경우에 나중에 답을 내기..
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가 그 이후에 나가게 된다. 하..
우선순위 큐의 활용 문제 풀이
2023. 3. 10. 15:42
DataStructure/Tree
제공되는 문제들은 제로베이스 백엔드 스쿨 11기의 비선형 자료구조 문제들입니다. 우선순위 큐의 활용 우선순위 큐(Priority Queue) 자료구조는 힙을 사용한 자료구조이다. 힙의 특성상 최대, 최소값만 찾고 나머지는 연산할 필요가 없는 문제들에서 사용될 수 있다. 이는 매 턴마다 최대 최소값을 찾기 위해 정렬을 수행해야하는 상황에서 특히 강력함을 발휘할 수 있다. 힙 정렬을 사용하여 O(NlogN) 으로 정렬을 수행한다 하더라도 턴의 수가 M인 경우에 전체 시간 복잡도는 O(M x NlogN)으로 M >= N인 상황에서 O(N^2logN)의 수행시간이 걸리며 이는 그렇게 좋은 시간 복잡도는 아니다. 이를 우선순위 큐를 통해 최대 - 최소값만을 찾을 경우에 데이터의 삽입 - 삭제만 일어나기 때문에 전..
DFS문제와 그 풀이 - (2)
2023. 3. 8. 21:34
Algorithm/BFS, DFS
해당 문제는 제로베이스 벡엔드 스쿨 11기 자료구조 문제입니다. 문제 설명 이메일 정보가 들어있는 2차원 문자열 배열인 accounts가 입력으로 들어온다. accounts[i][0]은 사람의 이름, accounts[i][1]은 이메일을 나타내는 구조로 되어있다. 한 사람이 여러 개의 이메일을 소유하기도 하며, 동명이인이 존재할 수 있다. 이때 구분하는 방법은 다음과 같다. 이름이 동일하고, 이메일이 다르다면 동명이인이다. 이름이 동일하고, 이메일 중 동일한 이메일이 존재한다면 동일인이다.(복수의 이메일을 가진 사람) 이때 이메일 정보를 취합하여 출력하는 프로그램을 작성하라 문제 접근 처음 보면 난해해 보인다. 하지만 입력 부분을 잘 보면 그래프로 모델링할 수 있다. 위의 조건 중 하나로 이름이 같고, ..
DFS 문제와 그 풀이 - (1)
2023. 3. 8. 21:05
Algorithm/BFS, DFS
해당 문제는 제로베이스 벡엔드 스쿨에서 만든 문제입니다. 문제의 설명 N x M 크기의 행렬인 board와 문자열 word가 입력으로 들어올 때 행렬 board에서 word를 찾을 수 있는지 확인하는 문제이다. 이때 word로 찾아지는 문자열은 모두 인접해 있어야 한다. 예를 들어 위와 같은 board가 주어졌다고 할 때, word로 ABCCED가 들어왔다면 위 사진의 색칠된 것과 같이 찾을 수 있게 되어 true를 반환하게 된다. 문제의 접근 word로 주어진 문자열을 찾을 때 모든 문자들이 인접해야 한다는 조건이 있다. 이는 board의 각 칸을 하나의 노드로 생각할때 상하좌우로 간선이 연결된 그래프로 모델링이 가능하다. 즉 문제는 이 그래프에서 탐색을 통해 word와 동일한 문자열을 만들어낼 수 있..
트라이(Trie)의 정의와 구현
2023. 3. 7. 20:37
DataStructure/Tree
트라이의 정의 트라이는 문자열을 저장하고 빠르게 탐색하기 위해 사용하는 자료구조의 일종으로 트리 구조를 가진다. 일반적으로 어떠한 문자열에서 특정 문자열을 찾기 위해서 이중 루프를 사용하나 해당 방법은 O(N^2)에 가까운 수행시간이 걸리게 된다. 트라이에서는 트라이 자료구조를 생성하는데 걸리는 시간 O(MN)이 수행된다(M : 문자열의 개수, N : 문자열의 길이) 하지만 생성하고 나면 길이 N의 문자열을 탐색하는데 O(N)이 수행되며 트라이 자료구조를 위한 메모리와 탐색에 걸리는 시간을 trade-off 하였다고 할 수 있다. 위 사진의 트라이에는 각각 "apple", "april", "ace", "bear", "best"가 들어가있다. 푸른색으로 색칠된 노드들은 해당 노드가 문자열의 끝임을 나타내는..