알고리즘 부수기

C번) 문제 링크 : http://codeforces.com/contest/1095/problem/C 문제의 입력으로는 n과 k가 주어진다. 쉽게 설명해서 주어진 숫자 n을 k개의 2의 거듭제곱의 합으로 나누는 것이다. 사용한 방법은 우선 k와 상관없이 필요한 최소한의 개수를 구하는 것이다. ex) n=9, k=4라고 하자. 이 때, 필요한 최소한의 개수는 1과 8 즉, 2개이다. 최소한의 개수가 구해졌다는 것은 2의 거듭제곱 형태로 나타낼 수 있다는 것이다. 이 형태는 2진수의 형태에서 1인 값들과 동일하다. 여기까지만 생각하고 바로 YES를 출력해서는 안된다. 문제에서 요구하는 YES/NO의 조건은 2의 거듭제곱의 합 형태로 나타낼 수 있느냐가 아닌 k개의 2의 거듭제곱의 합으로 나타낼 수 있느냐이다..

문제링크 : https://www.acmicpc.net/problem/3111 먼저 결과만 말하자면 이 문제는 내 힘으로 풀지 못했다. 그래서 잘못 생각한 점, 도움을 받은 방법을 적으려고 한다. 이 문제의 설명은 간단하다. A, T라는 2개의 문자열이 주어지고1. T에 A가 없으면 알고리즘을 종료한다.2. T에서 처음 등장하는 A를 찾은 뒤, 삭제한다.3. T에 A가 없으면 알고리즘을 종료한다.4. T에서 마지막으로 등장하는 A를 찾은 뒤, 삭제한다.5. 1번으로 돌아간다. 이 문제를 보고 시도한 방식은 문제에서 주어진 것과 같다. 1. 문제에서 주어지는 방식대로 T의 맨 앞부터 A가 나올 때까지 탐색을 하고,2. A가 나올 경우 index를 A의 길이만큼 더한다. ( 새롭게 만들어진 문자열에 추가하지..

문제 링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWDTN0cKr1oDFAWD 간선을 지나는 비용은 1로 동일하다. 이 때, 여러 개의 중간 지점을 순서대로 지나는 경로의 최솟값을 구하는 문제이다. 우선, 대각선의 길을 제외하고 보자. 모든 간선의 비용이 1이므로 최솟값은 x값의 차이 + y값의 차이 이다. 이 상황을 Case 1이라고 한다. 이제 남은 부분은 대각선이 추가되는 경우이다. Case 1에서 대각선을 추가해보면 아래와 같다. 위 상황에서 대각선을 이용해서 비용을 줄일 수 있는 경우는 어떤 경우가 있을까? 1. x와 y의 값이 +1 +1인 경우 ( 둘 다 증가하는 경우 )2. x와 y..

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWxqfhKAWgDFAW4&categoryId=AWWxqfhKAWgDFAW4&categoryType=CODE 이 문제의 핵심은 간단하다. 우선, 개구리가 몇 번을 울 수 있다는 제한이 없다. 개구리는 몇 번이고 울 수 있다. 하지만 'c' 'r' 'o' 'a' 'k' 의 문자를 순서대로 말해야 한다. 즉, 한 개구리가 5글자를 말하기 전에 울음소리가 시작된다면 이는 최소 2마리가 필요하다는 뜻이 된다. 문제 정의 및 해결방법을 떠나서 가장 먼저 고민했던 부분은 입력이 들어오는 형태이다. 입력을 잘 살펴보면, 한 테스트케이스에 몇 개의 문자가 들어..

문제 링크 : https://codeforces.com/contest/1080/problem/C 사실 문제는 많이 어렵지 않았다. 결과 개수만 long long으로 하고 좌표를 long long으로 선언하지 않아서 계속 맞왜틀을 시전한 문제. 문제에 대한 자세한 내용은 링크를 통해 확인하기로 하고 해결한 방법은 다음과 같다. 우선, black과 white의 개수가 있다. 이 때, white의 개수는 무조건 전체 개수 - black 개수이다. 그러므로 black만 따져주도록 하자. 흰색 잉크를 쏟고 그 다음 검정색 잉크를 쏟는 순서이다. - 먼저 원래 black이었던 칸의 개수를 구해준다.( 1,1이 w이므로 무조건 전체 칸 개수 / 2 ) - 다음은 흰색을 쏟은 상황이다. 흰색에 흰색을 쏟은 경우는 개수..

https://codeforces.com/ Codeforces에는 각 유저마다 Rating이 존재한다. 그리고 이 Rating은 Codeforces에서 시행하는 Round들을 통해 올릴 수 있다. 매번 메일이 오는데 전부 무시하다가 처음으로 참여를 해봤다. 참여한 라운드는 Codeforces Round #524 (Div.2) 문제수는 총 6문제였고 뒤로 갈수록 난이도도 올라가고 점수도 많이 주는 구조. 몰랐는데 Div.1은 첫 문제가 Div.2의 3번째 문제 수준이고 일정 Rating 이상만 참여할 수 있다고 한다. 그렇게 참여한 첫 Round 6문제 중에 3문제를 통과했고 뒤의 문제는 건들지도 못했다.. 다시 한번 부족함을 느낀 계기가 되었다. 제일 오른쪽의 +-숫자는 Rating의 변화를 의미하는데 ..

문제 링크 : https://www.acmicpc.net/problem/16510 cin / cout의 입출력 속도를 높이지 않고 풀었을 때 시간초과가 났던 문제이다. 먼저 일의 개수인 N이 주어진다. 매번 일을 수행할 때 앞에서부터 수행해서 시간안에 할 수 있는 일의 개수를 물어보는 문제이기 때문에 N을 입력받으면서 누적합을 하여 값을 저장해야한다. 단순히 값을 저장할 경우 매번 앞에서부터 합하며 결과를 확인해야하기 때문이다. 다음 과제는 주어진 일의 시간이 어느 구간에 들어가는지를 확인하는 것이다. 일할 수 있는 시간이 충분히 작다면 최대크기의 배열을 생성해서 N을 받으면서 값을 늘려가는 방법으로 들어온 시간을 인덱스로 하여 확인할 수 있지만 시간, 즉 T의 범위가 2*10^9이다. 배열로 만들기에는..

문제 링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWbrg9uabZsDFAWQ&categoryId=AWbrg9uabZsDFAWQ&categoryType=CODE 2048 게임을 몇 번만에 풀수 있는지 혹은 풀 수 있는지 없는지를 물어보는 문제가 아닌 단순히 주어지는 방향으로 한 번 시행했을 때의 결과를 출력하는 문제이다. 기본적인 방법은 UP의 경우 위에서부터 아래로 내려가면서, DOWN의 경우 아래에서 위로 올라가면서 확인을 한다. 우선, 방향이 문자열로 들어온다. 생각한 방법은 2가지이다. 1. 문자열 그대로 받은 후 strcmp를 통한 비교 2. up / left / right / down..