https://www.acmicpc.net/problem/1695 1695번: 팰린드롬 만들기 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열 www.acmicpc.net 간단한 dp 문제였지만 아이디어 떠올리기는 좀 힘들었습니다 dp[i][j] : i ~ j까지 부분 배열에 팰린드롬을 만들기 위해 필요한 최소 개수라 하면 입력된 배열을 arr 이라 할 때 arr[i] = arr[j] 이면 i, j 번쨰 값이 같으므로 i+1, j-1 번째까지 배열로 팰린드롬을 만드는데 필요한 개수와 같습니다. 그리고 arr[..
https://www.acmicpc.net/problem/3108 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net (중간에 i, j 잘못 가져와서 맞왜틀을 몇 번이나 했는지 모르겠다.... i랑 j 같이 햇갈리게 생긴 애들 주의하기....) 문제 예제를 몇 개 그려보면 결국 분리된 직사각형이 몇 개나 있는지를 찾는 것입니다. (같은 곳도 여러 번 지나갈 수 있으므로) 예를 들어, (1,1), (4,4) / (2,2), (5,5) 를 꼭지점으로 갖는 직사각형은 (2,4), (4,2) 라는 공통 부분을 통해 이어서 그릴 수 ..
https://www.acmicpc.net/problem/15718 15718번: 돌아온 떡파이어 각 테스트 케이스마다 한 줄에 하나씩 나이를 먹는 방법의 가짓 수를 100007로 나눈 나머지를 출력하시오. 100007은 일반적이지 않은 나눗수임에 유의하라. www.acmicpc.net 예외 사항이 생각보다 좀 있어서 몇 번 틀렸습니다. 문제를 해석해보면 M째 날에 N세로 생을 마감한다고 하였고, 0개를 먹을 때 죽으므로, M-1일 째까지는 1 이상의 값을 가지고, 합이 N이 되는 경우의 수를 구하면 됩니다. 즉, x1 + x2 + ... + x(m-1) = n , xi >= 1 인 경우의 수를 구하는 것이고, 이것은 고등학교 수학을 잘 떠올려보면 중복조합의 개수를 구하는 것과 동일합니다. 그렇기 때문에..
https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 주어진 A, B에 대해 같은 수끼리 이었을 때 교차점이 몇 개인지를 구하는 문제입니다. 예전에 풀었던 문제와 비슷하여 동일한 방식으로 풀었습니다. https://ghqls0210.tistory.com/152 백준 / 1517 버블 소트 C++ www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 ..
https://www.acmicpc.net/problem/2957 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net 오랜만에 조금 높은 티어 문제를 풀었습니다. (사실 예전에 틀린 것... 뭔가 최악의 케이스에 걸려 시간초과가 떴었을 듯하다....) 문제에서 구하고자 하는 C 값은 사실 이진트리에서 루트부터 몇 개의 노드를 카운트하는 지를 구하는 문제입니다. 단 카운트 수가 누적됨에 주의합니다. 문제를 다 풀고 좀 찾아보니 단순 이진 탐색을 이용한 방법 외에 유니온 파인드를 이용해서도 풀 수 있음을 알게 ..