프로그래밍에 대한 고찰 및 생각

문제이해 문제에서는 총 N개의 그림이 주어지고 각 그림마다 높이와 가격이 존재한다. 중요한 부분은 앞에서 보았을때 보이는 폭의 길이가 특정정수 S이상이 되어야 판매가능한 그림이 된다는점이다. 이부분을 중점으로 생각해보자 알고리즘 전략 먼저 앞에서 봤을때 보이는 폭의 길이가 중요한 포인트이므로 높이와 가격을 가진 각각의 그림들을 구조체로 선언해주고 높이를 오름차순으로 정렬해주자. 그리고 배열 dp[i]를 이렇게 정의하자. dp[i] : i번째그림까지중 i번째그림을 무조건 선택한다고 했을때 최대 가격의 합 그리고 문제에서는 모든 그림들을 배열한다고 했지만 편의상 총가격에 포함되는 그림들을 선택하고 불필요한 그림들은 선택하지 않는다고 생각하자. 그렇다면 점화식은 어떻게되는지 보자. price[i] 를 i번째 ..

문제 이해 백준저지에는 이미 n x m의 격자상에 특정 블록을 넣어 채우는 경우의 수를 구하는 문제들이 많다. 2 x N 격자에 2 x 1 , 1 x 2 크기의 타일로 채우는 경우의 수를 구하는 11726번 https://www.acmicpc.net/problem/11726 2 x N 격자에 2 x 1 , 2 x 2 크기의 타일로 채우는 경우의 수를 구하는 11727번 https://www.acmicpc.net/problem/11727 3 x N 격자에 2 x 1 , 1 x 2 크기의 타일로 채우는 경우의 수를 구하는 2133번 https://www.acmicpc.net/problem/2133 좌우대칭을 고려해야하는 1720번 https://www.acmicpc.net/problem/1720 위의 타일링..

문제 이해 문제자체는 간단하지만 n이 조금만 커져도 경우의수가 커지고 점화식도 쉽게 발견되지 않아 조금은 까다로웠던 문제였다. 서로 팔이 교차하지 않는 것을 중점으로 생각해봐야 할것같다. 알고리즘 전략 점화식에 접근할때 n이 주어졌을때 그 상황들을 분해하려고 고민을 했다. 먼저 n = 8 일때로 먼저 분석을 해보자. ( 편의상 n=k일때 가능한 경우의 수를 dp[k]라고 하자 ) 이 상황에서 악수를 할수 있는 경우의 수를 찾다보면 한가지 규칙을 찾을 수 있다. 어떤사람과 어떤사람이 악수할때 그 둘 사이에 있는 사람의 수가 홀수가 되면 안된다는 것이다. 따라서 파란색 점을 기준으로 할때 이 사람이 악수 할수 있는 사람은 위의 3점과 자신을 제외한 4개의 점이다. 파란색이 악수 할수있는 점은 다음과 같다. ..

문제이해 n x m 의 보드에 숫자들이 주어지고 특정지점에서 출발해서 특정조건에 따라 상하좌우로 이동하며 최대,최소의 경우를 구하는 전형적인 문제이다. 다만 여기서는 무한번 움직인다면 -1을 출력해야하므로 이부분이 까다로울수 있다. 알고리즘 전략 [0][0] 지점에서 시작해서 해당칸의 숫자만큼 상하좌우로 이동할수 있으므로 모든 경우를 확인해봐야한다. 따라서 재귀함수를 이용한 brute-force 와 메모이제이션을 이용해 DP로 해결하면 될것같다. 문제에따르면 최대한 보드 내에서 많이 움직여야하는데 보드바깥으로 나가거나 H를 만나면 종료되므로 해당조건으로 설계하면 이부분은 간단하다. 중요한 부분은 무한번 움직이는것을 어떻게 캐치해낼것인지이다. 쉽게생각하면 이런경우를 떠올릴수 있다. 위 상황은 1-3을 보면..

