본문 바로가기

알고리즘 문제/Programmerse42

[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.
[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.

티스토리툴바