Queue-숫자의 표현 문제

2023/08/27 카테고리 Python, DataStructure, Queue

문제

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

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

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

제한사항

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

풀이

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에 수를 추가한다.
- 더한 값이 원하는 수보다 큰 동안, 큐에서 수를 하나씩 꺼내어 합에서 뺸다.
- 더한 값이 원하는 수이면 정답 개수를 하나 늘린다.

댓글 공유

Queue로 이진수 만들기

2023/08/26 카테고리 Python, DataStructure, 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을 삽입한다.
n만큼 반복한다.
1. 큐에서 꺼낸 값을 i에 저장
2. i에 0과 1을 붙인 이진수를 큐에 삽입
3. i를 출력

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)

댓글 공유

요세푸스 문제

2023/08/25 카테고리 Python, DataStructure, Queue

2. queue로 풀기

josephus

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

댓글 공유

요세푸스 문제

2023/08/24 카테고리 Python, DataStructure, Queue

문제

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로 시작하는 점에 유의하자.

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

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

댓글 공유

큐 - 클래스로 구현하기

2023/07/24 카테고리 Python, DataStructure, Queue

Queue 클래스로 구현하기

enqueue와 dequeue

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

노드 삽입할 때,

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

노드 꺼낼 때,

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

코드

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

댓글 공유

큐 - 개념 및 설명

2023/07/23 카테고리 Python, DataStructure, Queue

Queue(큐)란?

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

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

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

queue

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

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

댓글 공유

스택 - 자신보다 큰 원소 찾기

2023/07/21 카테고리 Python, DataStructure, Stack

문제

참조: https://www.geeksforgeeks.org/next-greater-element/

음이 아닌 정수 배열이 주어졌을 때, 각 원소의 오른쪽에 있는 원소 중에서 현재 원소보다 큰 값을 출력하되, 가장 근접한 원소를 출력하라. 현재 원소보다 큰 값이 없으면 -1을 출력하라.

예시 1

입력: [4, 5, 2, 25]
출력:
4 --> 5
5 --> 25
2 --> 25
25 --> -1
예시 2

입력: [13, 7, 6, 12]
출력:
13 --> -1
7 --> 12
6 --> 12
12 --> -1

풀이

이중반복문

def solution(int_arr):
    for i in range(len(int_arr)):
        int = int_arr[i]
        result = -1
        for j in range(i,len(int_arr)):
            if int < int_arr[j]:
                result = int_arr[j]
                break
        print(f"{int} --> {result}")

스택

def solution*by_stack(int_arr):
    n = len(int_arr)
    s = []
    res = [-1 for * in range(len(int_arr))]

    for i in range(n-1,-1,-1):
        while s:
            if s[-1] > int_arr[i]:
                res[i] = s[-1]
                break
            else:
                s.pop()
        s.append(int_arr[i])

    for i in range(n):
        print(f"{int_arr[i]} --> {res[i]}")

현재 원소와 오른쪽 원소를 비교하므로, 오른쪽에서 왼쪽으로 이동하면서 비교하면 수월하다.
문제에서 요구하는 것은 현재 원소의 오른쪽 값 중 가장 가까운 값이므로, 오른쪽 부터 왼쪽으로 가면서 원소를 저장했다면 꺼낼 때는 역순으로 꺼내서 비교한다.

stack을 빈 상태로 초기화
res 배열을 -1로 배열 길이 만큼 초기화
역순으로 순회를 하면서 stack이 비어있으면, 원소를 추가한다.
만약 stack에 값이 있다면, 스택의 값들과 현재 원소를 비교한다.
스택의 값이 크다면 해당 원소의 index에 위치하는 res 배열에 스택의 값을 할당하고 해당 원소를 stack 저장
다음 순회
만약 스택의 값이 작다면 stack에 마지막 값을 pop한다.

댓글 공유

스택 - 후위 표기법2

2023/07/19 카테고리 Python, DataStructure, Stack

후위 표기법 2

소괄호를 포함한 후위 표기법 바꾸기

소괄호()는 *보다 우선순위가 높다.

