본문 바로가기

Problem Solving/Python

 (5)
[BOJ] 17299 오등큰수 https://www.acmicpc.net/problem/17299  한 수열이 주어졌을 때, 각 원소에 대하여, 해당 원소보다 등장빈도가 높은 숫자 중 오른쪽 방향으로 가장 가까이에 있는 숫자를 구하는 문제.  1/ 조건1) 수열의 크기는 1 이상 100만 이하다.2) 각 원소의 크기는 1 이상 100만 이하다.3) 시간 제한은 1초, 메모리 제한은 512MB.  2/ 설계일단 메모리가 충분하므로 100만+1의 크기를 갖는 배열을 만들어서 등장빈도를 기록해야겠다고 생각했다. 그렇게 해야 O(1)으로 각 등장빈도를 호출할 수 있을 테니.가장 간단한 방식은 각 원소보다 큰 인덱스를 탐색하며 등장빈도가 높은 원소를 만나면 break를 하는 것인데, 최악의 경우(예를 들어 모든 원소가 한 번만 등장할 경우) ..
[BOJ] 1695 팰린드롬 만들기 https://www.acmicpc.net/problem/1695  한 수열이 주어졌을 때, 주어진 수열을 팰린드롬(palindrome, 회문)으로 만들기 위해 추가해야 하는 숫자의 최소 개수를 구하는 문제.  1/ 조건1) 첫째 줄에 수열의 길이 n이 주어진다. 1 2) 수열을 이루는 숫자 n개가 주어진다. 각 숫자는 -2^31 이상 2^31 미만이다.  2/ 설계숫자를 어떤 식으로 추가해야 짝을 맞출 수 있을까에 대해 고민하다가 숫자를 추가하는 것과 제거하는 것이 동등하다는 사실을 깨달았다. 재귀적으로 하나씩 제거한 결과가 회문인지를 검사하려고 했는데, 그 과정에서 중복된 결과가 얻어졌다. DP 문제라고 생각했다.일단 top-down으로 풀어봤는데 메모리 초과가 났다. 재귀 횟수도 문제지만 메모이제이..
[BOJ] 1799 비숍 https://www.acmicpc.net/problem/1799 주어진 체스판 위에서 비숍을 최대 몇 개까지 둘 수 있는지 세는 문제.  1/ 조건1) 입력 첫 줄에는 정사각형 체스판의 크기 n이 주어진다. 1 2) n*n 행렬이 주어진다. 각 원소가 1이면 해당 위치에는 비숍을 둘 수 있고, 0이라면 둘 수 없다.  2/ 설계당연하게도 바로 DFS를 썼다. 정확히는 백트래킹. 가지치기를 생각할 수 있는 데까지 해봤지만 n=10에서 모든 칸에 비숍을 둘 수 있는 경우를 해결하긴 어려웠다.나는 'n이 정해지면 비숍의 최대치가 정해지는가?'라는 질문에 대해 생각했다. 답은 2n-2. 엄밀한 증명을 통해 얻어낸 것은 아니지만 확신은 있었다.대략적인 추론 과정은 이렇다. n*n 행렬에 존재할 수 있는 대각선은..
[BOJ] 5525 IOIOI https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 1/ 조건 1) P_N은 I로 시작하여 I와 O가 번갈아가며 나오며 2N+1의 길이를 갖는 문자열이다. 2) I와 O로만 이루어진 문자열 S와 정수 N이 이주어졌을 때, S 안에 P_N이 몇 개 포함되어 있는지 구해야 한다. 2/ 설계 시간 제한에 대한 감이 오지 않았다. 일단 순회를 반복하는 방식으로 풀어보고자 했다. 구체적으로..
[BOJ] 17070 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 주어진 지형 위에서 파이프를 목적지로 옮길 수 있는 가짓수를 세는 문제. 1/ 조건 1) 파이프는 연속된 2칸을 차지하며, (1, 1)과 (1, 2)에 가로로 놓여 있는 채로 시작한다. 2) 파이프를 (n, n)으로 밀어서 옮겨야 한다. 3) 파이프는 회전시킬 수 있는데, 가능한 방향은 x축을 기준으로 시계방향 0도, 45도, 90도이다. 4) 지형은 0과 1로 주어지는데..

티스토리툴바