알루 코딩

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

문제 설명 더보기 문제 처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다. 이 CPU는 다음과 같은 특징이 있습니다. CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다. 한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다. 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다. 처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요. 제한 코어의 수는 10,000 이하 2이상 입니다. 코어당 작업을 처리하는 시간은 10,000이하 입니다. 처리해야 하는 일의 개수는 50,00..

문제 설명 더보기 문제 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원을 5개 사용해서 거슬러 준다. 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다. 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다. 5원을 1개 사용해서 거슬러 준다. 거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를..

문제 설명 더보기 문제 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다. 제한 문자열 s의 길이 : 2,500 이하의 자연수 문자열 s는 알파벳 소문자로만 구성 입출력 예시 입출력 예 s answer "abcdcba" 7 "abacde" 3 입출력 예 설명 입출력 예 #1 4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다. 입출력 예 #2 2번째자리 'b'를 기준으로 "aba"가 팰린드롬..

더보기 문제 사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다. 예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다. ((1 - 5) - 3) = -7 (1 - (5 - 3)) = -1 위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다. 또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다. (((1 - 3) + 5) - 8) = -5 ((1 - (3 + 5)) - 8) = -15 (1 - ((3 + 5) - 8)) = 1 (1 - (3 + (5 - 8))) = 1 ((1 - 3) + (5 - 8)) = -5 위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, ..

그리디(Greedy) 알고리즘 : 욕심쟁이 알고리즘이라고도 하는 탐욕 알고리즘은 단순하지만 강력한 문제 해결법이다. 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 그리디 알고리즘은 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 가장 좋은 것을 선택하는 알고리즘으로, 문제에서 '가장 큰 순서대로' 혹은 '가장 작은 순서대로' 와 같은 기준을 문제에서 알게 모르게 제공해준다. 정렬 알고리즘을 사용했을 때, 효과적으로 풀 수 있어, 보통 정렬 알고리즘과 짝을 이루어 출제되곤 한다. 대표적인 그리디 알고리즘 예제 - 1) 동전 거스름돈 문제 import sys input = sys.s..