자료구조, 알고리즘 문제 풀어보기(우주선 긴급 암호 해독)

16 Jul 2025 | Data Structure

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

문제 1: 우주선 긴급 암호 해독

테마/상황:

당신은 우주 탐사선 ‘노바-1’의 통신 장교입니다. 그런데 외계 신호의 공격으로 인해 동료들과의 통신 암호가 뒤죽박죽이 되어버렸습니다! 암호를 원래대로 복구하여 긴급 메시지를 해독해야 합니다. 암호는 단어의 순서가 거꾸로 뒤집혔고, 특정 글자가 다른 글자로 바뀌었습니다.

미션:

주어진 암호 문장을 해독하는 함수 decode_message를 작성하세요.

해독 규칙:

문장을 단어 단위로 분리한 후, 단어의 순서를 거꾸로 뒤집습니다.
각 단어에서 ‘!’는 ‘a’로, ‘@’는 ‘e’로, ‘#’는 ‘i’로, ‘$’는 ‘o’로, ‘%’는 ‘u’로 바꾸세요.
해독된 단어들을 다시 하나의 문장으로 합쳐 반환합니다.

예시:

입력: "w@lc$m@! t$ pyth$n #s h@ll$!"
출력: "hello is python to welcome"

<1. 내가 푼 풀이>

def decode_message(sentence):
    for i in sentence:
        if i == '@':
            sentence = sentence.replace('@', 'e')
        elif i == '#':
            sentence = sentence.replace('#', 'i')
        elif i == '$':
            sentence = sentence.replace('$', 'o')
        elif i == '%':
            sentence = sentence.replace('%', 'u')

    # sentence를 ,구분자로 나누고 []배열안에 넣기
    sentence = sentence.split()  
    # 역순으로 넣은 후 배열에서 스트링으로
    return ' '.join(sentence[::-1])  

decode_message("w@lc$m@! t$ pyth$n #s h@ll$!")

<2. 교육 내 답변>

def decode_message(encoded_str):
     # 1. 암호를 단어 단위로 분리합니다.
    words = encoded_str.split(' ')
    # 2. 단어의 순서를 거꾸로 뒤집습니다.
    words.reverse()

    decoded_words = []
    print(decoded_words)
    for word in words:
        # 3. 각 단어의 특수문자를 알파벳으로 바꿉니다.(메서드 체이닝 활용)
        temp_word = word.replace('@', 'e').replace('#', 'i').replace('$', 'o').replace('%', 'u')
        decoded_words.append(temp_word)

    # 4. 해독된 단어들을 다시 하나의 문장으로 합칩니다.
    return " ".join(decoded_words)

 # 예시 실행
encoded_message = "w@lc$m@! t$ pyth$n #s h@ll$!"
decoded_message = decode_message(encoded_message)
print(f"암호: {encoded_message}")
print(f"해독: {decoded_message}")

Comment Read more

자료구조, Queue

16 Jul 2025 | Data Structure

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

Queue

선형 자료구조 중에서도 동적 자료구조에 해당하는 Queue는 필요에 따라 메모리에 공간을 유연하게 할당하고 해제해 데이터를 저장할 수 있어 데이터의 추가, 삭제, 크기 변경등이 가능하다. 이때 스택의 가장 중요한 특징은 FIFO 개념이다.

FIFO: First In First Out

먼저 들어온 데이터가 먼저 나가는 자료구조
선착순의 원리 > 먼저 들어온 사람이 먼저 서비스를 받음
스택과 반대되는 개념

주요 연산

Enqueue(인큐): queue의 뒤쪽(rear) 데이터에 삽입
Dequeue(디큐): queue의 앞쪽(front) 데이터 삭제 및 반환

Python으로 구현해보는 queue

class Queue:
    def __init__(self):
        # queue를 담아줄 빈 리스트 생성
        self.items = []
        # 맨 앞의 인덱스 0 지정 
        self.front_index = 0

    def enqueue(self, value):
        # items안에는 일단 차곡차곡 데이터가 쌓인다
        self.items.append(value)

    def dequeue(self):
        try:
            # items이 빈리스트가 아니라면 (값이 있다면)
            return self.items.pop(0)
        except IndexError:
            # items에 아무것도 없다면 더이상 삭제할 아이템이 없으니까 indexError발생
            print('Queue is empty')
            return None

queue = Queue()
queue.enqueue(3)
queue.enqueue(23)
queue.enqueue(5345)
queue.enqueue(234)
queue.enqueue(5456)