문제이해 문제에서는 다채로운 색이 등장하지만 단순하게 n등분 되어있는 원에서 인접하지않게 k개를 색칠하는 경우의 수를 구하는 문제이다. 알고리즘 전략 알고리즘 구현을 위한 첫걸음은 노트북에서 잠시 손을 내려놓고 펜과 종이로 직접 구해보는것이다. 무언가 규칙성이 있을것같았고 점화식이 있을것같았다. N=6 K=2 일때의 경우로 생각해보자 6개의 칸이 있고 2칸을 이웃하지않게 색칠하는 경우의 수를 구하는 문제이다. 이를 편의상 앞으로 color(6,2) 라고 하자 color(6,2)를 구하기 전에 color(5,2) 를 한번보자 color(5,2)는 다음과 같이 5가지이다 여기서 마지막 칸을 두개로 쪼갠다면 다음과 같다. 바로 위의 5가지 경우는 color(6,2) 의 경우의 수들중 일부이다. color(6,..

문제이해 설명에 앞서 문제에 제시된 M(1≤M≤⌈(N/2)⌉) 에서 ⌈x⌉ 기호는 x보다 작지않은 최소 정수를 의미한다. 예를들어 N=10 M=3일때 가능한 조합들중 일부는 다음과같다. 알고리즘 전략 가장 쉽게 떠올릴수 있는 방법은 모든 경우의 수를 전부 해보는것이다. 단 일반 재귀로 작성하면 재귀호출만 해도 말그대로 2^N 만큼의 시간복잡도를 가지므로 중복호출되는 함수는 그 값을 미리 메모이제이션을 해두고 바로 값을 불러오도록 처리를 하면 될것이다. 또한 이 문제는 k번째 값을 선택할지말지 고를때 그 앞의 (k-1)개의 선택 현황에 따라 선택지가 달라질수 있다. 즉 앞의 상황과 독립적이지 않다는 것이다. 만약 앞에서 주어진 구간개수를 모두 만들었다면 k이후로는 모든 수를 선택하지 못할수도있다. 여기서 ..

문제이해 이 문제에서 헷갈릴수 있는 부분은 주어진 추들을 모두 사용할 필요가 없다는 것이다. 예를들어 추가 1g 3g 5g짜리가 있다면, 5g짜리 하나만 사용해서 5g짜리 구슬을 측정할수있다. 알고리즘 전략 따라서 예를들어 3개의 추(1g, 3g, 7g)를 가지고 있다고 할때, 첫번째 추(1g)의 경우 세가지 선택권이 있다. 1. 왼쪽저울에 놓는다 2. 오른쪽저울에 놓는다 3. 저울에 아예 올리지 않는다. 그리고 각각의 경우에따라 두번째 추(3g)도 역시 세가지 선택권이 있다. 1. 왼쪽저울에 놓는다 2. 오른쪽저울에 놓는다 3. 저울에 아예 올리지 않는다. 마지막추도 역시 동일하다 1. 왼쪽저울에 놓는다 2. 오른쪽저울에 놓는다 3. 저울에 아예올리지 않는다. 따라서 3^3 만큼의 경우의수가 존재한다...

문제이해 이 문제의 포인트는 단어의 자릿수에 따라 해당 알파벳의 파워가 달라진다는 것이다. 예를 들어 GCF + ACDEB 의 경우 ACDEB라는 단어는 5글자로 A,C,D,E,B에 각각 9,8,7,6,5 를 대입해주면 98765 라는 숫자가 나온다. 즉 A에는 9를 넣고 B에는 5를 넣었는데 결론적으로 A = 90000 B = 5가 된 셈이다. 즉 단어의 길이가 길면서 앞쪽에 있는 알파벳들이 가지는 영향력이 크다는 의미이다. 따라서 ACDEB라는 단어가 주어졌을때 각각의 알파벳이 0~9중에 어떤 숫자를 배정받게 될지는 모르지만 확실한것은 각각 배정받은 숫자에서 A는 10000배의 C는 1000배의 D는 100배의 E는 10배의 B는 그 숫자만큼의 영향력(전체 합의 수치를 바꿔주는)을 가지게 된다. 알고..