후위 표기법은 우선순위가 높은 것을 먼저 출력하므로, 열린 소괄호가 나오면 스택에 넣는다.

이후 닫힌 소괄호가 나오면 스택에 열린 소괄호 나올 때 까지 pop하여 연산자를 결과값에 추가한다.

괄호는 변수에 추가하면 안되므로 스택에서 pop하여 제거한다.

def solution(str):
    priority = {'+':2,'-':2,'*':1,'/':1}
    result = ''
    s = []

    for x in str:
        if x.isnumeric():
            result += x
        elif x == '(':
            s.append(x)
        elif x == ')':
            while s[-1] != "(":
                result += s.pop()
            s.pop()
        elif x in priority:
            if s and s[-1] != '(' and priority[s[-1]] < priority[x]:
                result += s.pop()
            s.append(x)

    while s:
        result += s.pop()

    return result

코딩테스트를 본다고 생각하고 리스트를 활용하여 위 문제를 풀어보았다.
isnumeric() 함수는 문자열이 숫자인지 판단하는 메서드이다.
stack의 top을 의미하는 s[-1] 슬라이싱을 활용하였다.
빈 리스트는 논리값이 False라는 점을 활용하여 while 반복문을 실행했다.

후위 표기법 계산하기

문자열을 순회하면서 해당 문자가 숫자면 정수형으로 변환하여 스택에 push
연산자이면 스택에서 두 수를 pop하여 계산
스택은 후입선출이므로, 처음 pop한 수를 n2, 두번째 pop한 수를 n1으로 두고 (n1 연산자 n2)로 계산한다.
계산결과를 스택에 push
스택에 마지막에 저장된 값이 결과값이다.

def eval_postfix(expression):
    s = []
    for exp in expression:
        if exp.isnumeric():
            s.append(int(exp))
        elif exp != " ":
            n2 = s.pop()
            n1 = s.pop()
            if exp == '+':
                res = n1 + n2
            elif exp == '-':
                res = n1 - n2
            elif exp == '*':
                res = n1 * n2
            else:
                res = n1 / n2
            s.append(res)
    return s[0]

댓글 공유

스택 - 후위 표기법

2023/07/19 카테고리 Python, DataStructure, Stack

후위표기법 1

연산자를 피연산자 뒤에 쓰는 연산기법

예를 들어, 3+5x2 를 중위 표기법이라 하고,

352x+를 후위 표기법이라고 한다.

계산 방법

3+5x2를 후위 표기법으로 적으면, 352x+이다.

352x+를 계산하기 위해서 다음과정을 따른다.

피연산자(숫자)는 스택에 담는다. [3,5,2]
연산자를 만나면, 스택에서 피연산자 2개를 꺼내 계산한다.
결과값을 다시 스택에 넣는다. [3,10]
다음 연산자는 +이므로 3+10을 계산한다.

컴퓨터 입장에서는 후위 표기법이 연산의 우선순위가 명확하다는 장점이 있다.

중위 표기법을 후위 표기법으로 변환

3+5x2를 후위 표기법으로 바꾸는 과정을 알아보자.

피연산자 3을 결과값에 추가
- 연산자 스택에 push
피연산자 5 결과값에 추가
x 연산자와 스택의 마지막 값인 + 우선순위 비교
x 연산자가 우선순위 높으므로 스택에 push
피연산자 2 결과값에 추가
스택이 빌 때까지 pop하여 결과값에 추가

3x5+2를 후위 표기법으로 바꿔보자.

피연산자 3을 결과값에 추가
x 연산자 스택에 push
피연산자 5 결과값에 추가
- 연산자와 스택의 마지막 값인 x 우선순위 비교
스택의 마지막 값인 x 연산자가 높으니 pop하여 결과값에 추가
- 연산자는 스택에 push
피연산자 2을 결과값에 추가
스택이 빌 때까지 pop하여 결과값에 추가

문제 풀이

Stack 클래스를 이용한 풀이

