알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 타일 장식물

문제 : https://programmers.co.kr/learn/courses/30/lessons/43104 서론 피보나치수열과 DP문제. 프로그래머스의 레벨3 문제들만 풀고있는데, 같은 레벨인 문제들도 난이도 격차가 꽤 큰거같다. 이 문제는 DP의 전형적인 문제다. 풀이 그림이 그려져있다. 1, 1, 2, 3, 5, 8.... 피보나치수열이다. 그럼 DP를 이용한다. 문제를 보니 둘레를 구해야하는데 answer = (dp[N-1] + dp[N-2] + dp[N-2] + dp[N-3])*2; 위와 같이 점화식을 만들 수 있다. 그리고 N이 1, 2일때는 dp배열의 음수인덱스를 가지기 때문에 예외처리해줘야하는데, 예외처리를 해주지 않아도 통과한다. 테스트케이스가 없나보다. 구현 // c++ #includ..

2019. 10. 10. 22:38
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 N으로 표현

*** 제 풀이가 프로그래머스 테스트케이스들은 통과했으나 코드를 리뷰해주신 분을 통해 틀린 결과를 출력하는 케이스가 있음을 알게 되었습니다. 그래서 기존 코드를 수정하려고 했으나 쉽게 해결되지 않아서 다른 방법으로 새롭게 풀이했습니다. 아래 글은 기존의 틀린 풀이(#2)와 새로운 풀이(#1)를 모두 포함하고 있습니다. *** 문제 : https://programmers.co.kr/learn/courses/30/lessons/42895 #1 수정된 풀이 풀이과정 예와 같이 5를 통해서 어떠한 수를 찾고자 할때 먼저 2차원 행렬을 만들고 1행은 5 하나로 만들 수 있는 수들을 넣고 2행은 5 두개로 만들 수 있는 수들을 넣고 3행은 5 세개로 만들 수 있는 수들을 넣는것을 9행까지 반복한다. 그리고 행렬에서..

2019. 10. 9. 19:22
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 2 x n 타일링

문제 : https://programmers.co.kr/learn/courses/30/lessons/12900 서론 DP문제. 풀이 문제에 1000000007로 나눈 나머지를 출력하라는 조건이 있다. DP문제일 가능성이 매우 높으므로 규칙성을 찾는다. 직접 그려보니 result[n] = result[n-1] + result[n-2]인것 같다. 간단한 코드니 DP로 구현해본다. 통과. 구현 // c++ #include using namespace std; int dp[60001]; int solution(int n) { int answer = 0; dp[0] = 1; dp[1] = 2; for(int i=2; i

2019. 10. 9. 16:02
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 카카오 프렌즈 컬러링북

문제 : https://programmers.co.kr/learn/courses/30/lessons/1829 풀이 DFS를 이용. picture의 모든칸에 방문하지 않았거나 값이 0이 아니면 DFS를 실행한다. DFS를 한번 실행할때마다 하나의 영역이 만들어지고, DFS를 실행한 횟수가 영역의 개수다. 영역을 만들기 위해 실행한 DFS는 방문하지 않았고 현재 칸의 값과 같은 값을 가지는 칸을 상하좌우로 방문해서 방문처리하는것을 반복한다. 그리고 방문할때마다 cnt변수값을 1증가시켜서 최종적으로 리턴할때 cnt값이 이번 DFS의 max_size_of_one_area가 된다. 영역이 만들어질때마다 기존 max_size_of_one_area과 비교해서 큰값으로 갱신한다. 구현 //c++ #include #in..

2019. 10. 9. 12:42
알고리즘/문제풀이 - 백준

백준 15684 사다리 조작

문제 : https://www.acmicpc.net/problem/15684 서론 브루트포스 문제. 재귀를 이용하여 완전탐색했다. 풀이 의사코드는 main(){ 사다리 입력받음 사다리설치() 결과 출력 } 사다리설치(좌표, 추가한 사다리 개수, 사다리 설치){ if(좌표가 지도의 끝){ 사다리를 탄다(); if(사다리를 타보니 조건이 맞다) 결과 갱신 } 다음칸으로 이동할 좌표 생성 if(다음칸 사다리가 설치되어 있지 않다){ 다음칸 사다리 설치 사다리설치(다음칸 좌표, 추가한 사다리 개수+1, true) 다음칸 사다리 회수 } 사다리설치(다음칸 좌표, 추가한 사다리 개수, false) } 먼저 사다리를 지도에 입력해야하는데, 입력조건에 보면 가로선의 정보는 a, b로 나타내고 b번 세로선과 b+1번 세..

2019. 10. 7. 14:07
알고리즘/문제풀이 - 백준

백준 15686 치킨 배달

문제 : https://www.acmicpc.net/problem/15686 서론 재귀를 이용한 완전탐색문제. 아이디어 2차원 배열을 만들지는 않고, 지도를 입력받을때 1이면 집 벡터에 좌표를 넣어주고 2면 치킨 벡터에 좌표를 넣어준다. 도시에 있는 치킨집 중 최대 M개를 골라서 가장 작은 도시의 치킨거리를 구해야하는데, 최대M개를 고르라고 해서 M개를 고르는 경우의 수, M-1을 고르는 경우의 수, M-2를 고르는 경우의 수 ....를 고려할 필요는 없이 M개를 고르는 경우의 수만 고려하면 된다. 치킨집이 M-1에 비해 M개면 수익이 감소할지는 모르나 우리는 치킨거리만 고려하면 되고, 치킨거리는 치킨집이 많을수록 당연히 작다. 그래서 도시에 있는 총 치킨집 중 M개를 골라야 하는데, 고를 수 있는 모든..

2019. 10. 5. 13:42