Kakao Blind 2022 - 파괴되지 않은 건물 Level Ⅲ Kakao Blind 2022 - 파괴되지 않은 건물 문제 2차원 배열에서 특정 구간에 덧셈, 뺄셈을 진행하고 이를 효율적으로 시간 단축하는 문제입니다. 입력 출력 단순히 더하고 빼는 연산을 에 해결하더라도 정확도는 쉽게 100% 맞출 수 있습니다. 하지만, 이 문제는 효율성 문제로 시간 복잡도를 줄여야 합니다. 🍺 How to Solve? 🔥 Key Point 어떻게 하면 구간에 대해서 더하고, 빼는 연산을 매번 하지 않고 한 번에 할 수 있을까?? 🎯 2차원 배열에서 누적합을 이용한다. 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 위 상황에서 (3,3) 부터 (5,5) 까지 -4 만큼 적용한다면? 모든 구간에 적용할 필요 없이 각 사각형의 오른쪽 아래 끝 좌표에만 기록을 한다면 (0,0) 부터 해당 구간까지에는 x만큼 적용하겠다는 의…

BOJ 2632 - 피자 판매 Gold Ⅱ BOJ 2632 - 피자 판매 문제 고객이 두 종류의 피자 A와 B를 취급하는 피자가게에서 피자를 주문하고자 한다. <그림 1>과 같이 각 종류의 피자는 다양한 크기의 여러 개의 피자조각으로 나누어져 있다. 각 조각에 쓰여진 숫자는 피자조각의 크기를 나타낸다. 그림1 고객이 원하는 피자의 크기를 이야기하면, 피자가게에서는 한 종류의 피자를 2 조각 이상 판매할 때는 반드시 연속된 조각들을 잘라서 판매한다. 이때 판매한 피자조각의 크기 합이 주문한 크기가 되어야 한다. 판매한 피자조각은 모두 A종류이거나, 모두 B종류이거나, 또는 A와 B 종류가 혼합될 수 있다. 예를 들어서, <그림 1> 과 같이 잘라진 피자가 있을 때, 손님이 전체 크기가 7 인 피자를 주문하면, 피자 가게에서는 <그림2>와 같이 5 가지 방법으로 피자를 판매할 수 있다. 그림2 피자가게에서 손님이 원하는 크기의 피자를 판매하는 모든 방법의 가지 수를 계산하는 프로…

BOJ 1102 - 발전소 Gold-Ⅰ 이 문제는 BOJ 문제입니다. 문제 출처 : 발전소 💥 문제 은진이는 발전소에서 근무한다. 은진이가 회사에서 잠깐 잘 때마다, 몇몇 발전소가 고장이난다. 게다가, 지금 은진이의 보스 형택이가 은진이의 사무실로 걸어오고 있다. 만약 은진이가 형택이가 들어오기 전까지 발전소를 고쳐놓지 못한다면, 은진이는 해고당할 것이다. 발전소를 고치는 방법은 간단하다. 고장나지 않은 발전소를 이용해서 고장난 발전소를 재시작하면 된다. 하지만, 이때 비용이 발생한다. 이 비용은 어떤 발전소에서 어떤 발전소를 재시작하느냐에 따라 다르다. 적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고치는 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 발전소의 개수 N이 주어진다. N은 16보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 발전소 i를 이용해서 발전소 j를 재시작할 때 드는 비용이 주어진다. i줄의 j번째 값이 그 값…

SWEA 4699 - 콩순이의 가장 싼 팰린드롬 D-Ⅳ 이 문제는 SWEA 문제입니다. 문제 출처 : 콩순이의 가장 싼 팰린드롬 Palindrome 이란? 팰린드롬이란 문자열, DP 문제에서 종종 접할 수 있는 문제이다. 팰린드롬을 가장 쉽게 표현하자면 거꾸로 해도 똑같은 문자라고 할 수 있다. 예를 들어, ABBA 와 같이 거꾸로 해도 똑같은 문자를 의미한다. How to Solve? 처음에는 문자를 제거하고 삽입하는 모든 경우를 탐색하면서 팰린드롬이 완성됐다면 Cost 값을 저장해두고 해당 Cost보다 큰 경우는 바로 탐색 종료하는 방식의 BackTracking 방식으로 구현했다. 하지만 이 문제의 Stack 메모리 제한이 있기에 재귀로 해결하기 어렵다. 따라서 다른 방식의 접근이 필요하다. 앞서 Palindrome을 설명하면서 DP에서 자주 나온다고 설명했다. 따라서 이 문제에서도 DP를 활용한 접근 방법을 알아본다. 🔥 DP 핵심은 가장 인접한 두 글자부터 팰린…

SWEA 10805 - 야바위 D-Ⅳ 이 문제는 SW Expert Academy 문제입니다. SWEA 10805 - 야바위 문제 동호는 공과 N개의 컵을 가지고 야바위를 하고 있다. N개의 컵은 모두 구별이 가능하고, 일렬로 늘어서 있다. 처음에 왼쪽에서 첫 번째 컵에 공을 넣어놓는다. 그리고 앞으로 Q번 두 컵의 위치를 바꾸는데, i번째에는 왼쪽에서 Ai번째 컵과 왼쪽에서 Bi번째 컵의 위치를 바꾼다. 동호는 공이 어떤 컵에 있는지 맞출 수 없도록 하기 위해 정확히 한 번 속임수를 쓰려고 한다. 속임수는 현재 공이 들어있는 컵이 왼쪽에서 i번째 컵이라고 할 때, 왼쪽에서 i-1번째 컵이나 왼쪽에서 i+1번째 컵으로 공을 순간 이동시키는 것이다. 이 속임수는 컵을 섞는 도중이 아니라면, 어떤 시점에도 가능하다. 입력 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수 N,Q (1 ≤ N, Q ≤ 105)가 공백 하나로 구분되어 주…