회문 회문 문제 회문 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseud...

패스 패스 문제 N명의 사람들이 원형으로 앉아있고, i번째 오른쪽 사람은 i+1번째, N번째 사람 오른쪽엔 1번째가 앉는다. 1번이 처음에 공을 가지고 있고, 둘러앉은 사람 가운데에는 1~N의 카드가 있다. 둘러앉은 사람들은 다음과 같은 게임을 N차례 진행했다. 공을 가진 사람이 나와서 카드 한 장을 뽑은 다음 자기 자리로 돌아간다. ...

직사각형 && 약 팔기 직사각형 약 팔기 문제 풀이 날먹문제집? 시리즈에 있어서 넌센스 겸으로 풀어봤다. 애드 훅이지만 다행히도 풀이가 간단하게 생각나서 쉽게 푼 것 같다. 이제 붙어 있는 값을 더해서 1~1000000 까지의 숫자를 만들 수 있으면 된다. 처음에는 2진수로 1 2 4 1 2 4 8 … 이런식으로 하면 되지 않...

빙고 빙고 문제 구데기컵에 나온 빙고를 푸는 문제이다. 풀이 재밌어 보이고 티어도 높아서 1시간 동안 열심히 풀었는데 점수를 안 준다고 한다. ㅠ 그래도 푸는 과정이 퍼즐 푸는 것 같아서 재밌었다. 우선 C3는 반드시 참이다. 색칠되지 않으면 모순이 생기기 때문이다. B1이 참이 아니라면 빙고줄의 일부지만 체크가 되면 안되므로 모순이 ...

학부 연구생 민상 새벽까지 계속 고치고 고쳐봐도 문제가 풀리지 않는다. 문제는 빡구현이라고 할 수 있는 귀찮은 dfs? 문제라고 생각했고 어쨌든 구현은 다 했다. 그런데 59%에서 시간 초과도 아니고 자꾸 메모리 초과가 발생한다. 처음에는 배열 index를 넘어간다거나 그런게 있나? 하고 찾아봤는데 아무것도 없다. 문제 제한을 봐도 메모리 ...

백준 문제를 푸는데, 분명 로직이 맞는 것 같은데 안되는 경우가 있다. int ma=-1; for(int i=1;i<=n;i++){ if(ma < graph[i].size()){ ma = graph[i].size(); save = i; } } 이런 코드...

경비병 세우기 게임 경비병 세우기 게임 문제 Yuto 와 Platina가 보초 세우기 게임이라는 새로운 게임을 해보려고 한다. 이 게임은 N × M의 가로가 긴 격자판에서 진행된다. 게임은 항상 Yuto부터 시작하며, 둘은 번갈아 가면서 자신의 턴에 원하는 빈 위치에 경비병을 세운다. 이 게임에서 ‘안전상태’라는 것은 격자판 안에 완벽히 포함되는...

최솟값 찾기 최솟값 찾기 문제 N개의 수 A1, A2, …, AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. 입력 첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000) 둘째 줄에는 N...

소트 소트 문제 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. 입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 N개의 수가 주어진다. N개의 수는 1,000보...

동전 뒤집기 동전 뒤집기 풀이 비트 마스킹 문제인데 아직 어색하다. 우선 아이디어 1. 같은 자리를 두 번 이상 뒤집는 것은 아무런 의미가 없다. 그렇기에 모든 가로에 대해 뒤집는 경우 2^20을 해보고, 세로에 대해 그리디하게 뒤집으면 된다. 그러면 시간 복잡도는 2^n * n^2이니까 충분히 해결이 가능하다. 계속 시간 초과가 나서 다...