본문 바로가기

ALL

 (73)
백준 3190번: 뱀 백준 3190번: 뱀 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 요즘 알고리즘 푸는게 뜸해졌다. 게을러진거 같다. 다시 집중해서 공부해야 감을 잃지 않을 수 있다! 시뮬레이션 문제로 문제 이해를 하는데 조금 난해했다. 어렸을 때 뱀이 움직이면서 알맹이를..
백준 15736번: 청기 백기 백준 15736번: 청기 백기 15736번: 청기 백기 예제 입력 1의 경우 1, 2, 3번 깃발이 존재하고, 3명의 선수가 참가한다. 첫 번째 선수는 1의 배수의 번호를 가진 깃발을 뒤집는다. 초기에 청색이였던 깃발은 첫 번째 선수에 의해 모두 백기로 된다. 두 번째 선수는 2의 배수의 번호를 가진 깃발, 2번 깃발을 뒤집는다. 3개의 깃발은 백 청 백의 순서로 놓여있게 된다. 마지막 선수는 3의 배수의 번호를 가진 깃발, 3번 깃발을 뒤집는다. 마지막 깃발의 상태는 백 청 청이 되고, 따라서 백기의 수는 www.acmicpc.net 청기와 백기가 양면으로 있는 깃발이 놓여져있고, 선수들이 n번째 차례일때 n의 배수에 해당하는 깃발들을 뒤집는 게임을 하고 있다. 청기를 뒤집을 경우 백기, 백기를 뒤집을..
백준 1019번: 책 페이지 백준 1019번: 책 페이지 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 출력한다. www.acmicpc.net 근래 풀었던 문제중에 제일 어려웠던 것 같다. 도무지 풀 방법이 생각나지 않아 구글링을 했다, 와 이걸 어떻게 생각해내는 것일까 라는 생각이 들었다. 책의 페이지까지 나오는 모든 숫자의 개수를 구하는 1줄짜리 간단한 문제이지만 페이지의 범위가 10억까지여서 1부터 N까지 하나하나 계산하다 보면 1억 계산당 1초여서 10억이면 10초가 걸리게 되는 문제가 되어버린다. 그러니 여기서 규칙을 찾고 그 규칙을 코드화하면 된다. 규칙이란 것이 생각보다 어려운데 한번에 이해를 못해서 여러 글을 여러번 읽어봐야했다. 1부터 N까..
LCS 최장 공통 부분 수열 알고리즘 LCS(Longest Common Subsequence) 알고리즘은 두 문자열의 최장 공통부분 문자열을 구하는 알고리즘이다. 문자열 ABCD와 문자열 BCDE가 있으면 이 두 문자열 사이에서 공통으로 갖는 부분 수열인 BCD를 찾는 것이다. LCS의 함수 식은 두 문자열을 한 글자씩 비교하면서 같은 글자일 때 이전 글자 비교에서 찾은 부분 문자열 길이에 +1을 하고, 그러지 않을 경우에는 바로 이전 문자열 길이와, 이전 글자가 현재와 같은 글자에서의 최장 부분 문자열 길이 중 최댓값을 선택하는 것이다. 시간 복잡도는 비교하는 각 문자열의 크기 M과 N만큼 비교를 하기 때문에 O(MN)의 시간 복잡도를 갖는다. 그렇다면 예시로 두 문자열의 LCS를 구해보도록 하자 문자열 ACAYKP과 문자열 CAPCAK의..
백준 2096번: 내려가기 백준 2096번: 내려가기 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 메모리가 4MB이므로 변수의 크기를 최소화 해야한다. dp를 선언할 때 max와 min을 저장하는 것을 따로 설정하고 N만큼 반복하면서 max와 min일 때 모든 경우의 값을 저장하면은 해결이된다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; int score[3]; int ..
백준 10164번: 격자상의 경로 백준 10164번: 격자상의 경로 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다. www.acmicpc.net 가장 좌측 상단에서 가장 우측 하단으로 내려올 때 O를 거쳐온 곳의 경로의 수를 구하는 문제이다. 문제를 하나 이해를 제대로 하지 않아 틀렸던 문제이다. 나는 O가 없는 경우에는 가는 방법이 없다고 착각을 했었다. O가 없는 경우에는 모든 경로의 수가 정답이다. 나는 보자..
백준 2631번: 줄세우기 백준 2631번: 줄세우기 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 www.acmicpc.net 문제를 풀다보면 풀지못하는 문제도 있는 법인데 나중에 확인해보니 초등부, 중등부 문제인 것을 알았을 때, 나는 얼마나 걸음마 단계인지 실감하게된다. 이 문제도 풀지못하고 답을 봤..
백준 15664번: N과 M (10) 백준 15664번: N과 M (10) 15664번: N과 M (10) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net N과 M (9)를 풀었다면 10은 금방 풀 수 있다고 하는데 나는 (9)를 푼지 2달이 넘어서 기억이 잘 나지 않았다. 아무튼 기억을 되살려보고자 이것저것 하다가 9보다 더 간단하게 풀게되었다. 코드도 기존 N과 M시리즈에서 몇줄 추가되지 않았다. 이전에 삽입했던 값을 기억하는 prev 변수를 만들었고, 만일 다음에 들어가야하는 수가 prev값과 같다면 그 수는 생략. 비내림차순으로 정렬된 상태로 답을 출력하기 때..

티스토리툴바