🤖 옌지니어의 IT 기록 🤖

큐(Queue)란?

먼저 들어간 데이터가 먼저 나오는 자료구조

• FIFO(First In First Out) : 선입선출
• push : 큐에 삽입하는 연산 / pop : 큐에서 꺼내는 연산

큐의 동작원리

큐의 특성을 활용하는 분야

여러 이벤트가 발생했을 때 발생한 순서대로 처리하는 작업

• 작업 대기열 : 네트워크 통신 시 다수의 클라이언트에서 서버에 작업을 요청하면 들어온 순서대로 작업 처리
• 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자 이벤트(키보드/마우스) 처리

큐의 ADT (Abstract Data Type)

• 스택과 유사하지만 스택의 top → 큐의 front(앞) / rear(뒤)
  • 큐는 앞에서 데이터를 빼고 뒤에서 넣으므로 앞뒤 최종위치 저장 필요

큐의 세부동작

큐 구현하기

1) 리스트를 활용하는 방식

• push : append( )
• pop : pop( )
  •  첫 번째 데이터를 제거해야 하므로 pop(0) 사용

queue = []

# 큐에 데이터 추가
queue.append(1)
queue.append(2)
queue.append(3)

# 큐의 맨 앞 데이터 제거
first_item = queue.pop(0)
print(first_item)

# 큐에 데이터 추가
queue.append(4)
queue.append(5)

# 큐의 맨 앞 데이터 제거
first_item = queue.pop(0)
print(first_item)

2) 덱을 활용하는 방식

• DEQ(Double Ended Queue)
• 양 끝에서 삽입이나 삭제할 수 있는 큐를 구현한 것

from collections import deque

queue = deque()

# 큐에 데이터 추가
queue.append(1)
queue.append(2)
queue.append(3)

# 큐의 맨 앞 데이터 제거
first_item = queue.popleft()
print(first_item)

# 큐에 데이터 추가
queue.append(4)
queue.append(5)

# 큐의 맨 앞 데이터 제거
first_item = queue.popleft()
print(first_item)

※ 참고 자료 ※

https://wikidocs.net/221191

스택(Stack)이란?

먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조

• FILO(First In Last Out) : 먼저 들어간 것이 마지막에 나오는 규칙
• push : 스택에 삽입하는 연산 / pop : 스택에서 꺼내는 연산

스택의 동작원리

스택의 ADT (Abstract Data Type)

추상 자료형이라는 뜻으로 인터페이스만 있고 실제로 구현은 되지않은 자료형

스택의 세부동작

스택 구현하기

stack = []          # 스택 리스트 초기화
max_size = 10       # 스택의 최대크기

# 스택이 가득찼는지 확인하는 함수
def isFull(stack):
    return len(stack) == max_size

# 스택이 비어있는지 확인하는 함수
def isEmpty(stack):
    return len(stack) == 0

# 스택에 데이터를 추가하는 함수
def push(stack, item):
    if isFull(stack):
        print("스택이 가득 찼습니다.")
    else:
        stack.append(item)
        print("데이터가 추가되었습니다.")

# 스택에서 데이터를 꺼내는 함수
def pop(stack):
    if isEmpty(stack):
        print("스택이 비어있습니다.")
        return None
    else:
        return stack.pop()

• 파이썬의 리스트는 크기를 동적으로 관리하므로 실제 코드에서 max_size, isFull(), isEmpty() 함수 구현 X
• push(), pop() 함수가 하는 일은 리스트의 메서드를 호출하는 것 뿐이므로 굳이 구현 X
• 위의 코드를 아래 코드로 바꾸어서 사용

stack = []

# 스택에 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)

# 스택에서 데이터 꺼내기
top_element = stack.pop()	# top_element = 3
next_element = stack.pop()	# next_element = 2

# 스택의 크기 구하기
stack_size = len(stack)

→ 스택의 개념 자체는 어렵지 않지만 문제를 보고 스택을 떠올리기 위해 문제연습이 필요 !!

