[level 4] 매출 하락 최소화 - 72416 문제 링크 성능 요약 메모리: 10.2 MB, 시간: 0.02 ms 구분 코딩테스트 연습 > 2021 KAKAO BLIND RECRUITMENT 채점결과 Empty 문제 설명 유통전문회사 카카오상사의 오너인 제이지는 새로운 사업 아이템을 구상하기 위해 전문경영인(CEO)인 프로도에게 회사의 경영을 부탁하였습니다. "카카오상사"는 직원들을 여러 개의 팀 단위로 조직을 구성하고 있으며 아래 그림은 CEO를 포함하여 10명의 직원과 4개의 팀으로 구성되어 있는 회사 조직도를 보여주고 있습니다. 그림의 조직도는 다음과 같이 설명할 수 있습니다. 그림의 각 원들은 각각의 직원 1명을 표시하고 있으며, CEO를 포함하여 총 10명의 직원을 표시하고 있습니다. 원 안..
[level 3] 단속카메라 - 42884 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 성능 요약 메모리: 10.9 MB, 시간: 2.55 ms 구분 코딩테스트 연습 > 탐욕법（Greedy） 채점결과 Empty 문제 설명 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완..
공부할 때 참고한 블로그 : https://sepang2.tistory.com/ 학습기록 sepang2.tistory.com Ch:9: Theory of NP 다항시간 알고리즘이란 worst case 시간복잡도가 n에 대한 다항 함수로 구성되는 알고리즘이다. o(n^k) (K≥0) 다만 n^3을 넘어가는 다항시간 알고리즘 또한 실제 사용하기에는 복잡도가 커다는 평가가 있다. solvable problem 컴퓨터가 해결할 수 있는 해결할 수 있는 알고리즘이 입증되어 있는 경우를 말한다. polynomial of expoenential시간 복잡도를 가진다. unsolvable problem 미래에도 해당 문제에 대한 해결 알고리즘을 개발하는게 불가능하다는 것이 증명된 문제들을 말한다. intractable ..
Ch:8: Theory of computational complexity: Searching problem and selection problem as a case study 탐색문제의 lower bound도 확인해보자 binary search 알고리즘 사용 = worst case = logn인 효율적인 알고리즘 searching 문제는 여러개의 key field에서 원하는 key를 검색하는 과정이다. 즉, sorting 알고리즘과 유사하게 comparison이 base가 되는 알고리즘이다. = tree구조로 모델링이 가능하다. d = depth = comparison 횟수 search problem의 lower bound 도 logn이므로 binary search보다 더 빠른 알고리즘은 존재하지 않는다..
Ch:7: Theory of computational complexity: Sorting problem as a case study computational complexity theory = 계산 복잡도 이론 특정 문제를 해결하기 위해 필요한 시간복잡도를 계산하는 것이 아니라 동일한 문제를 해결하는데 사용될 수 있는 모든 알고리즘에 대해 시간 효율성에 대한 하한을 결정하는 이론 그렇기 위해서 주어진 제한된 자원으로 해결할 수 있거나 해결할 수 없는 문제를 분류함. 최대 T(n)으로 문제의 시간복잡도를 보이는 상한(upper bound)의 증명은 쉽지만(T(n)인 특정 알고리즘이 있다는 것만 보여주면 되기 때문) 하한을 증명하는 것은 어렵다(lower bound) 왜냐하면 lower bound는 주어진 ..
chap6 Branch and bound algorithm design approach 0-1 knapsack 문제에 대해서 항상 앞서있지는 않지만 많은 경우의 input 에 대해 유리한 결과를 보여준다. tree를 탐색하는 순서를 정해두고 하지않는다. 오직 optimization 문제를 위해 설계된 알고리즘이다. breadth first search = queue data structure로 구성된 level order traversal로 kanpsack 문제 해결하기. BFS = 너비 우선 탐색 시작노드에서 시작하여 가까운 노드부터 우선적으로 탐색하는 알고리즘 recursive function을 사용x BFS 동작 과정 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼낸 뒤에 해당..
chap5 Backtracking Algorithm design approach 해가 될 가능성이 있는지 promising을 확인한 수 필요없으면 가지치기 prune을 한다. DFS = 깊이 우선 탐색 DFS는 스택 자료구조 또는 재귀 함수를 이용한다. DFS backtracking 푸는법 Tree 형태로 visualize한다 branch를 제거하는 메커니즘을 설계한다. 조건에 따라 단일 leaf node에 도달하거나 여러개의 leaf node에 도달할 것이다. 이후 조건에 따라 이중에서 하나를 선택한다. DFS 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 ..
[level 2] 타겟 넘버 - 43165 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 성능 요약 메모리: 10.3 MB, 시간: 1.50 ms 구분 코딩테스트 연습 > 깊이／너비 우선 탐색（DFS／BFS） 채점결과 Empty 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1..
chap4 Greedy algorithm design pattern =과거 미래에 상관없이 현재 순간에 최선을 고르는 방식. = local optimal 해결책임 , global optimal solution이 아닐 수 있음. greedy 알고리즘의 반복순서 selection step = solution set에 들어갈 현재의 최선을 선택함 feasibility check = 타당한지 확인함(가능한지) solution checking step = 새로운 solution set이 문제를 만족하는 해답인지 확인. global optimal solution을 얻기 위해 local optimal을 선택하는 과정 Minimum spanning Tree 문제 = 최소 비용 신장트리 Select an edge Cyc..
chap3. Dynamic programming(planning) 작은 문제가 반복되는 경우에 작은 문제를 계산하여 한번 계산한 값을 저장하고 검색 후 재사용하는 방식. = recomputing 대신 look up table 만들기. fibonacci number DP의 핵심 스텝 DP는 schedule을 사용하여 문제를 효율적으로 풀지만 메모리를 추가로 사용하고 divide and conquer는 문제를 blindly(무턱대고) 풀며, 스케줄링과 planning이 없다. - 겹치는 계산이 없을 때 쓰면 좋음. Compute binomial coefficient=이항계수 문제 계속 이전 항끼리의 합을 구하는 방식이라 겹치는(over lapping)부분과 반복되는 계산이 많다. basic operation..
