문제 링크https://www.acmicpc.net/problem/2609문제 풀이 과정최대공약수와 최소공배수 문제에 대해 효율적으로 풀기 위해서는 유클리드 호제법에 따라 최대공약수를 푸는 방법에 대해 알아야 손쉽게 풀 수 있다.유클리드 호제법이란 2개의 자연수에 대한 최대공약수를 구하는 방식이다. 쉽게 설명하면 두 수 a,b에 대해서 더 작은 수로 나눈 나머지로 끊임없이 0이 될때까지 나누는걸 의미한다. 이걸 쉽게 설명하려면 아래 예시가 가장 쉽게 이해가 된다.더보기1. 1500 ÷ 3261500을 326으로 나눈 몫은 4이고, 나머지는 196이야.즉, 1500 ÷ 326 = 4 (몫), 나머지 1962. 326 ÷ 196이제 326을 196으로 나눠. 몫은 1이고, 나머지는 130이야.즉, 326 ÷..
코딩테스트
문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 풀이 과정from collections import dequedef solution(priorities, location): # 초기화 queue_list = deque(enumerate(priorities)) answer = [] while queue_list: current = queue_list.popleft() # 현재 프로세스보다 우..
문제 링크https://www.acmicpc.net/problem/10828문제 풀이 과정# 스택# 링크 : https://www.acmicpc.net/problem/10828from sys import stdininput = stdin.readlineclass Stack: def __init__(self): self.__stack = [] self.__size = 0 def empty(self): if not self.__stack: return 1 else: return 0 def size(self): return self.__size def push(self, item): ..
문제 링크 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 풀이 과정위 문제를 풀 때 두 가지 사항에 대해서 고려해서 문제를 풀어야겠다는 생각을 했다. 올바르지 못한 괄호가 나오는 경우는 크게 2가지로 나눠서 생각을 했다.처음부터 닫는 괄호가 나올 경우.괄호를 열었지만 개수만큼 닫지 않은 경우.위 2가지 사항을 고려해서 함수를 다음과 같이 구성하니 문제가 정상적으로 해결되었다.def solution(s): answer = [] # 1. 괄호가 열기 전에 닫는 기호가 나올 경우 if s[0] == ")": return False ..
문제 링크 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 풀이 과정def solution(arr): answer = [] check_number = arr[0] for i in range(len(arr)): # 이전 숫자와 중복이라면 패스 # 이전 숫자와 같거나, 처음 값이 아니라면 if (arr[i] == check_number) and (i != 0): continue # 반복문을 순회하며 처음보는 숫자는 배열에 저장. answer.append(arr[i..
1. Stack이란?스택은 '쌓는다'라는 이름의 어원처럼 먼저 입력한 데이터를 제일 나중에 꺼내는 FILO(Last In, First Out)의 구조를 가진 자료구조를 의미합니다. 일상 생활에서도 많이 확인할 수도 있는 형태인데, 차례대로 쌓인 접시라던지 혹은 곽티슈에 담긴 휴지라던지 확인할 수 있습니다. 혹은 프로그램 내부에서도 이런 구조를 확인할 수 있는데 함수를 호출하게 되면 프로그램을 호출된 순서에 따라서 차곡차곡 저장하고, 함수가 종료될때마다 가장 나중에 호출된 함수부터 차례대로 해제됩니다.위 구조로 잘 이해가 가지 않는다면 아래와 같은 그림을 이해하면 더 쉽게 이해할 수 있습니다.. 예를 들어 어떤 데이터를 1, 2, 3 순서대로 넣었다면 가장 나중에 넣었던 3부터 차례대로 2, 1 순서로 꺼..
1. DP란? 동적 계획법은 간단히 말하면 전체 문제 혹은 큰 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들로 나눠서 해결하고 이것들을 활용해 전체 문제를 해결하는 방법이다. 말만 들어보면 다른 알고리즘인 분할정복과 유사하게 보인다. 다만 DP를 효율적으로 사용하기 위해서는 2가지 조건을 만족해야한다. 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 한다.(중복 부분 문제) 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 한다.(최적 부분 구조) 분할정복과 DP 모두 부분 문제로 나눠서 해결한 뒤 원래 문제의 해답을 얻지만, 분할정복은 반복되는 작은 문제가 없다. 반면에 위에서 살펴본 것처럼 DP는 반복되는 작은 문제가 있을 때 사용하는 알고리즘이다. ..
1. 탐욕(Greedy) 이란? 그리디 알고리즘은 문제 해결 과정에서 결정하는 순간마다 눈 앞에 보이는 최선의 선택을 하는 알고리즘을 뜻한다. 즉 해결 과정 전체, 혹은 미래의 상황을 고려하지 않고 당장의 순간에 최선의 선택을 고려하는 알고리즘이다. 다른 알고리즘에 비해 구현하기가 쉬움 실행 속도가 빠름 특정한 상황에서만 적용 가능. 그리디는 위에서 설명했듯이 모든 순간에 적용 가능한 알고리즘은 아니다. 그리디 알고리즘을 사용할 수 있는 특정한 상황은 다음과 같다. 최적 부분 구조 : 순간마다의 부분 최적해들의 합이 곧 전체 문제의 해답과 동일할 때만 사용 가능. 그리디 선택 속성 : 이전의 선택이 이후의 선택에 영향을 끼치지 않음. 2. 대표 예시 그리디의 대표적인 예시는 거스름돈 문제다. 다음 설명을..
