[백준] 2225번 [python]
[백준] 2225번 [python] 문제 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 해당문제는 DP문제로 점화식을 구하면 풀수있다. 해당 점화식을 구해보도록 하자 N = 4, K = 3라고 가정할때 정수 0을 만들기 위해 갯수 1개인경우는 (0), 1개 갯수 2개인경우는 (0,0), 1개 갯수 3개인경우는 (0,0,0) , 1개이다. 또한 정수 2를 만들기 위해 갯수 1개인경우는 (2), 1개 갯수 2개인경우는 (0,2), (0,2), (1,1), 3개 갯수 3개인경우는 (0,0,2), (0,2,0), (2,0,0), (0,1,1), (1,0,1), (1,1,0),..
2020. 11. 3.
[프로그래머스] 지형이동
[프로그래머스] 지형이동 문제 https://programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 코드 이 문제는 최근에 풀었던 알고리즘 문제중에서 가장 어려웠던것같다. 우선 가장 처음에 문제에 접근할때 사다리 없이 이동 가능한 그룹끼리 그룹을 생성 현재 자리의 4방향을 탐색하면서 나와 다른 그룹을 경우 높이차를 측정 최소 높이차를 측정하여 결과를 구함 이 ..
2020. 9. 2.
[프로그래머스] 길찾기게임
[프로그래머스] 길찾기게임 문제 https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 코드 이 문제를 풀기위해 class를 이용한 트리구조생성과 전위순회, 후위순회를 다시한번 공부할수있었습니다. 우선 해당 문제의 조건에 맞게 class를 이용한 이진 트리(Binary Tree) 를 구현 이진트리의 각각의 노드의 property는 x, y, left, right, index를 갖고있습니다. 만들어진 이진트리에서 전회순..
2020. 8. 28.
[프로그래머스] 자물쇠와 열쇠
자물쇠와 열쇠 문제 https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 코드 이 문제는 2차원배열의 범위가 작기때문에 모든 경우를 탐색하면 풀수있다. 하지만 모든 경우를 탐색하는것도 생각보다 어려웠다. 길이가 N인 2차원 배열 lock을 (M -1) * 2 + N 의 배열로 늘려서 lock을 가운데에 넣고 key를 0, 0부터 90도씩 회전시켜나가면서 모든 위치를 확인하면서 풀었다. empty_lock 함수를 통해 자물쇠에서 비어있는 위치와 잠겨있는 위치를 찾아..
2020. 8. 27.