[내일배움캠프] 2022-11-23 TIL

자료구조 & 알고리즘 특강 (강창민 튜터님)

알고리즘의 정의

어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합. 여러 단계의 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다. [표준국어대사전]

인상깊었던 문제 (예제 3)

1. 입력으로 소문자의 알파벳 순으로 정렬된 문자열이 입력됩니다.

2. 각 알파벳은 중복이 가능합니다.

3. 중간에 없는 알파벳이 있을 수도 있습니다. 입,출력 예시와 같이 입력 문자열에 나타나는 각 알파벳의 종류,갯수를 요약하여 나타내시오.

 

# 문제의 번호별 조건에 대한 입력 예시와 출력
Ex 1)
abc  # a1/b1/c1

Ex 2-1)
aaabbbc # a3/b3/c1

Ex 2-2)
abbbc # a1/b3/c1

Ex 3-1)
ahhhhz # a1/h4/z1

Ex 3-2)
acccdeee # a1/c3/d1/e3

 

 

내가 구현한 코드

def solution(input_string):
    alphabet_set = sorted(set(input_string))
    answer = []
    for alphabet in alphabet_set:
        answer.append(f'{alphabet}{input_string.count(alphabet)}')
    return answer

print('/'.join(solution(input())))

반복문을 통해 다양한 풀이가 가능한 문제인데, 집합(set)을 공부한 것에서 아이디어를 떠올려 최대한 간단한 코드를 구상해보았다.

 

자료구조 알고리즘 원격 강의 진도 나가기

스택

• 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조 = Last In First Out(LIFO)
• 되돌리기 기능처럼 행동들을 순서대로 기억해야할 때 등에 활용
• 파이썬에서는 list가 스택 자료구조로 활용 가능

큐

• 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조 = First In First Out(FIFO)
• 먼저 들어온 순서대로 처리되어야 할 때, 먼저 해야하는 일을 정리해야 할 때 등에 활용

해쉬 테이블 

• 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 
• 데이터의 검색과 저장이 아주 빠르게 진행된다.
• 딕셔너리가 해쉬테이블과 같은 말