queue.items
# 출력: [3, 23, 5345, 234, 5456]
queue.dequeue()
# 출력: 3
stack.items
# 출력: [23, 5345, 234, 5456]

각 연산들의 시간 복잡도: O(1) 인 것도 확인 가능하다. (enqueue, dequeue)

Enqueue
1. 리스트의 append 함수 사용
2. 항상 리스트의 끝에 데이터가 추가됨
Dequeue
1. 리스트의 pop 함수 사용
2. 항상 리스트의 맨 앞 데이터가 삭제됨
3. collections의 deque를 사용해도 됨

큐 예제 > 조세푸스(josephus)

문제 상황
1. N명이 원형으로 앉아있음
2. K번째 사람마다 제거
3. 마지막 남은 1명의 번호 찾기

case1, 그냥 풀어보기

def josephus(n, k):
    queue_list = []

    for i in range(1, n+1):
        # 1부터 n까지 큐에 enqueue
        queue_list.append(i)

    # 2. 반복:
    # - (k-1)개는 dequeue 후 다시 enqueue
    # - k번째는 dequeue만 (제거)   
    # 3. 큐에 1개만 남을 때까지 반복
    while len(queue_list) > 1:
        for i in range(k-1):
            queue_list.append(queue_list.pop(0))
        queue_list.pop(0)

    # 4. 마지막 남은 번호 반환
    return queue_list

josephus(6,2)

case2, deque 활용해서 풀어보기

from collections import deque
# deque 사용해보기
def josephus(n, k):
    dq = deque()

    for i in range(1, n+1):
        # 1부터 n까지 큐에 enqueue
        dq.append(i)

    # 2. 반복:
    # - (k-1)개는 dequeue 후 다시 enqueue > k-1: 앞에서 몇번 건너뛸지
    # - k번째는 dequeue만 (제거)   
    # 3. 큐에 1개만 남을 때까지 반복
    while len(dq) > 1:
        for i in range(k-1):
            dq.append(dq.popleft())
        dq.popleft()

    # 4. 마지막 남은 번호 반환
    return dq

josephus(6,2)

Comment Read more

자료구조, Stack

16 Jul 2025 | Data Structure

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

Stack

선형 자료구조 중에서도 동적 자료구조에 해당하는 Stack은 필요에 따라 메모리에 공간을 유연하게 할당하고 해제해 데이터를 저장할 수 있어 데이터의 추가, 삭제, 크기 변경등이 가능하다. 이때 스택의 가장 중요한 특징은 LIFO 개념이다.

LIFO: Last In First Out

가장 마지막에 들어온 데이터가 가장 먼저 나가는 자료구조
데이터는 한쪽 끝에서만 삽입, 삭제가 이루어짐
중간에 대한 접근은 불가능 > 오직 맨 위(top) 데이터에만 접근 가능

주요 연산

push(value): 스택의 맨 위에 값을 추가 > append개념
pop: 스택의 맨 위 값만 제거하고 반환

Python으로 구현해보는 stack

class Stack:
    def __init__(self):
        # stack을 담아줄 빈 리스트 생성
        self.items = []

    def push(self, value):
        # 비어있는 stack에 값을 추가 
        self.items.append(value)

    def pop(self):
        try:
            # items이 빈리스트가 아니라면 (값이 있다면)
            return self.items.pop()
        except IndexError:
            # items에 아무것도 없다면 더이상 삭제할 아이템이 없으니까 indexError발생
            print('Stack is empty')
            return None

    def top(self):
        # 현재 스택 최상단 친구는 누구인지 묻는 함수
        try:
            return self.items[-1]
        except IndexError:
            # items에 아무것도 없다면 더이상 삭제할 아이템이 없으니까 indexError발생
            print('Stack is empty')
            return None

    # 이미 존재하는 함수인 len 접근
    def __len__(self):
        return len(self.items)

stack = Stack()
stack.push(12)
stack.push(3)
stack.push(2)
stack.push(1232)
stack.push(12123124)

stack.items
# 출력: [12, 3, 2, 1232, 12123124]
stack.pop()
# 출력: 12123124
stack.items
# 출력: [12, 3, 2, 1232]
stack.top()
# 출력: 1232
len(stack)
# 출력: 4

각 연산들의 시간 복잡도: O(1)인 것도 확인 가능하다.(push, pop, top, len)

스택 예제 > 괄호 맞추기

문제 상황
1. 왼쪽 괄호 ‘(‘ → 스택에 push
2. 오른쪽 괄호 ‘)’ → 스택에서 pop
3. 모든 괄호 처리 후 스택이 비어있으면 올바른 쌍

