gaki gaki

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 문제 풀이 이 문제는 재귀를 이용한 완전탐색으로 쉽게 해결할 수 있다. 숫자 앞에 + 나 - 둘 중 1개가 올 수 있으므로, 총 만들수 있는 경우의 수는 2^n 이다. 즉 Big(O) = 2^n 이다. 문제에서 n 의 범위가 20 이하라고 했으므로( 백만번 계산 ), 시간초과는 절대 안걸린다. 시간 복잡도 Big(O) = 2^n..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 문제풀이 원을 따라 위치한 집들을 털 때, 최대로 훔칠 수 있는 값을 리턴하는 문제이다. 이 문제에서는 기준점을 정해주는 것이 풀이의 첫단추를 꿰는 것이다. 나는 1번 째 집을 기준점으로 정했고, 1번째 집을 터는 경우와 털지 않는 경우 두 가지로 나누어서, 두 케이스 중 최댓값을 리턴하는 식으로 진행했다. 그리고 1번째 집부터 n 번째 집까지 순서대로..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 문제풀이 삼각형의 경로를 지나면서 최대값을 가지는 경로를 구하는 문제이다. 삼각형 트리안에 들어가는 값들은 0보다 크거나 같은 정수이기 때문에, 맨 아랫줄 삼각형의 누적값들 중 최대값을 고르면 되는 문제이다. Sum(i,j) = V(i,j) + max(Sum(i-1, j-1), Sum(i-1, j)) 라는 점화식을 이용해 풀면 되는데, i, j 값이 오바되지 않도록 예외처리만 신경써주면 쉬운 문제이다. 시간복잡도 n 층의 n ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제 풀이 정수 N 을 최소로 사용해서 K 를 만들어야한다. 최대 8번까지 N 을 사용 할 수 있고, 8번이 넘어갈 경우 -1 을 리턴하면 된다. DP 를 사용해서 풀 수 있으며, N 을 1 번 사용했을 때, 2번 사용했을 때, 3번 사용했을 때 .... 8번 사용했을 때의 값들 중에서 K 가 있는지 확인하고 K 가 있으면 몇 번 사용했을때 K 가 나왔는지를 리턴하면 된다. n 이라는 배열을 사용했고, n[i] 는 n 을 i 번 사용했을 때 나올 수 있는 모든 경우의 수들의 집합이다. 또한, 중복되는 숫자의 방지를 위해서 tota..

자바스크립트 클로저란 무엇인가? 요약 클로저란, 함수의 컨택스트가 사라져도 해당 컨택스트에 존재하던 변수에 접근할 수 있는 함수를 말한다. 예시 코드 function first() { let count = 0; return function second() { console.log(count); count += 1; } } const closer = first(); closer(); // 0 closer(); // 1 closer(); // 2 설명 위의 코드에서 closer 라는 상수에 의해 first 라는 함수가 실행되면 second 라는 함수를 리턴하고 가비지 컬렉터에 의해 제거된다. 그 말은 즉슨 first 라는 함수 스코프에 존재하던 count 라는 변수 또한, 제거되었음을 나타낸다. 하지만, c..

Graphql 이 Rest API 보다 나은 점 1. Rest API Rest API 는 특정 URL 에 요청을 보내면 서버가 해당 요청에 맞는 응답을 한다. Rest API 는 사용하기 간편하다는 장점이 있다. 1-1. Rest API 의 단점 Rest API 는 over-fetching 과 under-fetching 의 문제가 있다. over-fetching 은 내가 필요한 정보보다 더 많은 정보를 서버에서 받는 것이다. 예를 들어, 내가 유저 이름만 필요한데, Rest API 설계상 유저 정보를 Get 하면 유저 이름뿐만 아니라, 부가적으로 유저 닉네임이나 기타 다른 정보들까지 받을 수 밖에 없다. ( 각 상황에 맞는 Rest API 를 설계하지 않는이상..) 그렇게 되면, 필요 없는 정보들 까지도..

100일 동안 매일 알고리즘을 하면? - 14일차 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 이 문제는 크루스칼(Kruskal) 알고리즘으로 풀 수 있는 문제이다. 크루스칼 알고리즘을 이해하기 위해서 2가지 배경지식이 필요한데, 첫번째는 spanning tree 이고, 두번째는 union-find 이다. 1. spanning tree 란? spanning tree 는 n 개의 정점을 (n-1) 개의 간선을 사용해서 모두 연결하는 트리이다. 여러 spanning tree 중, 모든 간선의 비용 합이 가장..

100일 동안 매일 알고리즘을 하면? - 13일차 https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 큰수 만들기문제는 오름차순및 내림차순을 활용한 문제였다. 이 문제에서 12번 테스트케이스 "999",2 를 통과하지 못했었다. 테스트를 통과하지 못했던 이유는 오름차순, 내림차순에만 신경쓰다보니 같은 숫자가 나왔을때 k 값을 어떻게 처리해야 하는지에 대해서는 고려하지 않았던게 패인이였다. 오름차순, 내림차순으로 값을 처리할때는 계속 같은 값이 나오는 상황을 반례로 만들어놓고 풀자. def ans(deleted, number): answer = ""; for idx,v in enumerate..