어제 해커톤 마무리 회의를 하느라 늦게 잤다
잠이 쏟아진다.
자료구조 - Queue
특성
스택과 다르게 FIFO(First In First Out) 구조를 가진 자료구조
즉, 처음 들어온게 처음 나가는 구조를 갖는다.
다양한 알고리즘에 자주 사용되는 자료구조니 자세히 알아보자.
구조
간단하게 그림으로 알아보자면,
이렇게 구멍이 두 개 뚫린 원통을 생각하면 좋다.
활용
마이쮸 나눠주기 시뮬레이션!!!!
다음과 같이 상황이 주어졌다.
문제가 좀 불친절 하다고 느낄 수 있지만, 나는 정말 이러한 문제가 일상 생활에서 발생할 수 있는 시나리오라고 생각한다.
그리고 이를 알고리즘으로 푸는 것이 진짜 알고리즘 해결 능력이라고 생각한다.
인생은 실전이야
그럼 이 시나리오를 분석해보자.
1번이 줄을 서서 마이쮸를 받은 뒤,
한 번 더 받으려 줄을 서면 새로운 사람이 들어온다.
2번 역시 한 번 더 줄을 서면 3번이 들어오는 것을 확인할 수 있다.
그럼 n번이 2번 이상 받기 위해 줄을 서면 n+1번의 새로운 사람이 들어와 줄을 서게 된다.
이제 코드로 작성해 보자.
코드
public class 마이쮸 {
public static void main(String[] args) {
int N = 20; // 마이쮸 개수
Queue<int[]> queue = new ArrayDeque<>(); // 사람의 번호, 받아야하는 마이쮸 개수, 큐에 넣어서 관리
int person = 1;
queue.offer(new int[] {person, 1});
while(N > 0) {
int[] p = queue.poll();
int availableCnt = N >= p[1] ? p[1] : N;
N -= availableCnt;
if(N == 0) {
System.out.println("마지막 마이쮸를 포함해서 가져가는 사람은 " + p[0] + "번이며 " + availableCnt + "만큼 가져감");
}
else {
System.out.println(p[0] + "번의 사람이 " + availableCnt + "만큼 가져감");
p[1]++;
queue.offer(p);
queue.offer(new int[] {++person, 1});
}
}
}
}# 결과
1번의 사람이 1만큼 가져감
1번의 사람이 2만큼 가져감
2번의 사람이 1만큼 가져감
1번의 사람이 3만큼 가져감
3번의 사람이 1만큼 가져감
2번의 사람이 2만큼 가져감
4번의 사람이 1만큼 가져감
1번의 사람이 4만큼 가져감
5번의 사람이 1만큼 가져감
3번의 사람이 2만큼 가져감
6번의 사람이 1만큼 가져감
마지막 마이쮸를 포함해서 가져가는 사람은 2번이며 1만큼 가져감위에 분석한 알고리즘대로 코드를 짜 보았다.
조금 다른 점이 있다면, 가져갈 수 있는 마이쮸의 개수를 체크하는 것.
순번이 된 사람이 가져갈 양보다 많거나 같다면 상관없지만,
내가 받을 양보다 적으면 그거라도 가져가야한다.
사실 그냥 있든 없든 가져가고 N <= 0이라면 출력문을 실행시켜도 비슷한 결과를 보여준다. 하지만 최대한 실생활이라고 생각하고 코드를 작성했다.
Queue가 활용되는 알고리즘
Queue가 사용되는 곳은 FIFO 구조가 필요한 모든 알고리즘에서 이용된다고 보면 된다. 물론 문제마다 상황이 다르고 함정 문제도 있지만, BFS나 n방 탐색 등에 자주 사용된다.