def check_parentheses(seq):
    # 위에서 만들어놓은 Stack 클래스를 통해 stack 객체 생성
    stack = Stack()
    
    for s in seq:
        # 들어온 seq에 s가 "(" 라면
        if s == "(":
            # stack에 ( 를 추가 (push)
            stack.push(s)

        # 들어온 seq에 ")"라면
        elif s == ")":
            # 현재 stack의 길이를 확인해서 
            # 길이가 0이면 현재 스택엔 아무것도 없다는 뜻이니까
            if len(stack) == 0:
                # 비어있다고 출력 
                # 근데 원래는 )가 있었어야해 ()이렇게가 쌍이니까! 
                # 그래서 다르게 표현해보면 > return False 이것도 맞다 
                return "empty stack"
            # 만약 stack이 비어있지 않다면? -> 길이가 0이 아니라면
            # (든 )든 둘중 뭐가 있다는 뜻이니까 일단 맨끝에 있는 애를 삭제해! (pop)
            stack.pop()

    # for문을 통해 들어온 seq에 대한 push, pop을 다 진행한 뒤에 stack의 길이를 확인
    # pop을 했는데 stack의 길이가 0보다 많다면 ()의 쌍이 맞지 않았다는 뜻이니까
    if len(stack) > 0:
        # 쌍이 잘 맞지 않았고, stack은 비어있지 않다는 의미!
        return "not empty"
    # len == 0이라는 의미는 쌍이 맞았다는 의미니까
    return "잘 넣으셨군요"

Comment Read more

자료구조, 재귀함수

16 Jul 2025 | Data Structure

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

재귀함수

자료구조에서 재귀란 함수의 실행 과정에서 자기 자신을 한번 이상 호출하는 함수를 의미한다.

def sum_n(n):
    if n == 1:
        return 1
    return sum_n(n-1) + n

이 함수를 실행시켜보면 sum_n(4) > sum(3) + 4 > sum(2) + 3 > sum(1) + 2 > 1으로 진행될 것이다.

수행시간은 T(n) = T(n-1) + C (C는 상수) > T(n-2) + C + C > T(n-3) + C + C + C ... > C*N(=T1~Tn)으로 시간복잡도는 O(n)임을 알 수 있다.

재귀함수의 주의점

기본케이스(base case)를 반드시 만들어야한다.
recursive call이 반드시 있어야한다.

기본 케이스란 재귀 호출을 수행하지 않는 반환값을 의미한다. 위 코드에서 기본케이스는 if n == 1: return 1를 의미한다. 즉, 함수가 반복적으로 호출되었을때 제일 마지막 호출에서는 기본 케이스가 돌아야한다. 그렇지 않으면 코드는 무한반복으로 자기 자신을 호출하기 때문에 함수가 끝나지 않게된다. 파이썬에서의 while True를 떠올리면 이해가 쉽다.

그리고 재귀함수는 반드시 자기 자신을 한번 이상 호출해야한다. 위 코드에서는 return sum_n(n-1) + n에 해당한다.

이러한 재귀함수는 for,while문을 호출하지 않기에 좀 더 코드가 간결해진다는 장점은 존재하지만, 이러한 재귀호출이 많아지면 질수록 메모리의 효율은 떨어진다는 단점 또한 존재한다.

Comment Read more

Pandas 데이터프레임 합치기(concat, merge)

15 Jul 2025 | DA

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

데이터프레임 합치기

다수의 데이터프레임(DataFrame) 혹은 시리즈(Series)를 결합하는 방법에 대해 정리해본다.

pd.concat() > 데이터프레임 붙이기

데이터프레임을 말그대로 물리적으로 이어붙여주는 함수 > pd.concat(데이터프레임 리스트)로 사용

import pandas as pd

# df1, df2 데이터 프레임을 각각 만들어 주면서 각각의 index를 지정해줌
df1 = pd.DataFrame({'a':['a0','a1'],
                   'b':['b0','b1'], 
                   'c':['c0','c1']},
                   index = [0,1])

df2 = pd.DataFrame({'a':['a1','a2','a3'],
                   'b':['b1','b2','b3'],
                   'c':['c1','c2','c3'],
                   'd':['d1','d2','d3']},
                   index = [1,2,3])

df1, df2는 각각 이렇게 출력될 것이다.

[Output]
    a   b   c
0  a0  b0  c0
1  a1  b1  c1

    a   b   c   d
1  a1  b1  c1  d1
2  a2  b2  c2  d2
3  a3  b3  c3  d3