def solution(str):
    priority = {'+':2,'-':2,'*':1,'/':1}
    s = Stack()

    result = ''
    for x in str:
        if x not in priority.keys():
            result += x
        else:
            if s.top == None:
                s.push(x)
            else:
                if priority[s.top.data] < priority[x]:
                    s_pop = s.pop()
                    result += s_pop
                s.push(x)

    while not s.is_empty():
        s_pop = s.pop()
        result += s_pop

    return result

아래는 if 문으 조금 줄여보았다.

def solution(str):
    priority = {'+':2,'-':2,'*':1,'/':1}
    s = Stack()

    result = ''
    for x in str:
        if x not in priority.keys():
            result += x
        else:
            if not s.is_empty() and priority[s.top.data] < priority[x]:
                s_pop = s.pop()
                result += s_pop
            s.push(x)

    while not s.is_empty():
        s_pop = s.pop()
        result += s_pop

    return result

댓글 공유

스택 - 연습문제

2023/07/18 카테고리 Python, DataStructure, Stack

문제 1. 괄호 짝 검사

괄호의 짝이 바르면 True, 바르지 않으면 False를 반환하는 함수를 작성하라.

예를 들어 ((a*(b+c))-d) / e는 괄호의 짝이 올바르지만, (((a*(b+c))-d) / e 는 괄호의 짝이 맞지 않는다.

괄호는 소괄호(())만 사용한다.

풀이

def solution(str):
    stack = Stack()

    for x in str:
        if x == '(':
            stack.push(x)
        elif x == ')':
            if not stack.pop():
                return False
    return stack.is_empty()

여는 괄호가 나오면 stack에 Push
닫는 괄호가 나오면 stack을 pop
- 이 때, stack에서 아무것도 pop되지 않는다면, 제대로 된 괄호가 구성되지 않은 것이다.

문제 2. 소,중,대괄호 짝 검사

소괄호, 중괄호, 대괄호 짝이 맞는지 검사

1
2
3

"[{a * (b + c)} - d] / e" # True

"[{a * (b + c)] - d] / e" # False

풀이

def solution(str):
    brackets = {")":"(", "}":"{", "]":"["}
    stack = Stack()

    for x in str:
        if x in brackets.values():
            stack.push(x)
        elif x in brackets:
            popped = stack.pop()
            if not popped or brackets[x] != popped:
                return False
    return stack.is_empty()

brackets을 관리하는 딕셔너리를 만든다.
여는 괄호면 stack에 push한다.
닫는 괄호면, 해당 닫는 괄호와 짝을 이루는 여는 괄호가 stack.pop()한 요소와 같은지 비교
- 만약 다르거나 pop한 요소가 None이라면 False

문제 3. 짝지어 제거하기

같은 알파벳 2개가 붙어 있는 짝을 찾습니다.

그 다음 그 둘을 제거한 뒤 앞뒤로 문자열을 이어 붙입니다.

이 과정을 반복하여 문자열이 모두 제거된다면 1을 반환하고 그렇지 않으면 0을 반환합니다.

풀이

def solution(str):
    stack = []

    for ch in str:
        if stack and ch == stack[-1]:
            stack.pop()
        else:
            stack.append(ch)
    return 0 if stack else 1

stack 클래스 대신 배열을 사용했다.
stack의 push(): append()
stack의 pop(): pop()
stack의 peek(): [-1]로 인덱싱
is_empty(): 빈 리스트 논리값은 False 임을 이용

댓글 공유

문제

제한사항

풀이

문제

1. 내장함수 풀기

2. 큐를 사용하여 풀기

2. queue로 풀기

문제

예시

1. list로 풀기

Queue 클래스로 구현하기

노드 삽입할 때,

노드 꺼낼 때,

코드

Queue(큐)란?

문제

풀이

이중반복문

스택

후위 표기법 2

후위 표기법 계산하기

후위표기법 1

계산 방법

중위 표기법을 후위 표기법으로 변환

문제 풀이

Stack 클래스를 이용한 풀이

문제 1. 괄호 짝 검사

풀이

문제 2. 소,중,대괄호 짝 검사

풀이

문제 3. 짝지어 제거하기

풀이

loco9939