복습노트 복습노트

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 다음과 같이 n개의 제품이 n개의 공장에서 생산비용이 정해져 있다. 최소 비용을 구해라. 위의 예시에서는 1 = C, 2 = A, 3 = B 를 하면 최소비용이 된다. 3

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 영준이는 학생들의 시험을 위해 N개의 문제를 만들었다. 각 문제의 배점은 문제마다 다를 수 있고, 틀리면 0점 맞으면 배점만큼의 점수를 받게 된다. 학생들이 받을 수 있는 점수로 가능한 경우의 수는 몇 가지가 있을까? 2 3 2 3 5 10 1 1 1 1 1 1 1 1 1 1 예를 들어, 첫 번쨰 Testcase의 경우, 총 문제의 개수는 3개이며 각각의 배점은 2, 3, 5점이다 가능한 시험 점수의 경우의 수를 살펴보면 0, 2, 3, 5, 7, 8, 10의 7가지가 있다. 두 번째 Testcase의 경우, 총 문제의 개수는 10개이며 각각의 배점은 모두 ..

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 사재기를 해서 최대로 얻는 이익을 구하는 문제 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다. 첫 날에 1을 1개 구매 = -1 두번째 날에 2를 1개 구매 = -2 따라서 총 -3을 지불하고 세번째 날에 값이 3으로 올랐으므로 가지고 있는 2개를 팔면 (2 * 3 = 6) 이다. 따라서 6 - 3 = 3의 이득을 봤다. 구매는 최대 1개만 할 수 있다(안살 수도 있음) 판매는 언제든지 판매가 가능하다. 처음에는 주어진 매매가를 처음부터 차례대로 보면서 계산을 하려했지만 다음과 같이 주어..

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com S에서 시작해서 G까지 가는데 상하좌우 이동할 수 있다. 최소비용을 구하는 문제이다. 처음에는 bfs로 최소비용을 구하였지만, 지나온 경로를 체크하는 부분에서 의미가 없다고 생각해 풀지 못하였다. 이 문제는 최소 경로가 아니라 길을 돌아가더라도 최소비용을 구해야하는 것이다. 다음으로는 DP로 접근하였다. S에서 행 끝까지, 열 끝까지 누적합을 기준으로 dp를 진행하였다. 하지만 답이 틀려 다른 외부 사이트에서 영감을 얻었다. 단서는 bfs형태로 이동하면서 dp 형태로 푸는 것이다. bfs형태로 하면 지나온 경로를 체크해야하는데 이를 하지 않고 계속해서 최소비..

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 다음과 같이 입력이 주어질 경우 {123 1} 123을 1번 자리를 교환해 가장 큰 수를 만들어야 한다. 예시에서는 1과 3을 바꿔 321이 정답이다. {94 2} 일 경우 94 -> 49 -> 94 이다. 처음에는 단순히 백트래킹 기법으로 모든 자리를 교환해 그 중 가장 큰 수를 출력할려 했다. sol(st, change); //입력 받은 String 숫자배열, change는 교환할 수 있는 수 void sol(string s, int cnt) { if (cnt == 0) //cnt가 0이면 다 교환했다는 의미 이므로 최댓값을 갱신 { int temp = ..

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 위의 그림같이 건물 좌우 2칸씩 아무것도 없으면 view가 보인다. 위의 그림에서는 초록색으로 칠해진 곳이 view가 보이는 곳이다. 따라서 총 6개가 view가 보인다. A는 오른쪽으로 1칸때문에 안보이고 B도 마찬가지이다. C는 왼쪽으로 1칸때문에 안보인다. 맨 오른쪽, 왼쪽 2칸 씩은 건물의 높이가 0이다. 처음에는 스택과 큐로 접근 하였는데 계속 안풀려서 1시간 소비한 문제이다. 답지를 보면 정말 간단한것 을 알 수 있다. 일단 모든 건물의 높이를 다 배열에 담고 현재 인덱스로 부터 left(-2, -1), right(+1, +2) 인 곳을 찾아 둘 ..