링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqPrpnKSCQDFAT_문제경로에서 등장하는 모든 숫자의 곱에서 맨 뒷자리에 연속으로 있는 0의 개수, 즉 trailing zero의 개수의 최소를 구하는 문제입니다.trailing zero가 나오기는 위해서는 10의 배수라는 의미이고, 소인수 중 2와 5의 개수 중 작은 쪽만 확인하면 됩니다.이 부분은 BOJ 1676 - 팩토리얼 0의 개수 문제에서 풀어보시면 됩니다.가장 왼쪽 위 (1, 1) 지점에서 시작해서 오른쪽 또는 아래쪽으로만 이동한다는 점은,다음 지점의 입장에서는 위쪽 또는 왼쪽의 영향만 받는다는 의미이기도 하지요.항상 위쪽 또는 왼쪽까지 도착..

링크: https://www.acmicpc.net/problem/5535문제각 날짜마다 입을 수 있는 옷들이 있고, 다음 날과 옷의 화려함의 차이가 최대한 크도록 옷을 고르는 문제이다.날짜마다 가능한 옷을 저장해둔다. 그 날에 한해서는 옷의 종류나 순서가 중요치않길래 화려함 정도를 넣어버렸다. 이제 각 날짜마다 옷을 하나씩 고른다면, 총 D일동안 N가지의 옷을 고르므로 경우의 수는 \(O(N^{D})\) 이다. 어떤 d번째 날에 A라는 옷을 골랐다고 치자. 그럼 d+1번째 날 이후로는 d번째 날에 A를 고른 영향이 계속 생긴다.즉, d번째 날에 a를 고른 이후로는 하나의 부분 문제로 볼 수 있다. 점화식을 dp[D][N] = D번째 날에 N번째 옷을 선택했을 때의 화려함의 최대값 으로 세우면 \(O(ND..

여기서 맞왜틀이란, "맞았는 데 왜 틀렸지?"에 줄임말입니다. 이 글은 알고리즘 문제 풀이(Problem Solving)를 하면서 종종 마주하는 "맞왜틀?"을 피하는 방법들을, 제가 아는 지식과 겪어본 경험을 토대로 정리해볼까 합니다. 코드의 구현과 관련한 깊은 내용들은 C/C++을 기준으로 이야기합니다. 문제를 푸는 환경 이제는 많은 문제 풀이 플랫폼과 온라인 저지 사이트들이 있습니다. 역사 깊은 UVa Online Judge부터 Algospot(알고스팟), Baekjoon Online Jubge, 프로그래머스까지 굉장히 다양하고 많아졌습니다. 각 사이트마다 채점 방식이나 결과가 다를 수 있으니, 이것을 먼저 찾아보고 이해하는 것이 좋습니다. 어떤 컴파일러로 채점하나요? 대부분의 사이트에서 C, C++..

링크: https://www.acmicpc.net/problem/2517문제최선의 등수는 다시 말하면, "a[k] = 어떤 k 입장에서 왼쪽으로 자신보다 높은 실력의 개수" 이다."왼쪽으로"의 뜻은 "이전까지 등장한"과 같은 말이고, 자신보다 높은 실력의 개수는 기록을 통해서 셀 수 있다.문제는 수의 범위가 1,000,000,000 이하라서 수를 직접 저장하기는 힘들어 보인다.문제 조건 중, 참가한 선수들의 실력은 모두 다르다는 조건이 있다. 그럼 같은 의미로 그 사람의 등수를 기록하자.N은 50만 이하이므로, 등장한 등수(rank)를 1로 기록하고 k 위치에서 자신보다 높은 실력(=등수)는 세그먼트 트리로 쉽게 셀 수 있다.선수 k의 최선의 등수는 query(자신의 등수 + 1, 범위 끝) + 1이다...

링크: https://www.acmicpc.net/problem/1308문제풀이 재활훈련을 시작했다.문제를 푸는 데 실수가 너무 많아진다..문제날짜, 시간 차이를 구하는 문제는 정수 하나로 변환해서 퉁 치는게 제일 편하다. (년/월/일 -> 총 X일)단, 조건 중에 천년을 넘어가면 gg를 출력해야하는데, 2000/05/05 ~ 2100/04/30 같은 경우는 천년을 넘기지 않음에 조심해야한다.코드

링크: https://www.acmicpc.net/problem/17520풀이균형잡힌 문자열에서 확인하는 모든 부분 문자열은 첫번째 문자를 포함한다. 즉, 앞에서부터 순차적으로 확인하여 0와 1의 개수가 1 이상 차이가 난다면 균형잡힌 문자열이 아니라는 뜻이다. 우선 무식하게 모든 경우의 수를 다 확인해볼 수 있다. i번째 위치를 0 또는 1로 결정하면서, 균형잡힌 문자열이 되는 경우만 탐색했다. n=3일 때, 010, 011, 100, 101 네 개의 문자열이 나온다. n=1부터 하나씩 확인해보면 \(2, 2, 4, 4, 8, 8, \dots, 2^{n-1}, 2^{n-1}, 2^{n}, 2^{n}\) 로 규칙성이 보인다. 이제 문제는 \(f(n)=2^{\lfloor{(n+1)}/2\rfloor}~mo..

링크: https://www.acmicpc.net/problem/1699문제주어진 N을 최소 몇 개의 제곱수의 합으로 표현할 수 있는 지 구하는 문제이다. 문제를 풀기 전에, 라그랑주 네 제곱수 정리를 알고 있으면 좋다. 백준 온라인 저지에 문제로도 등장했다. BOJ 3933 - 라그랑주의 네 제곱수 정리 요약하면, 모든 양의 정수가 많아야 4개의 제곱수의 합이라는 정리인데, 다시 말하면 이 문제의 정답은 최대 4라는 뜻이다. \(x^a + y^b + z^c + w^d = N\) 에서 \(a,~b,~c,~d\) 를 모두 확인해 볼 필요는 없다. 라그랑주의 정리에 의하면 모든 \(a,~b,~c\)를 찾았는 데 없으면 4개로 표현할 수 있기 때문이다. 즉, 3중첩 반복문으로 해결 가능하다.코드

링크: https://www.acmicpc.net/problem/17521문제보자마자 주식 문제가 생각났다.주식 문제들은 최대 이익을 내기 위해서 그리디하게 행동하면 된다. 값쌀 때 사서 값비쌀 때 팔면 된다.이 문제에서는 늘어난 코인만큼 다시 투자를 할 수 있으니, 상승 곡선이면 무조건 사는것이 이득이다. (늘어난 코인을 배로 불릴 수 있으니)코드 직관적으로 풀었지만 내심 불안했다.그래서 dp로도 풀어보았다. 물론, 같은 결과가 나왔고 정답이다.점화식은 dp[k] := k일까지 벌 수 있는 최대 코인이다.\(i < j\) 인 \(i\)일째에 가진 돈으로 전부 매수하고, \(j\)일에 모두 매도한다면 (두 날짜 사이의 변폭) * (i일에 살 수 있었던 코인의 수)만큼 벌 수 있을것이다.