본문 바로가기

백준

 (81)
5397)키로거 https://www.acmicpc.net/problem/5397 문제를 이해하기 위해 메모장을 열어서 확인해보자. 키로거가 abdata = c; oldNode->right = NULL; if (t == NULL && password == NULL) { password = oldNode; t = password; } else if(t == NULL && password != NULL){ oldNode->right = password; password->left = oldNode; password = oldNode; t = password; } else if (t->right != NULL) { oldNode->right = t->right; t->right->left = oldNode; oldNode->..
2846)오르막길 https://www.acmicpc.net/problem/2846 자질구레한 설명을 빼면 문제를 조금 더 쉽게 이해할 수 있다. 주어진 수열에서 증가하는 부분 수열을 찾고 부분 수열의 크기 중 최대인 것을 찾아야 한다. 부분 수열의 크기는 가장 마지막 항과 첫 째 항의 차로 얻은 값이다. 문제를 풀고 다른 사람의 풀이와 비교를 하니 뻘짓을 많이 했다. 부분 수열이 증가하는 지 알려면 이전 항의 크기와 현재 항의 크기를 비교해봐야 한다. curHeight - preHeight > 0 이면 연속하는 두 개 항이 증가한다고 할 수 있다. 이 경우 이전 항의 값 preHeight와 현재 항의 값 curHeight를 배열 ascend에 넣는다.위 그림처럼 부분 수열이 증가하는 경우 연속하는 항들을 ascend 배..
1929)소수 구하기 https://www.acmicpc.net/problem/1929 M이상 N이하 소수를 찾는 문제이다. 예전에는 isPrime() 함수로 소수를 찾았다. i를 2부터 하나씩 증가시켜 n에 도달하기 전에 n이 i로 나누어 떨어지면 소수가 아니다. 어떤 수가 소수인지 알려면 못해도 2부터 n까지 나누어 봐야 한다. 그래서 isPrime()은 시간이 많이 걸린다. 문제는 더 짧은 시간 내에 소수를 찾을 것을 요구해서 다른 방법을 찾아야 했다. 소수를 구하는 방법중 쉬운 방법이 에라토스테네스의 체이다. 그래서 에라토스테네스의 체를 공부했는데 다음과 같은 방법으로 소수를 찾는다. 우선 2부터~n까지 수를 준비한다. 2가 소수라면 2의 배수는 소수가 아니기 때문에 제거한다. 3이 소수라면 3의 배수는 소수가 아니기..
9020)골드바흐의 추측 https://www.acmicpc.net/problem/9020 골드바흐의 추측은 어떤 짝수가 두 개의 소수 합으로 나타낼 수 있다는 주장이다. 예를들어 4는 2와2의 합으로 표현될 수 있다. 16은 5와 11의 합으로 표현될 수 있다. 일단 짝수 n이 주어지면 2로 나누고 몫이 소수인지 확인한다. 몫이 소수가 아니면 n을 다른 소수합으로 표현하되 그 소수의 차이가 최소가 되게 해야한다. 간단한 아이디어로 해결할 수 있다.위 그림처럼 16은 2로 나눈 몫은 소수가 아니지만 두 수의 합은 16을 만든다. 왼쪽 수를 i라하고 오른 쪽 수를 j라할 때 i,j가 소수이면서 j-i가 0에 가깝게 만들면 된다. i를 1씩 감소시키면 합은 일정하게 유지되야하기 때문에 j는 1씩 커져야 한다. i가 감소하고 j가 증..
1436)영화감독 슘 https://www.acmicpc.net/problem/1436 이 문제를 풀면서 내가 문제를 푸는 방식이 어떤 유형인지 알게 됬다. 문제를 분석하다 보면 솔루션이 있을 법도 한데 도무지 찾기 힘들 때가 있다. 그래서 가능한 모든 값을 비교해 조건에 맞는 값인 경우를 찾는 때가 있다. 이런 방식으로 무차별적으로 모든 값들을 조건과 부합하는 지 확인하는 방식을 브루트 포스 코드라 하더라. 이 문제는 6이 연속해서 3번 이상 나타나는 수들을 크기 순으로 나열했을 때 n번째에 해당하는 항을 찾아야 한다. 나는 i를 666부터 1씩 증가시켜 하나씩 찾았다..ㅋㅋ 예를들어 i가 16661이면 오른쪽 끝부터 하나씩 잘라낸다. 잘라낸 수가 6이라면 그 수를 currentDigit에 저장하고 previousDigit..
1018)체스판 다시 칠하기 https://www.acmicpc.net/problem/1018 문제를 이해해보자. 우선 처음에 주어지는 나무판은 체스판처럼 체크 무늬가 교차해서 나타나지 않는다. 주어진 나무판에서 아무데서나 8x8 모양을 잘라낸 다음 잘라낸 나무판이 체스판 모양이 될 수 있도록 체크 무늬를 다시 칠할 것이다. 이때 다시 칠하는 횟수가 최소가 되는 값을 찾아야 한다. 예를 들어보자.나무판이 위처럼 엉망으로 주어질 수 있다. 여기서 8x8 이되게 나무판을 자르는 경우는 아래와 같다. 즉 빨강 사각형을 옮겨 가며 다시 칠해야 할 색의 수를 세어 그중에서 최소인 것을 찾으면 된다. 여기서 하나 더 고려할 것이 있다. 체스 무늬는 왼쪽 위 모서리에서 흰색으로 시작하는 패턴이 있고 검은색으로 시작하는 패턴이 있다.왼쪽 위 모서..
1463)1로 만들기 https://www.acmicpc.net/problem/1463 몇 번의 뻘 짓으로 이 문제를 풀 수 있었다. 10을 1로 만들기 위해 연산하는 방법은 여럿 있을 수 있다. 처음에 생각했던 방법인데 최소 횟수가 아니었다. 10->5->4->2->1 예제 입력에서 어떻게 3번의 연산으로 10을 1로 만들 수 있었을까? 친절하게도 힌트에 잘 나와있다. 10->9->3->1 이렇게 연산을 수행하면 최소의 횟수로 1을 만들 수 있다. 여기서 눈여겨 볼만한 점은 9를 최소의 연산으로 1을 만드는 방법도 10을 1로 만드는 방법과 크게 다르지 않다는 것이다. 3을 1로 만드는 방법도 위와 크게 다르지 않다. 그렇다면 역으로 생각해서 1부터 시작해 n까지 바닥부터 최소 연산 횟수를 구해가면 되지 않을까? n 미만의..
1874)스택 수열 https://www.acmicpc.net/problem/1874 스택 수열은 주어진 수열을 push, pop해서 얻을 수 있는 수열을 말한다. 다만 스택에 수열을 넣을 때는 오름차순으로 넣어야 한다. 예를들어 5이하의 자연수를 스택에 넣는다면 다음 그림처럼 1,2,3,4,5 순으로 넣어야 한다.위와 같은 순서로 임의대로 push 와 pop 통해 만들어진 수열이 스택 수열이다. 문제는 N이하의 자연수로 push와 pop연산으로 주어진 스택수열을 만들어 낼 수 있는가 판단하는 것이다. 어떻게 주어진 수열이 스택 수열인지 판단할 수 있을까? 우선 top과 스택 수열의 첫 수를 비교한 뒤 같지 않으면 그 수와 같아질 때까지 1~N에서 차례대로 push한다. 스택 수열의 첫수와 top이 같아지면 같아지면 그 값..

티스토리툴바