배경 회사에서 COS Pro 시험 응시를 장려하는 분위기여서, 솔선수범 하자는 마음으로 시험을 응시하였다. 운이 좋았는지 1,000점 만점을 받았다. 시간이 지나면 기억에서 지워질 것 같아서 글로 남기고자 한다. (사실 조회수도 좀 나올것같아서....) 시험 설명 프로그래머스 스타일로 10문제가 제출 된다. 기출 문제가 6회 공개 되어있어서 나는 구름을 이용해서 준비했다. 1시간 30분씩 타이머를 켜놓고 5개의 기출문제를 풀었다. 본 시험을 위해 약 7시간 30분 투자한것 같다. 컴퓨터 공학과를 졸업했다면 조금만 준비해도 합격하는 것은 크게 어렵지 않을 것 같다. 600점 이상 획득하면 합격이다. https://edu.goorm.io/lecture/17301/cos-pro-1%EA%B8%89-%EA%B8..

Count Array Pairs Divisible by K 목적 integer의 배열이 nums가 주어진다. 주어진 nums에서 2개의 pair를 선택해서 곱한 결과가 k로 나뉘어지는 경우가 몇 번인가? 단, pair가 (1,2)이면 (2,1)과 동일하다. 접근 방법 Brute force 접근 가장 쉬운 접근은 모든 경우의 수를 곱샘 하는 것이다. 만약 nums = [1,2,3,4,5], k = 2 가 주어지면, [1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5] 를 만들 수 있고 이중에서 2로 나뉘어 지는 것은 2,3,4,5,6,8,10,12,15,20 중에서 2,4,6,8,10,12,20이 된다. 모든 경우의 수를 따지고 k로 % 연산을 진행할 ..

Longest Increasing Subsequence 문제 내용 주어진 Array에서 가장 긴 연속된 순서의 길이를 찾아라. Array내의 Position을 수정할 순 없지만, 중간에 있는 값을 삭제 할 수는 있다. 접근 방법 Brute Force 상위와 같은 배열이 주어졌을 경우 다음과 같이 Array를 찾을 수 있다. 9보다 작은 값이 이전에 있었는가? 없었다면 dp 1을 유지한다. 2보다 더 작은 값이 있는가? 없음으로 유지한다. 5보다 작은 값이 있는가? 2가 더 작았다. 그럼 2의 dp + 1을 해준다. 3도 같은 방법으로 dp의 값을 올려준다. 7의 경우 2,5,3 중 가장 높은 dp의 값에 + 1을 해준다. 101은 4가 된다. 18도 4가 된다. 위의 방식은 Time Complexity가..

Decode Ways 문제 내용 대문자 A부터 Z까지를 1부터 26까지의 숫자와 대응시켰을 때 주어진 숫자로 만들어 낼 수 있는 문자의 갯수는 몇개인가? 접근 방법 우선 Brute force 접근의 경우는 모든 경우를 분기 시키는 것이 가능하다. 만약에 '112'가 주어졌다고 하면 'aab','ai','kb' 이렇게 3개의 선택을 할 수 있다. 이 선택의 순서를 dfs방식으로 하게 되면, 최악의 경우 '11111111'

Arithmetic Slices 문제 내용 number array가 주어진다. 각 number의 연속적인 차가 동일할 경우 부분 집합의 갯수를 return해라 접근 방법 문제 내용을 보면 [1,3,5,7,9] [7,7,7,7] [3,-1,-5,-9] 가 동일한 차를 갖고 있다고 한다. 예를 들어서 [7,7,7,7]은 [0,0,0]의 차를 동일하게 갖고 있다. 이 array는 left : [7,7,7] right : [7,7,7] 전체 [7,7,7,7] 이렇게 3개의 부분 집합을 만들 수 있다. 이 부분 집합의 갯수를 다음과 같이 추상화 해보자. 부분 집합 갯수 구하기 차의 집합을 [a,a] 라고 생각해 보자. 위에서 [7,7,7,7]은 [0,0,0]으로 구성되어 있음으로 이 동일 갑을 'a'라고 치환한 ..

Shortest Path Visiting All Nodes 문제 내용 주어진 Node를 모두 Visite하는데 얼마의 step이 필요한가? 각 Node는 중복으로 방문이 가능하다. 접근 방법 개인적으로 이해하는데 시간을 오래 끌었다. Youtube나 google을 조회해 봐도 Floyd-Warshall 알고리즘이나 Dijkstra 를 이용한 방법이 검색되었다. 한마디로 이해하기 어렵고 주어진 시간내에 개발하기도 어려웠다. 그래서 Discussion을 찾아보는데 Smart BFS를 사용한 방법으로 본 문제를 풀었다는 이야기를 많이 보았다. 그래서 여기서 말하는 Smart BFS가 무었인지 알아보고 이를 통해서 문제를 풀어보고자 한다. BFS 접근 방법 BFS는 queue를 이용해서 접근 범위를 넓혀가는 방..

DFS 또는 Backtracking을 하거나 하는 방식으로 문제를 풀게 되면, 완전검색(Exhaustive Search)을 고려하게 된다. 처음 문제를 보았을때 이것이 완전검색을 원하는 것인지 아니면 최적의 P를 찾아낼 수 있는지를 판단하는 것이 중요하다. 가장 쉬운 판단법은 전제사항을 유심히 보는 것이다. 대부분 문제를 보면 숫자의 범위가 0에서 100,000이상의 범위를 갖게 된다. 그런데 이 문제만 이상하게 24, 32이런식으로 매우 작은 수로 범위를 갖는 경우가 나타난다. 이럴때는 완전검색을 고려해볼 필요가있다. 문제를 하나 풀어보면서 Masking과 DP를 어떻게 활용하는지 같이 알아보자. https://leetcode.com/problems/partition-to-k-equal-sum-subs..

Jump Game II 문제 내용 주어진 숫자 Array가 있다. 해당 Array index 0에서 출발한다고 할때, Jump가 가능한 범위는 arr[i]라고 할 수 있다. 예를 들어 arr[0]이 3이면 arr[1], arr[2], arr[3]으로 자리를 옮길 수 있게 된다. Array의 마지막 Index까지 갈수 있는 최소의 Jump 횟수를 구하시오. 접근 방법 DP를 이용해서 문제를 풀면 된다. 그런데 이렇게 간단히 최적화 되는 문제가 아니다 보니 글을 남기게 되었다. DP로 접근하고 이후 Greedy로 접근해 보겠다. DP 접근 다음과 같은 문제가 주어졌다고 생각해 보겠다. dp는 현재 index에서 마지막 index 7인 '2'까지 최소한의 jump를 기록 한다고 정의하자. 뒤에서 부터 접근해 ..

Sparse Matrix Multiplication 문제 내용 Matrix Dot(곱)을 연산 하시오 접근 방법 기본적인 수학 문제이다. 그런데 의외로 이런 문제를 코드로 변환 시키려고 보면 머리가 멈춘다. 아... 진짜 그냥 바보같다. 아무튼 다음과 같은 접근 방식으로 풀었다. A 배열을 arows * acols, B배열을 brows * bcols 라고 명명할 수 있다. acols와 brows의 크기가 같아야 곱셈이 가능하다 결과 배열은 arows * bcols가 된다. 위의 3가지를 이용해서 문제를 접근했는데, 기본적인 loop를 어떻게 돌것이냐? 가 가장 중요한 첫번째 step이다. A배열을 loop 시킬까? 아니면 B배열을 loop 시킬까? 결론은 Result 배열인 arow * bcols를 lo..