본문 바로가기

프로그래머스4

[programmers][월간 코드 챌린지 시즌1] 짝수 행 세기 문제 : programmers.co.kr/learn/courses/30/lessons/68647 0과 1로 이루어진 2차원 배열이 주어질 때 조건을 만족하며 만들 수 있는 2차원 배열의 경우의 수를 구하여라. 1. 모든 원소는 0, 1이다. 2. 입력으로 주어지는 배열의 각 열이 가진 1의 개수와 새롭게 만드는 배열의 각 열의 1의 개수는 같다. 3. 각 행의 1의 개수는 짝수이다. 경우의 수의 10^7 + 19로 나눈 나머지를 반환해라. dp로 풀었다. let, n = 입력 배열의 행의 수, m = 입력 배열의 열의 수. dp[column][num] = arr[0~n][0~column]까지 1,2번 조건을 만족하면서 num개의 행이 짝수인 배열을 만들 수 있는 경우의 수 dp 배열은 위와 같다. dp .. 2020. 9. 20.
[programmers][월간 코드 챌린지 시즌1] 삼각 달팽이 문제 : programmers.co.kr/learn/courses/30/lessons/68645 정수 n이 주어질 때 밑변, 높이가 n인 삼각형을 반시계 방향으로 달팽이 채우기를 진행한 배열을 구해라. ex) n = 3 1 2 6 3 4 5 queue, stack을 이용했다. n, n-1, n-2, n-3 ... 1 개씩 배열을 아래, 오른쪽, 위로 채워나간다. 이때, 아래, 오른쪽을 채울 때는 수를 큐에 넣고 위에 넣을 때는 스택에 넣는다. 높이가 n인 삼각형이므로 크기가 n인 queue 배열, stack 배열 2개가 필요하다. queue[i], stack[i] 에는 삼각형의 i형에 들어갈 수를 저장한다. 모든 배열을 채웠을 때, i를 처음부터 끝까지 탐색하면서 queue에 있는 수를 먼저 넣고 sta.. 2020. 9. 17.
[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.

티스토리툴바