※ 참고 자료 ※

https://wikidocs.net/221191

배열

인덱스와 값을 일대일 대응해 관리하는 자료구조

• 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응
• 어떤 위치에 있는 데이터든 한 번에 접근 가능 → 임의 접근 (random access)

배열을 선언하는 방법

# 1. 일반적인 방법
arr = [0,0,0,0,0,0]
arr = [0] * 6

# 2. 리스트 생성자를 사용하는 방법
arr = list(range(6))			# [0,1,2,3,4,5]

# 3. 리스트 컴프리헨션을 활용하는 방법
arr = [0 for _ in range(6)]		# [0,0,0,0,0,0]

※ 파이썬의 경우 배열 대신 리스트를 사용 ※

배열과 차원

• 배열은 2차원, 3차원과 같이 다차원 배열로도 사용
• 컴퓨터 메모리 구조는 1차원이므로 다차원 배열도 1차원 공간에 저장
• 배열은 차원과 무관하게 메모리에 연속 할당

1차원 배열

• 가장 간단한 배열 형태
• 배열의 모습 = 메모리에 할당된 실제 배열의 모습

2차원 배열

• 1차원 배열을 확장한 것

# 2차원 배열을 리스트로 표현
arr = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

# 저장된 값 출력
print(arr[2][3])

# 저장된 값을 변경
arr[2][3] = 15

# 리스트 컴프리헨션을 활용
arr = [[i]*4 for i in range(3)]

배열 연산의 시간 복잡도

• 배열은 임의 접근이라는 방법으로 모든 위치에 있는 데이터에 단 한 번에 접근 가능
• 데이터에 접근하기 위한 시간복잡도는 O(1)

배열에 데이터를 추가하는 경우

(1) 맨 뒤에 삽입할 경우

• 다른 데이터 위치에 영향 X
• 시간복잡도 = O(1)

(2) 맨 앞에 삽입할 경우

• 기존 데이터들을 뒤로 한 칸씩 미는 연산 필요
• 시간복잡도 = O(N)

(3) 중간에 삽입할 경우

• 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산 필요
• 시간복잡도 = O(N)

배열을 선택할 때 고려할 점

• 할당할 수 있는 메모리 크기 확인
  • 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당 실패
  • 보통 정수형 1차원 배열은 1000만개, 2차원 배열은 3000*3000 크기가 최대
• 중간에 데이터 삽입이 많은지 확인
  • 배열은 선형 자료구조이므로 빈번하게 삽입하면 시간 초과 발생

코딩 테스트를 준비하기 위해 알고리즘 공부가 필요하다. 관련 강의와 책을 찾아보면서 정리할 예정이고 그 전에 코딩 테스트를 효율적으로 준비하기 위한 방법들을 정리해보았다. ("코딩테스트 합격자되기 파이썬편" 참고)

코딩 테스트 공부방법

"아는 것과 모르는 것을 정확하게 구분하기"

1. 기록

- 어떤 알고리즘을 적용하려고 했는지

- 근거는 무엇인지

- 알고리즘을 어떻게 코드로 만드려고 했는지

2. 시험 보듯이 공부

- 주어진 시간을 효율적으로 사용

- 긴장감을 연습

3. 짧은 시간으로 코딩테스트 통과는 불가능

- 최소 한 달에서 두 달 정도 집중해서 공부

4. 나만의 언어로 요약

- 이해한 뒤에 요약은 필수

- 제대로 이해했는지 확인하는 과정

문제를 분석하는 법

코딩 테스트 = 문제 풀이 능력을 확인하는 것

→ 문제 분석에 시간 투자 필요 (50%~60% 정도)

1. 문제를 쪼개서 분석

2. 제약 사항을 파악하고 테스트 케이스 추가
- 어떤 알고리즘을 사용할지 고민할 때 유용
- 추후 코드를 구현하는 단계에서 예외를 거르기 편리

