본문 바로가기

전체 글657

[programmers][월간 코드 챌린지 시즌1] 풍선 터트리기 문제 : programmers.co.kr/learn/courses/30/lessons/68646 서로 다른 숫자가 써져 있는 n개의 풍선이 있을 때, 인접한 두 풍선을 고른 뒤 두 풍선 중 큰 풍선을 터트린다고 하자. 최후까지 남아있을 수 있는 풍선을 구해라. 이 때, 단 한 번 번호가 더 작은 풍선을 터트릴 수 있다. x 번 풍선이 최후에 남아있을 수 있는지는 x를 기준으로 왼쪽에 있는 풍선들 중 가장 작은 수(1번을 제외하고는 큰 풍선을 터트리므로 작은 수만 남는다.), 오른쪽에 있는 풍선들 중 가장 작은 수를 구한 뒤 왼쪽, 오른쪽 수들 중 1개 이하의 x번 풍선의 수보다 큰 풍선이 있다면 x번 풍선은 최후까지 남아있을 수 있다. 만약 왼쪽에 있는 풍선들 중 가장 작은 수가 10. 오른쪽 풍선들 중.. 2020. 9. 17.
[programmers][월간 코드 챌린지 시즌1] 두 개 뽑아서 더하기 문제 : programmers.co.kr/learn/courses/30/lessons/68644 정수형 배열이 주어질 때 서로 다른 인덱스 수를 두 개 골라서 합했을 때 나올 수 있는 수들을 오름차순 정렬해서 반환해라. 적절한 자료구조 쓸 수 있나. 묻는거 같은 문제. 나올 수 있는 수 -> 중복 x. set에 저장한다. for(i=0 ~ n-1) for(j=i+1 ~ n-1) set.insert(num[i] + num[j]) 시간복잡도는 O(NlogN). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%9B%94%EA%B0%84%20%EC%BD%94%EB%93%9C%20%EC%B1%8C%EB%A6%B0%EC%A7%80%20%EC%8B%9.. 2020. 9. 15.
[programmers][찾아라 프로그래밍 마에스터] 폰켓몬 문제 : https://programmers.co.kr/learn/courses/30/lessons/1845 총 N 마리의 폰켓몬 중 N/2 마리를 가져갈 수 있다. 최대 고를 수 있는 폰켓몬 종류의 수를 구해라. 최대로 고를 수 있는 폰켓몬 종류의 수는 N마리의 폰켓몬 종류의 수와 N/2 중 최소값이다. N/2는 계산으로 한 번에 구할 수 있고 총 폰켓몬 종류의 수를 구하기 위해 set에 폰켓몬 종류를 저장한다. 모든 폰켓몬을 저장했을 때 set의 크기가 콘켓몬 종류의 총 수가 된다. 시간복잡도는 set을 만드는데 소요되는 시간인 O(NlogN) 소스코드 : github.com/fpdjsns/Algorithm/blob/master/programmers/%EC%B0%BE%EC%95%84%EB%9D%BC%.. 2020. 9. 13.
[programmers][찾아라 프로그래밍 마에스터] 게임 맵 최단거리 문제 : programmers.co.kr/learn/courses/30/lessons/1844 0과 1로 이루어진 게임 맵이 2차원 배열로 주어진다. 0은 벽, 1은 통로를 의미한다. 시작 위치에서 종료지점으로 가고자 할 때 최단거리를 구해라. 종료지점으로 갈 수 없다면 -1을 반환해라. 전형적인 BFS 문제. 시작 지점에서 상하좌우((-1,0), (1,0),(0,-1),(0,1))로 이동하면서 이동횟수를 저장한다. 이동한 위치가 벽(0)이라면 탐색을 종료하고 통로(1)라면 해당위치에서 상하좌우로 탐색을 계속한다. 너비우선탐색으로 탐색하며 가장 먼저 도착지 (n, m)에 도착했을 때 이동횟수가 정답이 된다. (n,m)에 도착하지 않고 탐색이 종료되었다면 -1을 반환한다. 시간복잡도는 게임맵 크기인 O(N.. 2020. 9. 13.
[programmers][찾아라 프로그래밍 마에스터] 사칙연산 문제 : programmers.co.kr/learn/courses/30/lessons/1843 숫자와 연산 기호(+, -)로 이루어진 수식이 주어질 때 괄호를 추가해 그 수식의 계산 결과는 여러가지가 나올 수 있다. 이 때 나올 수 있는 계산 결과 중 최대값을 구하여라. DP로 해결했다. 수식이 문자열 arr로 주어지고 부분문자열 arr[s~e]의 최대값, 최소값을 저장하는 배열을 만든다. 최대값 배열 dMax[s][e] = arr[s~e] 수식의 계산 결과 중 최대값. 최소값 배열 dMin[s][e] = arr[s~e] 수식의 계산 결과 중 최소값. 우리가 알고자 하는 값은 dMax[0][n-1] 인데 최대값을 구하기 위해서는 최소값도 알아야 하기 때문에 dMin 배열도 필요하다. 만약 i 인덱스가 연.. 2020. 9. 13.
[leetcode][216] Combination Sum III 문제 : leetcode.com/problems/combination-sum-iii/ 1에서 9까지의 숫자 만 사용할 수 있고 각 조합은 고유 한 숫자 집합이어야한다는 점을 고려하여 숫자 n이되는 k 숫자의 가능한 모든 조합을 찾습니다. 숫자 n을 k개의 수의 합으로 만들 때 가능한 조합들을 구하라. 이 때, 수들의 합은 1~9 중 고유한 수들의 조합이다. ex) 가능 : [1,3]. 불가능 : [2,2] -> 2가 겹침 백트래킹으로 풀었다. index 위치에 오름차순으로 숫자(let, i)를 하나씩 대입하면서 n-i, k-1 로 갱신하면서 배열을 만들어나간다. k 혹은 n이 음수가 되면 정답이 불가능한 경우다. n과 k가 모두 0이 되면 정답이 가능한 경우이므로 이때동안 만든 숫자 배열을 정답배열에 추.. 2020. 9. 12.

티스토리툴바