알루 코딩

스택의 어원은 '쌓는다' 입니다. 어원에서 짐작할 수 있듯이, 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조입니다. 이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 후입선출 혹인 LIFO(Last IN First Out)이라고 합니다. 이 때, 스택에 삽입하는 연산을 push, 꺼내는 연산을 pop 이라고 합니다. 📖 스택의 동작 원리 이해하기 빈 통(빈 스택)에 사탕을 넣는다고 하면, 아래와 같이 나타낼 수 있습니다. 📖 스택의 ADT ADT는 우리말로 추상 자료형(abstract data type)인데요, 추상 자료형이란 인터페이스만 있고 실제로 구현은 되지 않은 자료형입니다. 일종의 자료형의 설계도라고 생각하면 됩니다. 그렇다면 스택은 어떤 정의가 필요한 자료구조일까요? 우선 스택에는 ..

배열은 인덱스와 값을 일대일 대응에 관리하는 자료구조입니다. 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있습니다. 데이터에 한 번에 접근할 수 있으니 어디에 있는지만 알면 빠르게 탐색할 수 있는 것이죠. 이런 접근 방식을 임의 접근(random access)라고 합니다. 📖 배열 선언 배열을 선언하는 방법은 다음과 같습니다. 이름이 arr 이고 길이가 8인 정수형 배열을 리스트를 활용해서 선언하는 3가지 방법을 예제를 통해서 알아보겠습니다. 1) 일반적인 방법 arr = [0,0,0,0,0,0,0,0] arr = [0] * 8 # 결과는 둘 다 동일합니다. 2) 리스트 생성자를 사용하는 방법 arr = list(range(8)) # [0..

이번 포스팅에서는 파이썬 기초 문법을 충실히 설명하기보다는 코딩 테스트에 자주 사용하는 문법을 설명하는 데 집중합니다. 📖 빌트인 데이터 타입? 빌트인 데이터 타입(built-in data type)은 언어 자체에서 제공하는 데이터 타입과 컬렉션 데이터 타입이 있습니다. 기본 데이터 타입으로는 정수형(Int), 부동소수형(Float), 문자열 타입이 있고 컬렉션 데이터 타입으로는 리스트, 튜플, 셋, 딕셔너리 등이 있습니다. 1) 정수형 - 정수형은 양과 음의 정수, 0을 포함합니다. 여러가지 연산을 할 수 있죠. - 정수형 변수 선언 a = 13 b = 4 - 정수형 산술 연산 print(a+b) # 더하기 17 print(a-b) # 빼기 9 print(a*b) # 곱하기 52 print(a/b) #..

코딩 테스트에서는 제약사항에 따라 빠르게 풀리는 알고리즘으로 문제를 풀어야 할 때가 있습니다. 시간 복잡도를 기준으로 알고리즘을 택해야 하는데, 그럼 시간 복잡도라는 것이 도대체 무엇일까요? 📖 시간 복잡도란? 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미합니다. 시간 복잡도는 낮으면 낮을 수록 좋습니다. 예를 들어, 1차원 배열에서 특정 값을 찾는다고 가정해봅시다. 어떤 경우에 가장 빨리 값을 찾게 되고, 어떤 경우에 가장 늦게 값을 찾게 될까요? 1) 값을 가장 빨리 찾는 경우 - 값을 가장 빨리 찾는 경우는 검색 시작 위치에 찾고자 하는 값이 바로 있는 경우입니다. target = 1 array = [1,5,2,6,3,17,13,9] # 찾고자 하는 값 1이 arra..

순차 탐색 이진탐색 알고리즘을 배우기 전에 가장 기본 탐색 방법인 순차 탐색 방법에 대해 알아보자. 순차 탐색이란, 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례로 확인하는 방법이다. 말그대로, 순차적으로 탐색을 한다는 의미인데, count() 함수를 이용할 때도 내부에서는 순차 탐색이 수행될 정도로 자주 사용된다. N개의 데이터에서 최대 N번의 비교 연산이 필요하므로 순차 탐색의 시간복잡도는 최악의 경우, O(N)이다. 순차 탐색 코드는 아래와 같다. import sys input = sys.stdin.readline # 순차 탐색 소스코드 구현 def sequential_search(n,target,array): # 각 원소를 하나씩 확인하며 for i in range(..

