Dot Dot Line Dot

title: Programmers - 배달 date: 2022-06-21 tags: Algorithm Graph Dijkstra https://programmers.co.kr/learn/courses/30/lessons/12978 문제 요약 주어진 그래프에서 root 노드로부터 K 가중치 내로 이동 가능한 노드의 수를 구하여 return한다. 문제 풀이 전형적인 Dijkstra Graph 문제이다. 주어진 그래프를 인접행렬로 변환한 후, N-1번 거리를 갱신하여 root로부터 모든 노드로 가는 거리가 K 이하인 노드의 개수를 구한다. 갱신이 이루어지지 않을 때 갱신을 중단하여도 되지만, 최대 갱신 횟수는 N-1번이다. 중단 조건 구현이 귀찮아서 N-1번 갱신하였다. 가중치에 -가 존재한다면 Floyd-W..

title: Programmers - 2 x n 타일링 date: 2022-06-21 tags: Algorithm DP https://programmers.co.kr/learn/courses/30/lessons/12900 문제 요약 1x2 타일을 2xn 공간에 배치하는 모든 경우의 수를 구한다. 문제 풀이 전형적인 DP 입문 문제이다. n >= 3 일때, n번째 경우의 수는 n-2번째의 배치에서 가로로 배치하는 경우의 수와 n-1번째의 배치에서 세로로 배치하는 경우의 수의 합이다. 이전 두 단계의 값만 참조하기 때문에 과한 메모리를 할당할 필요 없이 길이 3의 배열만 있으면 된다. n 3 일 때 (n-3)번 DP 계산을 해준다. 계산 이후 배열의 마지막 element의 값이 정답이다. 프로그램 #incl..

title: Programmers - 짝지어 제거하기 date: 2022-06-20 tags: Algorithm https://programmers.co.kr/learn/courses/30/lessons/12973 문제 요약 데이터로 들어온 문자열에서 같은 문자가 서로 붙어있다면 붙어있는 2개의 문자를 제거한다. 모든 문자가 제거가 되면 1을, 안 되면 0을 return한다. 문제 풀이 문자열의 길이는 최대 1M이므로 1s라 가정하면 O(nlogn)이 한계이다. 앞에서부터 탐색하며 제거가 되면 바로 앞의 문자부터 체크를 시작하여야 불필요한 탐색을 하지 않는다. 처음에는 string.erase 함수를 이용하였으나, 시간이 너무 오래 걸려 효율성 테스트를 하나도 통과하지 못하였다. 스택 방식으로 수정하였다...

title: Programmers - 가장 큰 수 date: 2022-06-20 tags: Algorithm https://programmers.co.kr/learn/courses/30/lessons/42746 문제 요약 데이터로 들어온 숫자들을 이어 붙여 가장 큰 수를 만들어야 한다. 매우 큰 수가 될 수 있으므로 문자열로 바꾸어 return한다. 문제 풀이 문자열로 return하라는 의미는 모든 수를 비교하는 것이 아닌, 올바른 방식으로 수를 정렬한 후 그대로 이어 붙이라는 뜻이다. algorithm의 sort 함수를 사용, 비교 함수인 bCompare 함수를 만들어 정렬한다. 정렬시 두 숫자를 붙인 문자열로 바꾸어 비교하여 더 큰 수가 만들어지는 순서대로 정렬한다. 추가적으로 프로그래머스는 itoa..

title: Programmers - 단체사진 찍기 date: 2022-06-20 tags: Algorithm DFS https://programmers.co.kr/learn/courses/30/lessons/1835 문제 요약 카카오 프렌즈를 조건에 맞게 배치하여야 한다. 가능한 경우의 수를 return한다. 문제 풀이 8마리가 확정이므로 약 40k를 검사하여야 한다. 조건은 최대 100개이므로 최대 4M의 순열 조합 생성과 조건 확인이 이루어진다. 조건 확인시 주어진 vector를 계속 확인해야 하므로 .data () 함수를 이용하여 시간을 줄일 수 있을 것으로 보인다. 이전에는 이러한 문제를 DFS로 풀었으나, next_permutation이라는 좋은 함수를 알게 되어 이를 활용하면 프로그램의 길이..

title: Programmers - 더 맵게 date: 2022-06-20 tags: Algorithm https://programmers.co.kr/learn/courses/30/lessons/42626 문제 요약 데이터로 들어온 값을 전부 K 이상으로 만들어야 한다. 가장 작은 두 데이터간의 연산을 통해 하나의 큰 데이터로 바꿀 수 있다. 변환 횟수를 count하며, 만들 수 없다면 -1을 return한다. 문제 풀이 데이터의 개수는 최대 1M, minimum indicator인 K는 0~1B 사이이다. int 타입으로 충분하나, signed의 경우 overflow가 발생할 수 있다. 테스트 케이스가 부족하여 overflow는 잡아내지 않는다. 1s 기준으로 O(nlogn) 까지가 한계이며, 값이 ..

Introduction 사실 자세히 찾아보기 전에는 실제 업무는 Data Scientist와 Data Engineer를 모두 해야하는 줄 알았다. Data Engineer는 데이터를 가공하여 쉽게 다룰 수 있게 만들며, Data Scientist는 그러한 데이터를 분석하고 연구하여 유의미한 결과를 낸다. 앞으로 내가 공부할 것은 Data Engineer에게 있어 필요한 것들이다. 아래의 글이 많은 도움이 되었다. [취준생의 데이터 분야의 커리어 고민 3] 엔지니어가 되자 저번 글에 이어 이번에는 '엔지니어' 가 되기로 한 계기와, 준비하는 과정을 적어보려고 한다. 고민 시리즈 마지막 글이 될 듯. 추천 시스템의 기억 예전에 추천기술팀에서 인턴 할 때, 데이터 분 dailyheumsi.tistory.com..