문제 A,B,C 로 구성할 수 있는 부분집합을 모두 구하시오. 해결 방법 부분집합의 모든 경우의 수가 2^(원소의 개수) 인 것은 학교에서 배우는 내용이다. 코딩 문제에서도 부분집합과 순열, 조합의 경우 해당 개념을 사용하는데, 그 이유는 다음 사진과 같다. A,B,C를 각각 on off 개념으로 1,0 으로 나타낼 수 있다. 즉, 파이썬에서는 for i in range(2**3) 으로 모든 부분집합을 구할 수 있는 것이다. 예시 코드 비트를 사용하여 부분집합을 구하는 예시입니다. # 비트를 활용한 부분집합 구하기 letters = ['a', 'b', 'c'] for i in range(1 0 0 0 => 공집합 # ['a'] | => (i = 1) => 0 0 1 => (j = 0)에서 걸려 'a'가 ..
[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 함수를 완..
함께 자라기 애자일로 가는 길 2023-08-09 함께 자라기 나머지 전부를 읽고 쓴 글입니다. 함께 추상화의 중요성 서로 시각이 다른 두 사람의 생각을 연결해 줄 다리가 추상화이고, 이 추상화를 통해 더 나은 해결방법을 도출해 낼 수 있다. 혼자 작업할 때 보다 여러 사람과 함께 대화하고, 공유 ppt나 화이트보드에 그림을 그려가며 이야기하는 경우가 더 좋았던 경험이 있다. 이야기를 통해 새로운 아이디어가 잘 떠오르거나 문제에 대해 상담하다 보면 생각보다 간단한 해결방법이 존재하는 등의 예시이다. 일의 효율성을 위해서라도 커뮤니케이션 능력은 확실히 중요하다 생각한다. 신뢰를 깍는 공유인가 신뢰를 쌓는 공유인가 만약 속해있는 집단이 자신이 알거나 배운 것에 대해 공유하기를 주저하는 집단이라면 나 또한 그..
함께 자라기 애자일로 가는 길 2023-08-02 함께 자라기 반을 읽고 쓴 글입니다. 자라기 파트는 전체적으로 학습하는 방법에 대해 이야기하는 부분이었다. 1만 시간의 법칙이란 한 분야에 대해 1만 시간의 시간을 들인다면 전문가가 된다는 법칙이다. 다만 저자는 그저 1만 시간을 보내는 것이 아니라 1만 시간의 의도적 수련을 보내야 한다고 이야기한다. 자라기 파트에서는 의도적 수련을 위한 여러 방법을 설명해 준다. 신입 개발자보단 2년 차 개발자가 확실히 일을 잘하지만 2년차 개발자보다 5년 차 개발자가 일을 더 잘할 것이라는 보장은 불가능하다는 말에 고개를 끄덕이며 봤던 것 같다. 오랜 시간을 투자하면 더 잘할 가능성이 당연히 높긴 하겠지만 시간을 어떻게 효율적으로 사용하냐에 따라 큰 차이가 있음을 알..
공부할 때 참고한 블로그 : 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 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 ..
