본문 바로가기

분류 전체보기

 (265)
백준9372 - 상근이의 여행 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 문제 상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다. 이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 도시들을 여행할 수 있도록 도와주자. 상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다. 입력 첫 번째 줄에는 테스트 케 www.acmicpc.net 풀고 나니까 되게 허탈한 문제였다. 나는 BFS로 구현해서 풀었다. 현재 노드에서 다른 노드로 왕복 가능한 비행기들이 주어지고 출발점..
백준9019 - DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경 www.acmicpc.net 단순 BFS 문제였다. 현재 있는 경로에서 숫자들을 하나씩 탐색한 결과를 저장해두다가 내가 찾는 숫자가 나오면 종료하면 된다. BFS를 ..
백준1669 - 멍멍이 쓰다듬기 https://www.acmicpc.net/problem/1669 1669번: 멍멍이 쓰다듬기 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍멍이보다 키가 작기 때문에 멍멍이를 쓰다듬어줄 수 없다. 원숭이가 멍멍이를 쓰다듬으려면 둘의 키가 같아야 하기 때문이다. 그래서 원숭이는 그 날부터 자신의 키를 조절하기로 마음먹었다. 원숭이는 초능력자이기 때문에 마음대로 키를 늘릴 수 있다. 하지만 안타깝게도 사람이 아니라 www.acmicpc.net 수열을 찾아푸는 문제다. 다음과 같은 규칙이 나온다. 시작과 끝은 무조건 1로 고정이 된다. 나머지 부분은 직전 수에서 1을 증가..
백준1309 - 동물원 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이가 되게 짧아서 허탈한 문제였다. 점화식이 간단하니 스스로 세워서 풀어보도록 하자 #include using namespace std; int mat[100001]; int main() { int n; cin >> n; /* 3 7 17 = 7 * 2 + 3 41 = 17 * 2 + 7 . . . 따라서 점화식은 : a(n) = 2 X a(n - 1) + a(n - 2), a(1) = 3, a(2) = 7, (n >= 3) */ mat[1] = 3; mat[2] = 7; for (int i = 3; i
백준1544 - 사이클 단어 https://www.acmicpc.net/problem/1544 1544번: 사이클 단어 첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 단어가 한 줄에 하나씩 주어진다. 단어는 영어 소문자로만 이루어져 있다. N은 50보다 작거나 같은 자연수이며, 단어의 길이는 최대 50이다. www.acmicpc.net 방문처리 여부로 풀었다. 원소들이 같은 단어이면 true, 다른 단어이면 false로 방문 여부를 표시한 뒤 현재 원소가 과거에 같은 원소였었던 경우는 탐색을 하지 않고 과거에 같은 적이 없던 단어면 현재 위치에서 탐색하여 총 몇 종류의 단어가 존재하는지 센 문제다. #include #include #include #include using namespace std; bool compare(st..
백준1965 - 상자넣기 https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 www.acmicpc.net 동적 계획법을 사용한 문제다. 전에 내가 풀어봣던 동적 계획법과 다른 점이 있던 문제다. 전에 있던 동적 계획법들은 과정이 진행될 수록 ..
백준2493 - 탑 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다. www.acmicpc.net 스택을 활용하여 푼 문제다. 스택을 사용하면 확실히 O(n)시간으로 알고리즘을 만들 수 있어서 편리하다. 나는 우선 입력받은 숫자를 리버스하여 생각하였다. 그 다음 스택에 숫자를 넣기 전에 현재 넣을 수보다 작은 수가 있는지 찾는다. 있다면 현재 넣을 숫자의 인덱스를 답으로 넣어준다. 그 다음 스택에 현재 넣을 수를 넣는다. 결과로 나온 답은 리버스한..
백준9935 - 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 www.acmicpc.net 문자열을 이용하여 푼 문제다. 시간 초과가 많이 났는데 이유는 string의 함수들의 시간 복잡도를 계산하지 못한 것이 이유였다. 처..

티스토리툴바