Algorithm
Q. 정렬 알고리즘에 대해 설명해주세요.
Q. 정렬 알고리즘에 대해 설명해주세요.
2019.06.03Q. 정렬 알고리즘에 대해 설명해주세요. Goal 정렬 알고리즘의 개념을 설명할 수 있다. 정렬 알고리즘의 종류에 대해 설명할 수 있다. 정렬 알고리즘의 개념 정렬 알고리즘이란 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 얼마나 효과적으로 해결하는 지가 정렬 알고리즘의 핵심 정렬 알고리즘이 중요한 이유 데이터가 정렬되어 있으면 이진탐색이라는 강력한 알고리즘을 사용할 수 있다. 대표적인 정렬의 종류 실제 응용에서는 상황에 따라 두 가지 이상의 정렬 방법을 사용하는 경우가 많다. 정렬 대상이 특정 크기 이하로 단편화될 때까지는 퀵 정렬을 쓰다가, 삽입 정렬을 쓴다던가, 특정 횟수 이상 재귀호출이 발생하면 O(nlgn)의 힙 정렬을 사용한다. 버블정렬(Bubble Sort) 방법 1번째와 2 번째..
[프로그래머스] 🔢 큰 수 만들기 / python
[프로그래머스] 🔢 큰 수 만들기 / python
2019.05.08🔢 큰 수 만들기 😃 나의 코드 def solution(number, k): length = len(number) if length > k: m = 0 for cnt in range(k): for idx in range(m, length-1): if number[idx] 0: m = idx-1 break else: number = number[:length-k+cnt] break return "".join([str(i) for i in number]) else: return "0" 탐욕법Greedy 알고리즘에 해당하는 문제입니다. 하지만, 탐욕법을 적용하고도, 특정 ..
[프로그래머스] 🖨 프린터 문제 / python
[프로그래머스] 🖨 프린터 문제 / python
2019.02.18🖨 프린터 문제 풀어보기 😃 나의 코드 def solution(priorities, location): pos = [] for i in range(len(priorities)): if i == location: pos.append(True) else: pos.append(False) answer = 0 count = 0 m = max(priorities) while True: if m > priorities[0]: priorities.append(priorities.pop(0)) pos.append(pos.pop(0)) else: count += 1 priorities.pop(0) if pos.pop(0): return count m = max(priorities) 스택(stack)/큐(queue) 자료..
[프로그래머스] 👨💻 기능 개발 / python
[프로그래머스] 👨💻 기능 개발 / python
2019.02.18👨💻 기능 개발 문제 풀어보기 😃 나의 코드 import math def solution(progresses, speeds): answer = [] progresses = [math.ceil((100-a)/b) for a, b in zip(progresses, speeds)] front = 0 for idx in range(len(progresses)): if progresses[front] < progresses[idx]: answer.append(idx-front) front = idx answer.append(len(progresses)-front) return answer 스택stack/큐queue 자료구조에 속한 문제입니다. 우선 progresses와 speeds로 나누어진 두 list를 하나..
[프로그래머스] 👷♀️ 타일 장식물 / python
[프로그래머스] 👷♀️ 타일 장식물 / python
2019.02.18👷♀️ 타일 장식물 문제 풀어보기 😃 나의 코드 def solution(N): rad_array = [1,1] for i in range(2,N): rad_array.append(rad_array[-1] + rad_array[-2]) answer = (rad_array[-2] + rad_array[-1]*2)*2 return answer DP(Dynamic Programming, 동적계획법)을 이용해 해결한 문제입니다. DP의 계획에 따라 전체 문제를 작은 부분으로 나누겠습니다. 최종적으로 구할 직사각형의 둘레는 마지막으로 구한 정사각형과 그 전 정사각형의 변의 길이를 통해 구할 수 있기 때문에 변을 구하는 문제로 치환해서 풀겠습니다.가장 작은 정사각형부터 구하면 마지막으로 구한 정사각형의 한 변과 그..
[알고리즘] 🤷♂️ 동적 계획법 / dynamic programming
[알고리즘] 🤷♂️ 동적 계획법 / dynamic programming
2019.02.18👉 동적계획법 DP(동적 계획법)이 뭔가요? DP는 알고리즘 문제로 자주 나오는 디자인 패러다임 중 하나입니다. Dynamic Programming이라는 말은 고안자인 벨만이 dynamic이라는 단어가 멋있어서(…) 선택한 단어라고 합니다. 따라서 이 방법은 전산학 전반에서의 동적(dynamic) 혹은 프로그래밍(programming)이라는 단어와는 관련이 없습니다. DP의 한글 번역도 동적 프로그래밍보다는 동적 계획법으로 번역됩니다. 👉 특징 부분 문제(overlapping subproblems) 동적 계획법의 접근 방식은 분할 정복과 같습니다. 주어진 문제를 더 작은 문제로 나눈 뒤 이 문제의 답을 계산하고, 이 답을 토대로 원래 문제의 답을 도출해가기 때문입니다. 하지만 분할 정복과 문제를 나누는 ..
[프로그래머스] 👨🏫 정수 삼각형 / python
[프로그래머스] 👨🏫 정수 삼각형 / python
2019.02.18👨🏫 정수 삼각형 문제 풀어보기 😃 나의 코드 def solution(tri): m_lst = [] for row in tri: lst = [] if len(m_lst) == 0: lst.append(row[0]); else: for idx, num in enumerate(row): if idx == 0: lst.append(m_lst[-1][idx] + num) elif idx == len(row)-1: lst.append(m_lst[-1][-1] + num) else: lst.append(max(m_lst[-1][idx-1],m_lst[-1][idx]) + num) m_lst.append(lst) return max(m_lst[-1]) DP(Dynamic Programming, 동적계획법)을 이용해..
[프로그래머스] ⚾ 숫자 야구 / python
[프로그래머스] ⚾ 숫자 야구 / python
2019.02.15⚾ 숫자 야구 문제 풀어보기 😃 나의 코드 from itertools import permutations def check_score(question, candidate, s, b): strike = 0 for i in range(len(question)): if question[i] == candidate[i]: strike += 1 if s != strike: return False ball = len(set(question) & set(candidate))-strike if b != ball: return False return True def solution(baseball): lst = list(permutations([1,2,3,4,5,6,7,8,9], 3)) for i in baseball:..
[프로그래머스] 🕵️♀️ 소수 찾기 / python
[프로그래머스] 🕵️♀️ 소수 찾기 / python
2019.02.15🕵️♀️ 소수 찾기 문제 풀어보기 😃 나의 코드 from itertools import permutations def solution(numbers): answer = set() maximum = 10000000 prime_lst = [False, False] + [True] * maximum for idx, num in enumerate(prime_lst): if num: k = idx*2 while k
[프로그래머스] 🎨 카펫 문제 / python
[프로그래머스] 🎨 카펫 문제 / python
2019.02.15--- --- 🎨 카펫 문제 풀어보기 😃 나의 코드 def solution(brown, red): for a in range(1, int(red**0.5)+1): if not red % a: b = red // a if 2*a + 2*b + 4 == brown: return [b+2, a+2] 완전 탐색(exhaustive search)를 이용하여 푸는 문제입니다. 빨간색의 가로를 A, 세로를 B라고 했을 때, 주어진 값 red는 A*B가 되고 brown은 2(A+B)+4가 됩니다. 이제 A와 B에 찾는 과정입니다. red를 두 자연수 곱의 쌍으로 봤을 때, 중복된 곱의 쌍을 없엔다면 A의 범위는 red의 제곱근의 내림값보다 작거나 같을 것입니다. 이를 통해 얻은 자연수 A와 B의 쌍이 brown에 값에..
[프로그래머스] 👩🏫 모의고사 / python
[프로그래머스] 👩🏫 모의고사 / python
2019.02.15👩🏫 모의고사 문제 풀어보기 😃 나의 코드 def solution(answers): peoplePatternArray = [[1,2,3,4,5], [2,1,2,3,2,4,2,5], [3,3,1,1,2,2,4,4,5,5]] scoreArray = [0,0,0] result = [] for idx, answer in enumerate(answers): for i in range(0,len(peoplePatternArray)): if answer == peoplePatternArray[i][idx%len(peoplePatternArray[i])]: scoreArray[i] += 1 for idx, s in enumerate(scoreArray): if s == max(scoreArray): result.ap..
[알고리즘] 🤷♂️ 완전 탐색 알고리즘 / exhaustive search algorithm
[알고리즘] 🤷♂️ 완전 탐색 알고리즘 / exhaustive search algorithm
2019.02.15출제 빈도 높음 평균 점수 낮음 🤷♂️ 완전 탐색 알고리즘(exhaustive search algorithm)?PS(Problem Solving)을 하는 데 가장 간단하고 쉬운 방법이 무엇일까요? 답은 가능한 경우를 다 해보는 것입니다. 이게 무슨 알고리즘이야? 할 수 있겠지만, 이것도 알고리즘에 일종입니다. 전산학에서는 이를 무식하게 푼다라는 뜻의 Brute-force라 하고, 전체를 확인한다고 해서 완전 탐색 알고리즘(exhaustive search algorithm)이라고 합니다. 👉 어디에 쓰이는가?하지만 대부분의 문제들은 시간 초과등의 이유로 완전 탐색으로 풀리지 않습니다. 하지만 어려운 알고리즘을 생각할 필요 없이 완전 탐색으로 풀리는 문제도 있으며, 가끔 어려운 완전 탐색 문제도 존재합니다..