노는 게 제일 좋아

이 문제 또한.. DP로 즉, 이전 결과가 다음 결과에 쓰이는 문제라고 볼 수 있다. 추가 시간이 없다는 말은 언어마다 추가시간이 없다는 말 같다. C++은 항상 기준이 되므로 시간제한에 추가시간이 있을까 없을까 고민안해도 된다. 시간 초과나면 잘못푼거다 ㅎ https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 맞는 풀이 #include using namespace std; int num[11]; int main(){ int n; cin >> n; num[1] = 1; num[2] = 2; num[3] = 4; //왜 이렇게 되는가? // 4를 만..

흠... 나는 처음에 BFS로 풀었는데 사람들이 DP라고 한다.. 그래서 둘다 풀어보았다. 시간제한이 아주 짧은 것으로 보아... 그렇다. DP가 확실하였구나 1초에 5억번 연산이라치면.. 1/6 대충 8천만번이면 되겠구나. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 먼저 BFS로 한 풀이 15분만에 푼 것 같다. #include #include using namespace std; int num[1000001]; int dist[1000001]; queue Q; int target; void init() { ios::sync_with_stdio(0);..

음.. 전형적인 구현 문제로 말하는 대로 구현하면 된다. 구현에 무엇을 쓸 지는 모두 사용자의 맘대로 다만 시간보다 메모리는 많기에 맘껏 써도 될 것 같다. https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 이건 내가 한 번에 못풀었다. 감은 왔는데 도저히 구현이 되질 않았다. 하지만 풀이를 보니.. 30%정도까지는 맞았더라.. 백트래킹을 써야지~ 생각은 했지만 백트래킹에서 탐색을 하지 못했다. #맞은 풀이(참고해서) #include ..

전형적인 백트래킹 문제다. 백트래킹에 익숙하지 않은 터라 다른 사람풀이를 봐도 이해가 시간이 걸렸다. https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹은 제일 인간다운 생각이 아닌가 싶다. 그리고 무의식적으로 그것이 효율적이라 생각하면서 쓰고 있다. 우선 나는 그렇다. 우선 이 문제를 보자마자 같은 줄에 못놓겠구나 생각이 들었다. 아무튼 거기까지만 하고 들어가보자 한줄에 하나 넣어보고 다음 줄에 되는 것 넣어보고 그 다음줄에 되는 것 넣어보고 하면 될 ..

구현하라는 대로 그냥 구현만 해주는 문제다. 메모리가 아주 적다. https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 문제 범위가 0부터면 쉽겠는데..? 역시 문제를 어렵게 하려면 입력을 드럽게 주면 된다. 하지만 우리가 중요한 것은 연도다. 연도는 해가 한 바퀴 도는 것이 중요하지 연도가 중요하진 않다. 다같이 -1을 해주자 # 맞는 풀이 #include using namespace std; int main(){ int E,S,M; int e,s,m;..

메모리 heap에 생성되며 동적할당이 가능하여 동적 배열을 대체할 수 있는 std:: 를 알아보자 C++ STL 에서 컨테이너는 크게 두 가지 종류가 있다. 배열 처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너 (sequence container) 키를 바탕으로 대응되는 값을 찾아주는 연관 컨테이너 (associative container) 가 있다. 우리가 알아볼 벡터는 시퀀스 컨테이너다. 벡터에는 원소들이 메모리 상에서 실제로 순차적으로 저장되어 있고 따라서 임의의 위치에 있는 원소를 접근하는 것을 매우 빠르게 수행할 수 있다. 하지만 벡터가 만능인줄 알고 있는 사람들도 있지만 그렇지 않다. 맨 뒤에 원소를 추가하거나 제거하는 것은 빠르지만 임의의 위치에 원소를 추가하거나 제거하는 것은 O(n) 으..

BFS의 응용문제다. 어렵진 않지만 응용하는 첫번째 단계라고 할 수 있다. www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 이 문제도 BFS를 이용한다는 감이 온다. 고려해야 할 조건이 몇가지 있다. 1. 지훈이의 탈출 조건 2. 불이 있는 곳에 지훈이 있을 수 없다. 우선 지훈이는 문제에서 가장자리에 있으면 탈출 할 수 있다. 즉, [ i ][ j ] 위치에서 i 또는 j 가 0을 가지거나 최댓값을 가지면 탈출한 것이다. -> 다시 말해서 가..

이것도 BFS의 기본이라고 볼 수 있다. www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이전 문제의 최단경로의 경로문제라고 해도 무방하다. 하지만 약간 꼬아놨으니 BFS의 시작점이 여러군데다. 근데 뭐 별다를 거 없다. 시작점을 큐에 다 넣고 시작하는 것과 같이 얘도 똑같이 해주면 된다. #맞는 풀이 다만 최적화는 되어있지 않은 풀이 #include #include #define X first #define Y second using nam..

이 문제도 이전 문제와 형제문제라고 할 정도로 BFS의 기본을 알려준다 [프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 2178번 C++ [CPP] www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 바로 이 문제가 BFS가 탐색한 노드의 수를 알려주는 것인데 뭐 메모리랑 관련이 있다고만 해두겠다. **사실 큐에 쌓이는 노드가 더 메모리랑 관련있지만..뭐 그렇다. # 맞는 풀이 #include #include using n..

경로 탐색의 핵심은 탐색 방법이다. 그 중 얘는 BFS다. www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 왜 BFS일까?는 최단경로를 찾아야하기 때문이다. DFS는 최단경로를 보장하는 방법이 아니다. 어떠한 경우에 대해서도 최단경로를 찾기 위해서는 BFS를 쓸 수 있다. 일반적으로 메모리는 DFS보다 BFS가 많이 먹을 수 있는..가능성이 높다 나는 이것을 논리가 맞다고 생각하고도 엄청 많이 틀렸다. 바로 입력에 대해서 확인을 소홀히 해서 그렇다. 이 문제에서 입력은 공백없이 주어졌다. ..