알루 코딩

스택의 어원은 '쌓는다' 입니다. 어원에서 짐작할 수 있듯이, 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조입니다. 이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 후입선출 혹인 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..

오늘은 백준 2589번 '보물섬' 문제에 대해 가져와봤습니다. 해당 문제는 전형적인 bfs 문제인데, 우리가 이런 BFS 문제를 풀 때 놓치면 안될 점들을 상기하면서 문제를 설명드리겠습니다. "보물섬"문제는 주어진 지도에서 최단거리로 갈 수 있는 가장 먼 거리에 있는 두 지점을 찾는 문제입니다. 지도는 'L'(땅)과 'W'(바다)로 구성되어 있으며, 이동은 상하좌우로만 가능합니다. 이 문제의 핵심은 가장 긴 최단 거리를 찾는 것입니다. 해당 문제를 봤을 때, 뭔지 정확히는 모르셔도 '전형적인 그래프 탐색 알고리즘일 것이다' 라고 느끼셨을 겁니다. 맞습니다. 저는 이 문제를 보고 'bfs 알고리즘을 활용하면 뭔가 풀릴 것 같은데?' 라는 직감을 느꼈습니다. BFS 알고리즘을 이용하면 모든 가능한 경로를 탐..

문제를 먼저 해석해봅시다! 문제에서는 직사각형 모양의 판에 치즈가 표시되어 있습니다. 치즈는 1로 표시되며, 치즈가 없는 부분은 0으로 표시됩니다. 각 시간 단위마다 외부 공기와 접촉한 치즈가 녹아 없어지는데요, 이 때, 치즈의 내부에 있는 공기는 외부 공기로 간주되지 않는게 핵심입니다! 문제의 목표는 모든 치즈가 녹는 데 걸리는 시간과 마지막으로 녹기 전의 치즈 조각의 수를 찾는 것입니다. 이를 위해 BFS 알고리즘을 사용합니다. BFS는 주로 그래프의 최단 경로를 찾거나, 2차원 배열에서 특정 조건에 따라 요소를 탐색할 때 사용되는 알고리즘입니다. 이 문제에서는 BFS를 이용해 보드의 가장자리부터 시작하여 외부 공기를 탐색하고, 이를 통해 치즈의 녹는 경계를 식별합니다. 외부의 공기와 내부의 공기를 ..

이 문제는 DFS와 BFS를 결합한 흥미로운 접근 방식을 요구합니다. 이 문제의 핵심은 "가능한 한 많은 영역을 안전하게 보호하는 벽의 배치를 찾는 것" 입니다. 여기서 주목해야 할 점은 "모든 벽의 조합을 시도"해보고, "각 경우에 대해 바이러스가 얼마나 퍼지는지를 시뮬레이션"해야 한다는 것입니다. 이를 위해서 DFS를 사용해 벽을 세우고, BFS로 바이러스의 확산을 시뮬레이션합니다. 초기 접근 방법은 아래와 같습니다. from collections import deque import sys input = sys.stdin.readline # 벽을 3개를 세운다. -> 모든 경우의 수를 다 세어본다 : dfs # 바이러스를 퍼뜨려본다. # 0의 개수를 구한다. # 이 값을 max값과 계속 비교하면서 최..

이 문제를 처음봤을 때, 최장수열과 관련한 풀이가 떠올랐습니다. 최장수열은 대표적인 DP 유형의 문제로서 기억을 하고 있기에 보자마자 DP를 활용해보고자 했습니다. 이 문제의 핵심은 문자열 S를 순회하면서 반복되지 않는 문자를 가지는 문자열의 최대 길이를 반환하는 것입니다. 그렇다면, 순회를 할 때 계속해서 알아야 하는 값은 현재 위치에서 조건에 맞는 문자열을 만들 수 있는 최장길이 이전에 똑같은 문자가 나왔는지에 대한 여부 로 정리할 수 있겠습니다. 그럼, 바로 코드를 살펴보고, 코드 해석을 해보도록 하겠습니다. 코드는 아래와 같습니다. class Solution(object): def lengthOfLongestSubstring(self, s): if s == "": return 0 dp = [1] ..

이 문제를 푸는 것에 있어서 O(n^2)으로는 바로 풀 수 있겠지만, 결과적으로 시간초과가 나고, follow up을 보면, 공간복잡도를 O(1)로 풀기를 제안하고 있습니다. 처음에 제가 접근한 방식은 배열의 길이를 2배로 늘려서 [1,2,3,4] 가 인풋 배열이라면, [1,2,3,4,1,2,3,4] 로 만든 후, 1을 바라볼 때는, [2,3,4] 의 곱을 2를 바라볼 때는 [3,4,1], 3을 바라볼 때는 [4,1,2], 4를 바라볼 때는 [1,2,3] 을 곱해서 결과 배열을 만드려고 했습니다. 위와 같은 방식으로 문제를 풀 때, 많은 변수들이 필요했고, 파이썬의 for문을 돌면서, index를 다시 뒤로가도록 하는 것에 있어서 어려움을 겪었습니다. 결국, 저는 문제를 O(n)의 방식으로 30분만에 풀..

처음에 그냥 생각나는 로직대로 푼 알고리즘은 다음과 같습니다. nums를 처음부터 더하는데, target보다 같거나 커지면, check 변수를 통해 플래그를 걸어 놓고 여태 더했던 순회 횟수, 즉 길이를 저장합니다. 그리고 다음 인덱스로부터 또 같은 행동을 반복하는데, 최소 길이가 갱신 된다면 최소 길이를 갱신하고 그렇지 않다면 그냥 패스합니다. 풀었던 코드는 아래와 같습니다. 푼 코드는 아래와 같습니다. class Solution(object): def minSubArrayLen(self, target, nums): for i in range(len(nums)): tmp = 0 for j in range(i,len(nums)): tmp += nums[j] if tmp >= target : length ..