이제 이 두 데이터프레임을 concat을 통해 합쳐보자.

result = pd.concat([df1, df2])
result

[Output]
    a   b   c   d
a0  b0  c0  NaN
a1  b1  c1  NaN
a1  b1  c1  d1  
a2  b2  c2  d2
a3  b3  c3  d3

pd.concat()의 axis는 디폴트 0로 지정되어있기 때문에 둘의 합쳐진 방향이 아래로 이어붙여짐을 알 수 있다.(axis=0은 열기준, 위아래) 그리고 df1의 c는열은 존재하지 않기 때문에 c에 해당하는 데이터가 NaN으로 채워진것 또한 볼 수 있다. 그리고 더 나아가 데이터프레임을 붙일때 그냥 이어붙이다보니 인덱스 번호도 그대로 붙여진 것을 볼 수 있다. 이때는 ignore_index=True를 하면 인덱스 재배열이 가능하다.

pd.concat(axis=0) 이 defalut
비워진 값은 NaN으로 채워짐
인덱스 재배열은 ignore_index=True

pd.concat(axis=1)을 하는 경우

axis=1은 행기준, 좌우방향!

result = pd.concat([df1, df2], axis=1)
result

[Output]
    a    b    c    a    b   c   d
0  a0   b0   c0   NaN  NaN  NaN  NaN
1  a1   b1   b1   a1   b1   c1   d1
2  NaN  NaN  a2   a2   b2   c2   d2
3  NaN  NaN  a3   a3   b3   c3   d3

이때 보면 느꼈겠지만 pd.concat()함수는 default로 outer를 가진다.

outer: 합집합
inner: 교집합

이때 그러면 inner옵션을 줘보도록 하자.

pd.concat(join=’inner’)을 하는 경우

result = pd.concat([df1, df2], axis=1, join='inner')
result

[Output]
    a    b    c    a    b   c   d
1  a1   b2   c3   a1   b1   c1  d1

pd.merge() > 데이터프레임 병합

두 데이터프레임을 각 데이터에 존재하는 고유값(key)을 기준으로 병합할 때 사용(공통된 열 혹은 인덱스를 기준으로 두 테이블을 합침)

디폴트는 pd.merge(df_left, df_right, how=’inner’, on=None)이다. 예시로 위에 만들었던 데이터프레임을 다시 사용할 것이다. (이떄 on은 기준이 되는 열을 지정해주는 매개변수를 의미)

left, right: 병합하려는 두 데이터프레임
on: 기준이 되는 열 이름
how(->join): 병합 방식, 기본은 inner(교집합) outer(합집합) left(왼쪽값 기준) right(오른쪽값 기준)
suffixes: 중복된 열 이름에 접미사 추가 (기본값: ‘_x’, ‘_y’)

좀 더 보기 편한 데이터를 가져와 예시를 들어본다.

fruit = pd.DataFrame({'Num':[123, 456, 789, 1011, 1112], 
                      'Fruit':['Apple', 'Banana', 'Cherry', 'Lemon', 'Peach'], 
                      'Grade':['A', 'B', 'A', 'D', 'E']})

grade = pd.DataFrame({'Num':[123, 789, 1314, 1011], 
                      'Grade':['A', 'B', 'C', 'D']})

pd.merge() 그냥 해보는 경우

아무 옵션을 적용하지 않으면, on=None이기에 두 데이터의 공통된 열인 Num과 Grade를 기준으로 교집합인 데이터가 반환된다.

result = pd.merge(fruit, grade)
result

여기서 pd.merge(fruit, grade)는 pd.merge(fruit, grade, on=[‘Num’,’Grade’])와 동일하다.

pd.merge(fruit, grade, how=’outer’)의 경우

merge()의 how는 inner(교집합)가 디폴트이기때문에 outer(합집합)인 경우를 보겠다.

result = pd.merge(fruit, grade, how='outer')
result

Grade에 존재하지 않았던 Fruit 값은 NaN으로 들어가있음을 볼 수 있고, 공통적으로 있던 값은 하나로 합쳐져 출력된 것을 볼 수 있다.

pd.merge(fruit, grade, how=’left or right’)

how=’left’

result = pd.merge(fruit, grade, how='left')
result

fruit에 관한것만 나오는것을 볼 수 있다. 그 이유는 pd.merge(fruit, grade, how=’left’)에서 데이터프레임의 순서가 fruit, grade 순서로 병합해준 것이기 때문이다. 따라서 왼쪽에 위치만 fruit에 관련된 데이터만 출력된 것을 볼 수 있다.

how=’right’

