문제

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

1
2
3
4

1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항

• n은 10,000 이하의 자연수 입니다.

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13

def solution(n):
    q = [1]
    answer, i, total = 1, 1, 1
    mid = int((n+1) / 2) # 절반보다 큰 값부터는 값이 없으니 절반까지 반복문 실행
    while i < mid:
        i += 1
        total += i
        q.append(i)
        while total > n:
            total -= q.pop(0)
        if total == n:
            answer += 1
    return answer

• 원소가 1만 있는 큐(리스트)를 만든다.
• 주어진 수의 절반까지 반복한다.
• 차례로 수를 더할 때마다 queue에 수를 추가한다.
  • 더한 값이 원하는 수보다 큰 동안, 큐에서 수를 하나씩 꺼내어 합에서 뺸다.
  • 더한 값이 원하는 수이면 정답 개수를 하나 늘린다.

댓글 공유

문제

양의 정수 n이 주어질 때 1부터 n까지의 십진수를 이진수로 출력하라.

Generatre Binary Numbers

1. 내장함수 풀기

1
2
3

def generate_binary(n):
    for i in range(1, n+1):
        print(bin(i)[2:]) # 이진수는 0b가 붙으므로 슬라이싱으로 제거한다.

2. 큐를 사용하여 풀기

문제를 분석해보면, 2의 이진수는 10이고 3의 이진수는 11이다.

이는 1에다가 0과 1을 붙인 것이다.

4의 이진수는 100이고 5의 이진수는 101이다. 이는 2의 이진수 10에다가 0과 1을 추가한 것이다.

앞서 사용한 숫자에 0과 1을 붙인 이진수가 나중에 사용된다.

1. 큐를 하나 생성하고 1을 삽입한다.

2. n만큼 반복한다.

   1. 큐에서 꺼낸 값을 i에 저장
   2. i에 0과 1을 붙인 이진수를 큐에 삽입
   3. i를 출력

1
2
3
4
5
6
7
8
9

def generate_binary_queue(n):
    q = Queue() # 직접 구현한 Queue 클래스
    q.enqueue('1')

    for _ in range(n):
        i = q.dequeue()
        q.enqueue(i+'0')
        q.enqueue(i+'1')
        print(i)

댓글 공유

2. queue로 풀기

1
2
3
4
5
6
7
8
9
10
11

def josephus(n,k):
    res = []
    q = Queue() # 직접 구현한 Queue 클래스
    for i in range(n):
        q.enqueue(i+1)
    while q.front.next: # 끝에서 2번째 원소까지 반복
        for _ in range(k-1):
            q.enqueue(q.dequeue())
        res.append(q.dequeue())
    res.append(q.dequeue()) # 마지막 원소 출력
    return res

댓글 공유

문제

1번부터 N 번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K 번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

예시

• 입력: 7, 3
• 출력: [3, 6, 2, 7, 5, 1, 4]

1. list로 풀기

예시대로 3번째 마다 사람을 제거하려면, 처음에는 시작점이니 2번만 인덱스를 이동하고 제거한 후 이 후에는 3번 인덱스를 이동해서 제거한다.

첫 시작을 0이 아닌 -1로 시작하는 점에 유의하자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def josephus(n,k):
    res = []
    line = [1 for _ in range(n)] # 값이 1이면 제거 대상, 0이면 제거 완료
    i = -1

    for _ in range(n-1):
        count = 0
        while count < k:
            i = (i + 1) % n # i는 0~6까지 순회해야하므로 나머지로 계산한다.
            if line[i]: # line의 원소가 0이 아니면...
                count += 1
        line[i] = 0
        res.append(i+1)

    res.append(line.index(1)+1)
    return res

1. line 배열을 1로 초기화 해준다. 1은 아직 제거안된 요소이고 0은 제거된 요소로 처리
2. 마지막 1개가 남을 때 까지 반복하므로 n-1회 반복한다.
3. count 변수는 제거되지 않은 원소를 지나온 순서를 카운팅하기 위해 사용한다.
4. 0 ~ 6까지 index가 순회해야하므로, n으로 나눈 나머지 값을 이용한다.
5. i를 순회하면서 line의 요소가 0이 아니면, 즉 아직 제거되지 않았으면 순서를 카운팅 해준다.
6. 순서를 카운팅 해서 k번째 순서에 도달하면, 반복을 멈추고 해당 index 요소를 0으로 바꾼다. (요소 제거)
7. 해당 index는 0부터 시작했으므로, 결과 배열에 넣어줄 땐 +1을 해준다. 왜냐하면 문제에선 1부터 시작한다 했으니 때문이다.
8. 이렇게 n-1번 반복하게되면 line의 요소는 1개 남는다. 이 때는 index 메서드를 사용하여 1인 요소의 index를 구한 뒤 결과배열에 추가한다. 이 때도 + 1 을 해줘야한다.

댓글 공유

Queue 클래스로 구현하기

• Queue는 입구가 rear이고 출구가 front이다.
• 입구쪽에서 데이터를 추가하는 것을 enqueue라고 한다.
• 출구쪽에서 데이터를 제거하는 것을 dequeue라고 한다.

노드 삽입할 때,

• 빈 Queue이면 front, rear가 모두 첫 노드를 가리킨다.
• 빈 Queue가 아니면, rear의 next가 새 노드를 가리키고 rear를 새 노드로 옮긴다.

노드 꺼낼 때,

• 빈 Queue가 되면, front, rear는 모두 None을 가리킨다.
• Queue에 노드가 남아있으면 front를 front의 next로 옮긴다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Node:
    def __init__(self,data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self,data):
        node = Node(data)
        if self.front == None:
            self.front = node
            self.rear = node
        else:
            self.rear.next = node
            self.rear = node

    def dequeue(self,data):
        if self.front == None:
            return None
        node = self.front
        if self.front == self.rear:
            self.front = None
            self.rear = None
        else:
            self.front = self.front.next
        return node.data

    def is_empty(self):
        return self.front == None

댓글 공유

Queue(큐)란?

큐는 대기행렬(줄)이다.

우리가 무언가를 사거나 장소에 들어갈 때 줄을 선 순서를 생각하면 된다.

많은 양의 자료를 프린터로 출력한다 했을 때, 프린터 상태창을 보면 출력할 자료가 순서대로 들어가있고 들어간 순서대로 출력되는 것을 알 수 있다.

스택이 한쪽입구가 막힌 상자에 자료를 차곡차곡 쌓는 것이라면, 큐는 입구와 출구가 따로 있는 통로로서 한쪽에서 밀어 넣으면 반대쪽에서 나오는 것이다.

• 큐에서는 head 대신 front, tail 대신 rear(or back) 이라 한다.
• enqueue: 가장 마지막에 자료를 넣는 것으로 위 그림에서 연결리스트의 append()와 같다.
• dequeue: 가장 먼저 들어간 자료를 꺼내는 것으로 연결리스트의 popLeft()와 같다.

댓글 공유