본문 바로가기

STUDY/Algorithm

(3)
[알고리즘] SW Expert Academy 10806. 수 만들기 문제 풀이 (사고의 흐름) 문제를 읽어보면, N개의 수 a,b,c....(>=2) 가 주어지고 이 수들을 곱한 값들을 더해서 K를 만드는 문제이다. 이때, K를 만들기위해 수를 더하는 회수를 최소로 해야한다. 처음에 문제를 풀기위해 "답을 구하기 위한 하나의 정확한 로직이 있을것이다" 라는 생각을 해버렸다. 계속 반복문을 돌려가서 정답을 찾아가는 것이 아닌, K에 a,b,c...를 곱하여 만들 수 있는 K보다 작거나 같은 수를 빼고... 남은값에서 이를 다시 반복하면 정답이 나올거라고 생각했다. 하지만 반례가 계속해서 나왔고 로직을 수정해보아도 새로운 반례가 나왔다. 그래서 다시 처음부터 생각을 고쳤다. "답을 한번에 구하는 완벽한 로직은 없다. 최선으로 계속 시도해서 답을 찾아보자". 수를 더하는 회수..
[알고리즘] SW Expert Academy 10033. 카드 뒤집기 문제풀이(사고의 흐름) 문제를 보고 처음에는 어떻게 풀어야할지 바로 감이 오지 않았다. 문자열과 문자열을 바꿀수 있는 동작을 주고, 동작이 최대 몇번 수행되어야 하는지 조건이 주어졌지만, 바로 풀이 코드가 떠오르지 않았다. 이런 상황에서는 샘플을 만들고 이를 조건대로 수행하며 법칙을 찾아내는 편이다. 그래서 예제 문자열을 조건에 따라 동작을 수행하여 보았다. BWBWBW // 시작 문자열 WBBWBW // 동작수행 1 WBWBBW // 동작수행 2 WWBBBW // 동작수행 3 WWBBWB // 동작수행 4 WWBWBB // 동작수행 5 WWWBBB // 동작수행 6 이렇게 샘플을 한번 돌려보니, 바로 직감이 떠올랐다. "모든 수행의 끝에는 결국 모든 W는 왼쪽으로 가고, 모든 B는 오른쪽으로 가는구나!..
[알고리즘] SW Expert Academy 10032. 과자 분배 문제 풀이 (사고의 흐름) 문제를 보고 가장 처음든 생각은 N이 K로 딱 나누어 떨어지면 모두 같은 수의 과자를 먹을 수 있다는 것이다. 그리고 자연스럽에 N이 K로 딱 나누어 떨어지지 않으면 어떤지 생각해 보았다. 다르게 말하면 N이 K로 나누었을 때, 나머지 Z(K보다 작다)가 있다는 말이고 Z개의 과자는 Z명의 사람들에게 1개씩 줄 수 있다. 즉, Z명의 사람들은 과자 1개씩을 더 받게되고, K-Z명의 사람들은 과자를 더 받지 못한다. 이 상황에서 과자 수 차이는 1이다. 결론적으로 다음과 같다고 할 수 있다. N이 K로 나누어 떨어질 때(N%K == 0), 과자수 차이는 0 N이 K로 나누어 떨어지지 않을 때(N%K != 0), 과자수 차이는 1 정답 코드 #include iostream int ..