신장 트리 : 신장 트리(Spanning Tree)란 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하기 때문에, 이러한 그래프를 신장 트리라고 부르는 것이다. 예를 들어보자. 크루스칼 알고리즘 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장 트리를 찾아야 하는데, 이처럼 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '신장 트리 알고리즘'이라고 한다. 대표적인 신장 트리 알고리즘으로는 '크루스칼 알고리즘(Kruskal Algorithm)'이 있다. 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. 모든 간선에 대하여 정렬을..

'DFS/BFS'와 '최단 경로'에서 다룬 내용도 그래프 알고리즘의 한 유형으로 볼 수 있다. 그래프 알고리즘은 코딩 테스트에서 출제 비중이 낮은 편이지만, 출제되기 때문에 기타 그래프 알고리즘도 살펴볼 필요가 있다. 지금부터 다룰 알고리즘은 앞서 배운 내용에 기반하는데, 예를 들어 크루스칼 알고리즘(Kruskal Algorithms)은 그리디 알고리즘으로 분류되고, 위상 정렬 알고리즘(Topology Algorithms)은 앞서 배운 큐 자료구조 혹은 스택 자료구조를 활용해야 구현할 수 있다. 복습을 해보자면, 그래프란 노드와 간선의 정보를 가지고 있는 자료구조이고, 알고리즘 문제에서 '서로 다른 개체가 연결되어 있다'는 얘기가 있다면 가장 먼저 그래프 알고리즘을 떠올려야 한다. 더불어, 그래프 자료구..

최단 경로(Shortest Path) 란 ? : 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. '길 찾기' 문제라고도 불리는데, 다양한 유형이 있다. 예를 들어, "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우" 나 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우" 등이 있다. 보통, 최단 경로 문제는 그래프를 이용해 표현하는데, 각 지점은 그래프에서 '노드(node)'로 표현되고, 각 지점마다 연결된 도로는 그래프에서 '간선(edge)'으로 표현된다. 코딩 테스트에서는 보통 최단 경로를 모두 출력하는 문제보다는 '최단 거리'를 출력하는 문제가 많다. 학부 수준에서 다루는 최단 거리 알고리즘은 대표적으로 아래와 같다. 1. 다익스트라 알고리즘 2. 플로이드 워..

다이나믹 프로그래밍(동적 계획법) 이란 ? : 컴퓨터 연산을 하면서 중복되는 연산을 줄이자는 목적으로 나온 기법이다. 보통, 다이나믹이라고 하면 '프로그램이 실행되는 도중에' 라는 의미로 쓰이는데(ex.동적할당), 여기서는 그런 의미는 아니다. 연산을 줄이자는 것이 목적이라면, 재귀함수로 프로그램을 짤 수도 있는 것 아니냐고 생각할 수 있다. 물론, 할 수는 있다. 하지만, 수가 크다면, 실행시간은 기하급수적으로 늘어나기 때문에, 계속해서 재귀함수를 호출하는 것은 컴퓨터에 많은 부하를 줄 수 있다. 예를 들어, 피보나치 수열을 재귀함수로 구현한다면, n이 100 이기만 해도, 연산 횟수가 약 1,000,000,000,000,000,000,000000,000,000번이다. 즉, 1초에 1억번 정도의 연산을..

정렬(Sorting)이란 ? : 데이터를 측정한 기준에 따라서 순서대로 나열하는 것으로, 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘은 굉장히 다양한데, 이 중에서 많이 사용하는 정렬은 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등이 있다. 정렬 알고리즘을 잘 공부하면, 알고리즘의 효율을 높일 수 있다. 또한, 코딩 테스트에서의 정렬 알고리즘 문제는 어느 정도 정해진 답이 있어서, 외워서 잘 풀어낼 수 있는 문제라고도 할 수 있다. 오름차순을 기준으로 각 정렬을 살펴보자. 선택 정렬(Selection Sort) : 데이터가 무작위로 있을 때, 그 중 가장 작은 값을 선택해 맨 앞에 있는 값과 바꾸고, 그 다음 작은 값을 선택해 앞에서 두 번째 값과 바꾸는 과정을 계속 ..