HappyTomatoLife

2606번: 바이러스 (acmicpc.net) 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 첫 DFS 문제! 일단 이차원 배열에 그래프를 정의해주고, 그 다음에 dfs 함수를 구현하고, 시작 노드를 dfs에 넣어 완전탐색을 시킨다. #include #include int answer = 0; void dfs(int x, int vertex, int edge, int** graph, int* visited) { visited[x] = 1; for (int i = 1; i > vertex; std::cin >> e..

15649번: N과 M (1) (acmicpc.net) 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 이전에 알아야할 것 = DFS #include int n, m; int arr[9] = { 0, }; bool visit[9] = { 0, }; void back(int depth) { if (depth == m) { for (int i = 0; i < m; i++) { std::cout m; back(0); return 0; }

9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 알고리즘을 복습해보자. 백트래킹 백트래킹 알고리즘은 해를 찾는 도중에 해가 아니어서 막히면, 그 전으로 되돌아가서 다시 해를 찾는 기법을 말한다. DFS가 모든 경우의 수를 살핀다면, 백트래킹은 지금의 경로가 해가 아닌 것이 판명나면 다른 경로를 찾아간다. N-Queen 문제 설명은 간단하다. [문제] N-Queen 문제는 크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 ..

1620번: 나는야 포켓몬 마스터 이다솜 (acmicpc.net) 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 마찬가지로 C++ STL map을 이용해서 푸는 문제였다. 이 문제는 시간초과가 관건이라 최대한 간단하게 생각해내는 게 중요한 것 같다. 그리고 출력을 따로 벡터에 저장하지 않고 바로바로 처리해줘도 된다는 걸 오늘 알았다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include int m..

2358번: 평행선 (acmicpc.net) 2358번: 평행선 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 주어진다. 만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다. 좌표는 절댓값이 231보 www.acmicpc.net 문제는 너무 간단해서 딱 그냥 for문으로 풀면 시간초과가 나겠다는 생각이 들었다. STL map을 이용하면 해결되는 문제 Code by horang :: c++ std::map 사용법 총 정리1 (생성, 반복자, 크기, 값 확인 등) (tistory.com) #include #include #include int main() { // n 개의 좌표 int n; std::cin >> n; std::m..

2257번: 화학식량 (acmicpc.net) 2257번: 화학식량 첫째 줄에 화학식이 주어진다. 화학식은 H, C, O, (, ), 2, 3, 4, 5, 6, 7, 8, 9만으로 이루어진 문자열이며, 그 길이는 100을 넘지 않는다. www.acmicpc.net 골드까지 화이팅! #define _CRT_SECURE_NO_WARNINGS #include #include #include #include int main() { char* str = new char[100]; scanf("%s", str); int size = strlen(str); std::stack stk; int i = 0; while (i < size) { if (str[i] == '(') { stk.push(-1); } else if..

1823번: 수확 (acmicpc.net) 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 다이나믹 프로그래밍.. 너무 어렵당 그래도 왜 전역변수로 DP용 배열을 만드는지 알게 되었다. DP용 배열이 전역변수로 있으면, 재귀함수로 구현했다고 하더라도, 같은 값을 여러 번 구하지 않아도 된다. #include using namespace std; int n, a[2001], d[2001][2001]; int dp(int l, int r, int k) { if (l > r) { return 0; } int& ret = d[l][r]; if (ret..

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 다이나믹 프로그래밍 문제였다. 다이나믹 프로그래밍을 푼 두번째 문제였는데, 다이나믹 프로그래밍은 배열을 하나 더 만들어서 재귀 대신 쓰는 방식인 것 같다. 이 문제에서도 복잡하게 생각할 것 없이 수열 사이즈에 맞는 배열을 하나 더 만들고, 배열마다 그 사이즈를 다른 배열을 이용해 저장해주었다. 몇 번 틀렸는데, 그건 배..

2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net DP에서는 재귀 대신 배열이나 벡터를 이용해서 값을 저장한다. #include #include #include int main() { int n; std::cin >> n; std::vector v; std::vector dp(301); for (int i = 0; i > tmp; v.push_back(tmp); } dp[0] = v[0]; dp[1] = v[0] + v..

18310번: 안테나 (acmicpc.net) 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 짝수와 홀수로 나눠서 중간값을 출력해주면 끝! #include #include #include int main() { int n; std::cin >> n; std::vector v; for (int i = 0; i > tmp; v.push_back(tmp); } std::sort(v.begin(), v.end()); if (v.size() % 2 == 0) { std::cout