알고리즘
Q. 정렬 알고리즘에 대해 설명해주세요.
Q. 정렬 알고리즘에 대해 설명해주세요.
2019.06.03Q. 정렬 알고리즘에 대해 설명해주세요. Goal 정렬 알고리즘의 개념을 설명할 수 있다. 정렬 알고리즘의 종류에 대해 설명할 수 있다. 정렬 알고리즘의 개념 정렬 알고리즘이란 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 얼마나 효과적으로 해결하는 지가 정렬 알고리즘의 핵심 정렬 알고리즘이 중요한 이유 데이터가 정렬되어 있으면 이진탐색이라는 강력한 알고리즘을 사용할 수 있다. 대표적인 정렬의 종류 실제 응용에서는 상황에 따라 두 가지 이상의 정렬 방법을 사용하는 경우가 많다. 정렬 대상이 특정 크기 이하로 단편화될 때까지는 퀵 정렬을 쓰다가, 삽입 정렬을 쓴다던가, 특정 횟수 이상 재귀호출이 발생하면 O(nlgn)의 힙 정렬을 사용한다. 버블정렬(Bubble Sort) 방법 1번째와 2 번째..
[알고리즘] 🤷♂️ 동적 계획법 / dynamic programming
[알고리즘] 🤷♂️ 동적 계획법 / dynamic programming
2019.02.18👉 동적계획법 DP(동적 계획법)이 뭔가요? DP는 알고리즘 문제로 자주 나오는 디자인 패러다임 중 하나입니다. Dynamic Programming이라는 말은 고안자인 벨만이 dynamic이라는 단어가 멋있어서(…) 선택한 단어라고 합니다. 따라서 이 방법은 전산학 전반에서의 동적(dynamic) 혹은 프로그래밍(programming)이라는 단어와는 관련이 없습니다. DP의 한글 번역도 동적 프로그래밍보다는 동적 계획법으로 번역됩니다. 👉 특징 부분 문제(overlapping subproblems) 동적 계획법의 접근 방식은 분할 정복과 같습니다. 주어진 문제를 더 작은 문제로 나눈 뒤 이 문제의 답을 계산하고, 이 답을 토대로 원래 문제의 답을 도출해가기 때문입니다. 하지만 분할 정복과 문제를 나누는 ..
[알고리즘] 🤷♂️ 완전 탐색 알고리즘 / exhaustive search algorithm
[알고리즘] 🤷♂️ 완전 탐색 알고리즘 / exhaustive search algorithm
2019.02.15출제 빈도 높음 평균 점수 낮음 🤷♂️ 완전 탐색 알고리즘(exhaustive search algorithm)?PS(Problem Solving)을 하는 데 가장 간단하고 쉬운 방법이 무엇일까요? 답은 가능한 경우를 다 해보는 것입니다. 이게 무슨 알고리즘이야? 할 수 있겠지만, 이것도 알고리즘에 일종입니다. 전산학에서는 이를 무식하게 푼다라는 뜻의 Brute-force라 하고, 전체를 확인한다고 해서 완전 탐색 알고리즘(exhaustive search algorithm)이라고 합니다. 👉 어디에 쓰이는가?하지만 대부분의 문제들은 시간 초과등의 이유로 완전 탐색으로 풀리지 않습니다. 하지만 어려운 알고리즘을 생각할 필요 없이 완전 탐색으로 풀리는 문제도 있으며, 가끔 어려운 완전 탐색 문제도 존재합니다..
[알고리즘] 🤷♂️ 백트래킹 알고리즘 / Backtracking Algorithm
[알고리즘] 🤷♂️ 백트래킹 알고리즘 / Backtracking Algorithm
2019.02.01🤷♂️ 백트래킹(Backtracking) 알고리즘모든 경우의 수를 전부 고려하는 알고리즘으로 트리형 자료구조에 적합하며 계속해서 답이 될 수 있는 후보 노드들을 만들어내고, 해당 후보로는 적절한 답을 얻을 수 없는 후보를 철회("Backtracks")하면서 문제를 해결하는 알고리즘이다. 가장 유명한 예제로는 서로를 공격할 수 없는 8개의 퀸의 위치 배열을 찾는 N-queens 문제가 있다. N-queens 문제를 백트래킹 알고리즘으로 접근하면, 첫 행부터 아래로 내려가면서, 이미 존재하는 퀸에 가로 세로 대각선에 존재하는 후보는 철회하는 방식으로 풀 수 있다. 백트래킹 알고리즘은 '부분적 후보 해결책'의 개념을 확인하는 문제와 그것이 유효한 해결책으로 완성될 수 있는 지의 여부를 상대적으로 빠르게 시험..
[BOJ] 👸 N-Queens / 파이썬
[BOJ] 👸 N-Queens / 파이썬
2019.02.01👸 N-Queens 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 😃 나의 풀이 def nqueen(sol, n): global count if len(sol) == n: # 정답 배열(sol)의 길이가 n과 같아지면, count 증가 count += 1 return 0 candidate = list(range(n)) # 0부터 n-1까지를 후보 배열로 만든다. for i in range(len(sol)): if sol[i] in candid..
Q. 정렬 알고리즘에 대해 설명해주세요.
Q. 정렬 알고리즘에 대해 설명해주세요.
2018.12.22Q. 정렬 알고리즘에 대해 설명해주세요. Goal 정렬 알고리즘의 개념을 설명할 수 있다. 정렬 알고리즘의 종류에 대해 설명할 수 있다. 정렬 알고리즘의 개념 정렬 알고리즘이란 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 얼마나 효과적으로 해결하는 지가 정렬 알고리즘의 핵심 정렬 알고리즘이 중요한 이유 데이터가 정렬되어 있으면 이진탐색이라는 강력한 알고리즘을 사용할 수 있다. 대표적인 정렬의 종류 실제 응용에서는 상황에 따라 두 가지 이상의 정렬 방법을 사용하는 경우가 많다. 정렬 대상이 특정 크기 이하로 단편화될 때까지는 퀵 정렬을 쓰다가, 삽입정렬을 쓴다던가, 특정 횟수 이상 재귀호출이 발생하면 O(nlgn)의 힙 정렬을 사용한다. 버블정렬(Bubble Sort) 방법 1번째와 2 번째 ..