알고리즘 문제풀이
-
프로그래머스 땅따먹기 c++ 풀이 Level 2 연습문제 땅따먹기 문제 정리 땅따먹기의 땅은 총 N행 4열 모든 칸에는 점수가 있다. 1행부터 땅을 밟으며 한 행씩 내려오며, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 한다. 단, 한 행씩 내려올 떄, 같은 열을 연속해서 밟을 수 없다. 마지막 행 까지 내려왔을 때, 얻을 수 있는 점수의 최대값으 구하여라. 문제 접근 DP??? 백준의 진우의 달 여행(Large) 문제와 비슷한 방식이라고 생각했습니다. 우선 dfs로 풀어보았습니다. 효율성 테스트도 있어서 시간초과 발생!!! 그래서 이번에는 풀이를 머릿속에 넣고 dp로 접근했습니다. 풀이가 잘 기억이 나지 않아 달 여행 문제 풀이를 보고 손으로 정리해보았습니다. 3차원 배열을 만들어서 [이전 col][현..
[DP] 프로그래머스 level2 땅따먹기 c++ 풀이프로그래머스 땅따먹기 c++ 풀이 Level 2 연습문제 땅따먹기 문제 정리 땅따먹기의 땅은 총 N행 4열 모든 칸에는 점수가 있다. 1행부터 땅을 밟으며 한 행씩 내려오며, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 한다. 단, 한 행씩 내려올 떄, 같은 열을 연속해서 밟을 수 없다. 마지막 행 까지 내려왔을 때, 얻을 수 있는 점수의 최대값으 구하여라. 문제 접근 DP??? 백준의 진우의 달 여행(Large) 문제와 비슷한 방식이라고 생각했습니다. 우선 dfs로 풀어보았습니다. 효율성 테스트도 있어서 시간초과 발생!!! 그래서 이번에는 풀이를 머릿속에 넣고 dp로 접근했습니다. 풀이가 잘 기억이 나지 않아 달 여행 문제 풀이를 보고 손으로 정리해보았습니다. 3차원 배열을 만들어서 [이전 col][현..
2020.07.04 -
프로그래머스 다음 큰 숫자 c++ 풀이 Level 2 연습문제 다음 큰 숫자 문제 정리 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음고 같다. ``` n의 다음 큰 숫자는 n보다 큰 자연수 n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같다. n의 다음 큰 숫자는 조건 1,2를 만족하는 수 중 가장 작은 수 n은 1,000,000 이하의 자연수이다. 문제 풀이 n보다 큰 숫자부터 2진수로 변환하여 1의 개수를 세본다. 개수를 세서 n의 1의 개수와 같다면 조건 1을 만족하고, 자동으로 조건 2도 만족하게 된다. 1의 개수는 이진수로 변환하는 로을 그대로 적용하면 된다. 2로 나눠서 2로 나눠 떨어지지 않는다면 1이 하나 있다는 뜻이다. 이를 n이 2나 1이 될때까지 반복한다. 마지막..
[2진수 변환] 프로그래머스 level2 다음 큰 숫자 c++ 풀이프로그래머스 다음 큰 숫자 c++ 풀이 Level 2 연습문제 다음 큰 숫자 문제 정리 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음고 같다. ``` n의 다음 큰 숫자는 n보다 큰 자연수 n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같다. n의 다음 큰 숫자는 조건 1,2를 만족하는 수 중 가장 작은 수 n은 1,000,000 이하의 자연수이다. 문제 풀이 n보다 큰 숫자부터 2진수로 변환하여 1의 개수를 세본다. 개수를 세서 n의 1의 개수와 같다면 조건 1을 만족하고, 자동으로 조건 2도 만족하게 된다. 1의 개수는 이진수로 변환하는 로을 그대로 적용하면 된다. 2로 나눠서 2로 나눠 떨어지지 않는다면 1이 하나 있다는 뜻이다. 이를 n이 2나 1이 될때까지 반복한다. 마지막..
2020.07.03 -
BOJ 1021번 회전하는 큐 c++ 풀이 랭크 : 실버4 백준 1021번 회전하는 큐 문제 정리 N개의 원소를 포함하고 있는 양방향 순환 큐가 있다. 첫 번째 원소를 뽑아낸다. 왼쪽으로 한 칸 이동. a1..ak -> a2..ak, a1 오른쪽으로 한 칸 이동 a1...ak -> ak, a1...ak-1 뽑아내려고 하는 원소의 위치가 주어질 때, 원소를 주어진 순서대로 뽑아내는데 필요한 4,5번 연산의 최솟값을 구하여라 문제 접근 arr의 idx 번째 수를 맨 앞에 나오게 만들어야 합니다. 그래야 pop해서 순서를 만들 수 있습니다. 최소의 연산을 하기 위해서는 왼쪽으로 움직여서 맨 앞으로 가져오느 경우, 오른쪽으로 움직여서 맨 앞으로 가져오는 경우 모두 해보아야 합니다. 그래서 왼쪽으로 움직여서 id..
[deque, 덱] 백준 1021번 회전하는 큐 c++ 풀이BOJ 1021번 회전하는 큐 c++ 풀이 랭크 : 실버4 백준 1021번 회전하는 큐 문제 정리 N개의 원소를 포함하고 있는 양방향 순환 큐가 있다. 첫 번째 원소를 뽑아낸다. 왼쪽으로 한 칸 이동. a1..ak -> a2..ak, a1 오른쪽으로 한 칸 이동 a1...ak -> ak, a1...ak-1 뽑아내려고 하는 원소의 위치가 주어질 때, 원소를 주어진 순서대로 뽑아내는데 필요한 4,5번 연산의 최솟값을 구하여라 문제 접근 arr의 idx 번째 수를 맨 앞에 나오게 만들어야 합니다. 그래야 pop해서 순서를 만들 수 있습니다. 최소의 연산을 하기 위해서는 왼쪽으로 움직여서 맨 앞으로 가져오느 경우, 오른쪽으로 움직여서 맨 앞으로 가져오는 경우 모두 해보아야 합니다. 그래서 왼쪽으로 움직여서 id..
2020.07.03 -
BOJ 11723번 집합 c++ 및 java 풀이 난이도: 실버5 백준 11723번 집합 문제 정리 비어 있는 공집합 S가 주어졌을때 다음 연산을 수행하는 프로그램을 작성하시오 add x : S에 x를 추가한다. (1
[비트마스킹, set] 백준 11723번 집합 c++, java 풀이BOJ 11723번 집합 c++ 및 java 풀이 난이도: 실버5 백준 11723번 집합 문제 정리 비어 있는 공집합 S가 주어졌을때 다음 연산을 수행하는 프로그램을 작성하시오 add x : S에 x를 추가한다. (1
2020.06.30 -
BOJ 11724번 연결 요소의 개수 c++ 및 java 풀이 난이도: 실버3 백준 11724번 연결 요소의 개수 문제 정리 방향 없는 그래프가 주어질때 그래프의 연결 요소(Connected Component)의 개수를 구하시오 연결 요소 란?? 그래프는 여러 개의 고립된 그래프로 구성될 수 있는데 서로 연결된 여러 개의 고립된 그래프 각각을 연결 요소라고 한다. 연결 요소의 특징 연결 성분에 속한 모든 정점을 연결하는 경로가 있어야 한다. 또 다른 연결 성분에 속한 정점과 연결하는 경로가 있으면 안된다. BFS, DFS를 통해 시작 정점으로부터 도달 가능한 모든 정점들이 하나의 연결성분이 된다. 문제 접근 처음에 주어진 예제를 잘못 보고 문제를 이해를 잘 못해서 빨리 풀지 못했습니다 ㅠㅠㅠ 예제를 똑바..
[유니온 파인드, bfs] 백준 11724번 연결 요소의 개수 c++, java 풀이BOJ 11724번 연결 요소의 개수 c++ 및 java 풀이 난이도: 실버3 백준 11724번 연결 요소의 개수 문제 정리 방향 없는 그래프가 주어질때 그래프의 연결 요소(Connected Component)의 개수를 구하시오 연결 요소 란?? 그래프는 여러 개의 고립된 그래프로 구성될 수 있는데 서로 연결된 여러 개의 고립된 그래프 각각을 연결 요소라고 한다. 연결 요소의 특징 연결 성분에 속한 모든 정점을 연결하는 경로가 있어야 한다. 또 다른 연결 성분에 속한 정점과 연결하는 경로가 있으면 안된다. BFS, DFS를 통해 시작 정점으로부터 도달 가능한 모든 정점들이 하나의 연결성분이 된다. 문제 접근 처음에 주어진 예제를 잘못 보고 문제를 이해를 잘 못해서 빨리 풀지 못했습니다 ㅠㅠㅠ 예제를 똑바..
2020.06.28 -
BOJ 1676번 팩토리얼 0의 개수 c++ 및 java 풀이 난이도: 실버3 백준 1676번 팩토리얼 0의 개수 문제 정리 N이 주어질때 N!의 맨 뒤에서 부터의 0이 아닌 숫자가 나올때 까지의 0의 개수를 구하여라 N은 0이상 500이하의 수이다. 문제 접근 처음에는 나이브하게 팩토리얄을 직접구해보려 했습니다. 하지만 역시나 20!까지 밖에 구할 수 없었습니다. 그래서 규칙을 찾아보았다. 16팩토리얄 까지 구해보면서 0의 개수가 군수열을 이루는것 같았습니다. 그래서 그렇게 풀었지만 실패... 그래서 다른 방법을 생각해보았습니다. 10이 몇개 곱해지는지 찾는 것!! 10이 몇개있는지 찾기 위해 인수분해하여 2와 5가 몇개있는지 찾아갑니다. 그리고 2와 5의 개수중 최소값이 10의 개수가 됩니다. 예를들..
[수학, DP] 백준 1676번 팩토리얼 0의 개수 c++, java 풀이BOJ 1676번 팩토리얼 0의 개수 c++ 및 java 풀이 난이도: 실버3 백준 1676번 팩토리얼 0의 개수 문제 정리 N이 주어질때 N!의 맨 뒤에서 부터의 0이 아닌 숫자가 나올때 까지의 0의 개수를 구하여라 N은 0이상 500이하의 수이다. 문제 접근 처음에는 나이브하게 팩토리얄을 직접구해보려 했습니다. 하지만 역시나 20!까지 밖에 구할 수 없었습니다. 그래서 규칙을 찾아보았다. 16팩토리얄 까지 구해보면서 0의 개수가 군수열을 이루는것 같았습니다. 그래서 그렇게 풀었지만 실패... 그래서 다른 방법을 생각해보았습니다. 10이 몇개 곱해지는지 찾는 것!! 10이 몇개있는지 찾기 위해 인수분해하여 2와 5가 몇개있는지 찾아갑니다. 그리고 2와 5의 개수중 최소값이 10의 개수가 됩니다. 예를들..
2020.06.27