3. 입력값을 분석
- 알고리즘의 시간 복잡도는 입력값이 결정
- 입력값의 크기를 확인하여 문제를 제한시간 내에 풀 수 있는지 확인

4. 핵심 키워드 파악

5. 데이터 흐름이나 구성 파악

의사코드로 설계하는 연습

의사코드란?

프로그램의 논리를 설명하고 알고리즘을 표현하기 위해 작성한 일종의 지침

의사코드의 원칙
1. 프로그래밍 언어로 작성하면 안된다.
2. 일반인도 이해할 수 있는 자연어로 작성해야 한다.
3. 일정한 형식이 없다. (자유롭게 작성)

의사코드를 작성하는 방법
1. 세부 구현이 아닌 동작 중심으로 작성
2. 문제 해결 순서로 작성
3. 충분히 테스트

※ 참고 자료 ※

https://wikidocs.net/221191

프로그래머스 Lv.2를 풀려고 하는데 난이도가 너무 어려워져 당황스러웠다. 친구가 알고리즘 공부부터 해야한다면서 코딩테스트 공부법 관련 자료를 보내줘서 나름대로 정리해서 공부해보려고 한다. 해야할 것이 너무 많은데 아무것도 안하고 있는 나...너무 대단하다...!!

1단계. 기본 문법 및 자료구조

어떤 언어로 코딩테스트를 볼 것인지 결정하고 기본적인 문법과 자료구조 공부

1) 프로그래밍 언어 선택

편하고 익숙한 프로그래밍 언어 선택하고 기본적인 문법 공부

2) 자료구조 공부

• 공부 순서
  • 배열 (Array)
  • 연결 리스트 (Linked List)
  • 스택 (Stack)
  • 큐 (Queue)
  • 해시 테이블 (Hash Table)
  • 트리 (Tree)
  • 힙 (Heap)
  • 그래프 (Graph)
• 공부 방법
  • 자료구조의 목적과 이론 이해 (책이나 강의 활용)
  • 자료구조의 구현 로직 따라하며 내부 작동원리 파악 (구글 검색)
  • 자료구조를 적용하여 문제 해결 (코딩 연습 사이트 이용)

2단계. 알고리즘 이론

문제를 풀기 위해 자주 사용되는 알고리즘 공부

1) 기본적인 개념 공부

• 이진 탐색 (Binary Search)
• 정렬 (Sorting)
• 완전 탐색 (Exhaustive Search)
• 재귀 (Recursion)
• 깊이 우선 탐색 (DFS)
• 너비 우선 탐색 (BFS)
• 동적 프로그래밍 (DP, Dynamic Programming)
• 백 트래킹 (Backtracking)

2) 빅오 표기법 (big-O notation) 마스터

• 하나의 문제를 해결하는 여러 방법의 효율성을 비교하기 위한 척도
• 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용

3단계. 알고리즘 문제 풀이

기본적인 이론을 공부하고 문제 풀이

1) 알고리즘 기출문제 플랫폼

• 국내
  • 백준 : https://www.acmicpc.net/problemset
  • 프로그래머스 : https://school.programmers.co.kr/learn/challenges
  • 코드업 : https://codeup.kr/problemset.php
• 해외
  • Hackerearth : https://www.hackerearth.com/practice/
  • Hackerrank : https://www.hackerrank.com/dashboard
  • Leetcode : https://leetcode.com/problemset/

2) 문제풀이 팁

• 간단한 문제부터 시작
• 시간을 정해놓고 시간이 지나도 못풀었을 경우 정답 확인
• 빅오 표기법으로 시간 및 공간복잡도 분석
• 풀고 난 후에는 다른 사람의 풀이 참고

※ Reference ※

코딩테스트 4단계 공부법 🌟

코딩테스트 준비(알고리즘 공부) 커리큘럼 🌟

→ 기본적인 단계 설정에 도움이 많이 된 블로그

자료구조를 공부하기 위한 5가지 단계

코딩테스트 대비를 위한 백준 문제 추천