전체 글 (30) 썸네일형 리스트형 [COSE214] Dynamic Programming, Greedy Algorithm Dynamic Programming으로 문제를 해결하기 위해 문제가 갖춰야 할 structural properties에 대해서 서술하고, DP로 해결할 수 있는 문제의 예시에 대해 서술하시오. Dynamic Programming으로 해결할 수 있는 문제의 예시에는 두 개 이상의 assembly line에서 여러 작업들을 수행하여 최소 시간 또는 비용으로 제품을 완성하는 문제인 Assembly line scheduling problem, 여러 개의 행렬을 곱하는 과정에서 최소한의 곱셈 연산을 수행하는 최적의 순서를 찾는 문제인 Matrix chain multiplication problem , 한정된 용량을 가진 배낭에 최대한 가치 있는 물건을 넣는 문제인 knapsack problem 등이 있다. DP.. [COSE214[] Heap Sort Max Heap의 조건과 구조에 대해 서술하시오. Max heap이 되기 위해서는 먼저 1) heap의 shape이 binary tree의 무조건 앞쪽에서부터 순서대로 노드를 채우는 almost complete binary tree 형태여야 한다. 2) 그리고 항상 위쪽 node가 아래쪽 node보다 큰 max heap property를 갖추어야 한다. 이렇게 형성된 almost CBT의 index로는 특정 node의 번호가 i라고 할 때 parent node는 i/2, left node는 2i, right node는 2i+1이라는 index를 가진다. 또한 height of a node는 leaf에서 0이고, upwards로 가며 숫자가 커진다. depth of a node의 경우 root에서 0이고.. [COSE214] Tree, Graph 정의 [COSE214] Hiring problem hiring problem은 computational problem은 아니지만 randomized algorithms의 아이디어를 이용하는 문제이다. 회사에서 n명의 candidate를 인터뷰하여 hire할지, fire할지를 정한다고 하자. 이 때 모든 candidate는 모두 distinct competitiveness를 가지고 있고, 우리는 회사가 hire 시 지불해야하는 총 비용을 계산하고자 한다. 인터뷰 비용: Ci / hire 비용: Ch / fire 비용: 0best case: nCi + 1 Ch : 첫번째 면접자가 가장 competitive 한 경우worst case: nCi + n Ch : 마지막 면접자가 가장 competitive 한 경우 이 때 평균적으로 얼마나 많은 candidat.. [COSE214] Sort: Merge Sort, Quick Sort Divide&Conquer approach로 알고리즘을 디자인 하는 방법에 대해서 서술하시오. Divide&Conquer 접근은 문제를 나눌 수 없을 때까지 나누어서 각각을 푼 후 다시 합병하여 문제의 답을 얻는 알고리즘이다. 이는 1) Divide 단계에서 문제를 더 이상 나눌 수 없을 때까지 분할하여 작은 부분문제들을 만든다. 2) Conquer 단계에서 분할된 부분 문제를 재귀적으로 해결하며, 3) Combine 단계에서 분할된 부분 문제를 결합하여 최종 해결책을 도출한다. Divide&Conquer 원리를 이용한 알고리즘에는 대표적으로 merge sort, quick sort가 있다. Merge Sort란 하나의 배열을 두 개의 균등한 크기로 분할하고, 두 부분을 합치면서 배열을 정렬하여 전체.. [COSE214] 알고리즘 기초 개념 알고리즘이란 무엇이며, 이가 가지는 특성과 구성요소에 대해 서술하시오. 알고리즘을 통해 모든 computational problem을 solve 할 수 있는가?Computational problem은 어떠한 input이 주어졌을 때 어떠한 output이 기대되는지를 명확하게 specification 한다. 이 때 computational problem은 여러 가지 형태의 입력 데이터인 instance를 가질 수 있다. 알고리즘이란 computational problem에서 정확한 output을 계산하기 위해 수행해야 할 작업에 대한 명확한 설명으로, 1) finiteness를 가져 유한한 단계의 수를 가져야 하며, 2) 주어진 문제의 모든 instance에 대해 올바른 output을 계산하기 위한 cor.. 삼성 sw 역량테스트 후기 다음에 시험볼 때 도움이 될까 해서 자기전에 간단하게 쓴다 8시반까지 입실이라 6시에 일어나서 7시 좀 넘어서 출발 7시 50분쯤 도착개 졸렸음 버스에서 자고 내리자마자 데자와 원샷 그제서야 잠이 좀 깼다도착해서 쾌변하고 양치함. 칸마다 비데 있더라 역시 이게 대한민국 최고의 기업? 옷을 뭐 입고 가야될지 고민하다가 그냥 셔츠에 자켓 입고 나름 단정하게 갔는데그럴 필요 없고 후드티 입고 온 사람 츄리닝 입고 온 사람 다들 제각각이니 마음대로 입고가면 될 것 같다사람들 옷차림이 하스나 진배없다대신 고사실 안에 에어컨 틀어줘서 약간 추울 수 있으니 겉옷 들고가야함 한 고사실에 30명 내외인 것 같았고 내가 본걸로는 11고사실까지 있었다오전 오후 합하면 대략 600명.. 순간 쫄았는데 인턴만 본게 아니라 공채.. [자료구조] Ⅰ-5,6,7. 알고리즘 성능 분석, 복잡도 5. 알고리즘 ● 알고리즘이란 문제를 풀기 위한 방식으로, 예시로는 10장의 카드가 무작위로 펼쳐져 있고 그 중 85를 찾기 위해 순서대로 찾기(Sequential Search - 순차탐색) , 반으로 나누어 중간과 먼저 비교하여 큰지 작은지를 통해 절반씩 탐색 범위를 줄여가며 찾기(Binary Search - 이진탐색), 가장 적은 수의 동전으로 거스름돈을 받기 위한 방법(그리디 알고리즘), 한붓 그리기 등이 있다. ● 알고리즘은 자료구조의 기본적 연산을 구현하기 위한 것으로, 같은 자료라고 해도 어떻게 저장, 표현되느냐에 따라 사용 가능한 알고리즘이 달라지며 알고리즘의 성능은 자료구조에 종속된다. ● 알고리즘의 표현 방식 ● 알고리즘의 조건 1) input: 외부에서 제공되는 자료 0개 이상 2) o.. 이전 1 2 3 4 다음