result = pd.merge(fruit, grade, how='right')
result

여기서도 마찬가지로 grade에 관련된 데이터만 나왔고, 비어있는 값에 대해서는 NaN으로 출력되어있다.

열을 지정해주는 경우

result = pd.merge(fruit, grade, on='Num')
result  

공통된 열 중에 Num 하나만 지정해주는 경우 재밌는 결과가 나온다.

Num을 기준으로 Fruit 데이터가 나오고 그에 대한 fruit, grade의 Grade 데이터가 나왔다.

열을 지정해주고 합집합으로 지정한 경우

result = pd.merge(fruit, grade, on='Num', how='outer')
result

공통된 열이 아닌 열을 기준으로 지정할때

result = pd.merge(fruit, grade, on='Fruit')
result 

당연히 에러가 뜬다

데이터프레임을 병합하는데에 있어서 흥미로웠던 점은 inner join을 했음에도, 공통되지 않은 열이 같이 결합되어 나왔다는 점이었다.

import pandas as pd
df1 = pd.DataFrame({'a':['a0','a1'],
                   'b':['b0','b1'],
                   'c':['c0','c1']},
                   index = [0,1])

df2 = pd.DataFrame({'a':['a1','a2','a3'],
                   'b':['b1','b2','b3'],
                   'c':['c1','c2','c3'],
                   'd':['d1','d2','d3']},
                   index = [1,2,3])

이렇게 데이터프레임 df1, df2를 각각 만들고 이 둘을 merge해본다고 하자.

result = pd.merge(df1,df2)
result

기본 how=inner'이기 떄문에 나는 당연하게 공통된 열 a,b,c에 대한 데이터만 나올 것이라고 생각했다. 혹여 d열이 나오더라도 안의 값은 NaN이 나오지 않을까? 했었다. 근데 이 merge를 함에 있어서 일정한 규칙이 있다고 한다.

즉, 이론상으로는 교집합만 합쳐지는 것이 맞지만 파이썬에서는 조금 다르게 설계 되어있다고 한다.

컬럼(열)정렬을 우선 > 각 데이터프레임이 가지고 있는 모든 열이 합해진다. 이때 공통된 컬럼이 기준으로 정렬되는 것. 중요한 것은 일단 모든 열이 다 합해진다는 것(d열이 나오는 이유)
로우(행) 정렬 > 값이 있으면(값이 올수있다면) 일단 다 가져온다. 이때 없는 경우 NaN이 채워진다.(d1이 나오는 이유)

다시 교집합을 하는 방법을 정리해보면,

데이터프레임이 가진 모든 열이 합쳐지고
교집합에 부합하는 행과 열이 있다면
교집합에 해당하지 않은 행 값은 탈락되지 않고
공통되는 행과 열에 남아 들어온다

이러한 이유는 SQL과 Pandas의 디자인 철학 때문이라고 한다.

기본적으로 join조건은 행을 매칭하는 기준으로 사용
데이터분석을 하는 경우, 더 많은 경우에 관련된 전체 정보가 필요함

따라서, SQL과 Pandas는 데이터분석을 위한 도구로서 데이터분석을 하기에 가장 좋은 방식으로 디자인되어 이렇게 설계된것이라고 이해하면 쉬울 것 같다!

궁금증 완료 !

Comment Read more

Older Newer

지혜의 개발공부로그

자료구조, 알고리즘 문제 풀어보기(우주선 긴급 암호 해독)

문제 1: 우주선 긴급 암호 해독

테마/상황:

미션:

자료구조, Queue

Queue

FIFO: First In First Out

주요 연산

Python으로 구현해보는 queue

큐 예제 > 조세푸스(josephus)

case1, 그냥 풀어보기

case2, deque 활용해서 풀어보기

자료구조, Stack

Stack

LIFO: Last In First Out

주요 연산

Python으로 구현해보는 stack

스택 예제 > 괄호 맞추기

자료구조, 재귀함수

재귀함수

재귀함수의 주의점

Pandas 데이터프레임 합치기(concat, merge)

데이터프레임 합치기

pd.concat() > 데이터프레임 붙이기

pd.concat(axis=1)을 하는 경우

pd.concat(join=’inner’)을 하는 경우

pd.merge() > 데이터프레임 병합

pd.merge() 그냥 해보는 경우

pd.merge(fruit, grade, how=’outer’)의 경우

pd.merge(fruit, grade, how=’left or right’)

열을 지정해주는 경우

열을 지정해주고 합집합으로 지정한 경우

공통된 열이 아닌 열을 기준으로 지정할때