본문 바로가기

전체 글

 (191)
블로그( BOJ 16157 ) 16157. 블로그 : https://www.acmicpc.net/problem/16157 16157번: 블로그 neighbor 블로그를 운영하는 디디는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 스스로 해결한 경우 파란색, 도움을 받아 해결한 경우 초록 www.acmicpc.net 문제 파악하기 블로그에 올린 문제는 3가지 색깔(R, G, B)로 칠하게 됩니다. 연속된 문제들은 한번에 같은 색깔로 색을 칠할 수 있습니다. 문제들을 각각 원하는 색깔로 칠하기 위해서는 최소 몇 번의 색칠 작업이 필요할 지 구해야 합니다. 그렇다면 그리디 알고리즘을 사용하면 문제를 풀 수 있을까요? 문제 해결하기 아쉽게도 그리디 알고리즘으로는 최적값을 찾는데 무리가 있습..
248 게임( BOJ 12031 ) 12031. 248 게임 : https://www.acmicpc.net/problem/12013 12013번: 248 게임 이 예에서, Bessie는 두 번째와 세 번째에 있는 1을 2로 합친다. (1 2 2) 두 번째와 세 번째에 있는 2를 3으로 합친다. (1 3) 첫 번째와 두 번째 1을 합치는 것은 최적해가 아님을 주의해라. www.acmicpc.net 문제 파악하기 인접한 숫자 중 값이 같은 숫자끼리 합칠 수 있으며, 합치면 그 값보다 1 큰 수 한개로 바꿀 수 있습니다. 게임을 진행하면서 만들 수 있는 가장 큰 숫자를 구해야 합니다. 인접한 숫자만 합칠 수 있기 때문에 구간에 따른 어떤 값을 구하면 문제를 해결할 수 있을 듯 합니다. 문제 해결하기 숫자들은 합치는 순서에 따라 만들어지는 최댓값..
크리스마스 트리 꾸미기( BOJ 16468 ) 16468. 크리스마스 트리 꾸미기 : https://www.acmicpc.net/problem/16468 16468번: 크리스마스 트리 꾸미기 이진트리란 각각의 노드가 최대 두개의 자식 노드를 가지는 트리 자료구조로, 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드가 있다. 제일 위에 노드가 1개, 그 다음 2개… 와 같은 식으로 위에 www.acmicpc.net 문제 파악하기 N개의 볼을 사용해 L 높이의 트리를 만드는 방법의 수를 구해야 합니다. 트리는 이진 트리 모양으로 구성되기에 N개의 볼이 있다면 (N-1)개의 볼을 왼쪽/오른쪽 자식으로 나눌 수 있습니다. (왼쪽 자식 수, 오른쪽 자식 수) 라고 표현한다면 N개의 볼은 (0, N-1) ~ (N-1, 0) 까지 총 (N-1)가지 경우의 수로 나..
모빌 이진수( BOJ 2471 ) 2471. 모빌 이진수 : https://www.acmicpc.net/problem/2471 2471번: 모빌 이진수 첫째 줄에는 0, 1과 괄호들로 구성된 모빌의 상태 표현이 주어진다. 모빌의 상태 표현은 빈칸 없이 이어진 문자열로 주어진다. 주어지는 0, 1과 괄호들의 총 개수는 200개 이하이다. 둘째 줄에는 K www.acmicpc.net 문제 파악하기 0과 1로 이루어진 이진수가 주어집니다. 괄호 안의 값은 회전할 수 있으며, 회전 시 괄호 안의 숫자들은 뒤집히게 됩니다. 주어진 이진수로 만들 숫자 중 K번째 숫자를 찾아야 합니다. 입력되는 숫자와 괄호의 길이는 최대 200개이기 때문에 문자열로 입력을 받아야 합니다. 메모리의 제한 때문에 만들 수 있는 모든 문자열을 저장할 수는 없습니다. 그럼..
Visiting Cows( BOJ 5934 ) 5934. Visiting Cows : https://www.acmicpc.net/problem/5934 5934번: Visiting Cows After many weeks of hard work, Bessie is finally getting a vacation! Being the most social cow in the herd, she wishes to visit her N (1
Manacher's Algorithm 일반적으로 문자열 속에서 팰린드롬(회문)을 찾는 알고리즘은 다음과 같이 O(n2)의 시간복잡도를 가지고 있습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include #define NMAX 35 int len, cnt; char inp[NMAX]; bool check(int l, int r) { while(l> 자신이 속한 팰린드롬 안에서 대칭점이 가진 팰린드롬의 반지름 구하기 if(i =0 and i+m[i]+1
양팔 저울( BOJ 1653 ) 문제 1653. 양팔 저울 : https://www.acmicpc.net/problem/1653 1653번: 양팔 저울 무게가 서로 다른 추들의 집합이 주어진다. 각 추의 무게는 1g 이상 9g 이하의 정수이다. 이 추들 중에서 몇 개를 선택하여 양팔저울에 올려서 평형을 만들고자 한다. 양팔저울에는 양쪽에 5개씩 www.acmicpc.net 문제 파악하기 추는 1g, 2g, ... , 9g까지 최대 9개가 있습니다. 양팔 저울에는 눈금이 5개씩 있으며, 평형을 이루게 만드는 추의 배치를 '평형정수'로 표현할 수 있으며, K번째 평형정수를 찾아야 합니다. 단순히 첫 번째 위치부터 추를 하나씩 놓으면 시간초과에 걸릴 수 있습니다. 어떤 방법으로 탐색을 해야 할까요? 문제 해결하기 추를 놓은 위치는 00001..
금고 (SAFE) ( BOJ 14932 ) 문제 14932. 금고 (SAFE) : https://www.acmicpc.net/problem/14932 14932번: 금고 (SAFE) 제연이는 멘사 회원이 되고 싶어 멘사 수학 퀴즈를 살펴보던 중 흥미로운 사실을 발견하게 된다. 바로 멘사 회원들은 평범한 금고를 쓰지 않고 오른쪽 그림과 같은 금고를 사용한다는 점이다! www.acmicpc.net 문제 파악하기 N*N 행렬로 금고가 주어집니다. 금고는 버튼으로 구성되어 있으며, 모든 버튼을 누를 수 있는 위치를 찾아야 합니다. 모든 버튼은 항상 하나의 버튼만을 가리킵니다. 따라서 버튼 사이의 관계를 그래프로 나타낼 수 있습니다. 출력되는 결과는 총 3가지 입니다. 좌표를 출력하거나, "THIEF LOVE IT!"을 출력하거나 "TOO SAFE"를 출..

티스토리툴바