기억보다는 기록을 해볼까

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 생각 문제의 조건이 많아 천천히 읽으며 정리해야 한다. 안 그러면 이상한 풀이로 계속 풀다가 꼬인다. 1주일 정도 고민을 했지만 계속 답이 나올락 말락 안 나왔다. 그래서 다른 사람의 코드를 참고했다. https://yulme.tistory.com/92 이 사람은 우선순위 큐로 우선순위를 연산자로 정했다. 우선순위는 거리 > 가장 위 > 가장 왼쪽 순이다. 이동하는 거리를 저장하는데 ..

문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 생각 트리의 루트와 노드의 기본에 대해 이해하기 좋은 문제이다. 코드 #include #include #include using namespace std; int main() { int n; cin >> n; vector v[100001]; bool vst[100001]; int arr[100001]; for(int i = 0; i > a >> b; v[a].push_back(b); v[b].push..

문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 생각 코드 #include #include using namespace std; int main() { int n; int dp[1000]; int arr[1000]; int sum = 0; cin >> n; for (int i = 0; i > arr[i]; for (int i = 0; i < n; i++) { //현재 위치 //자기 자신만으로도 1 dp..

문제 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 생각 시간 초과로 두들겨 맞고 있다. 추가적인 수정이 필요함 코드 #include #include #include #include #include using namespace std; int main() { ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; for(int j = 0; j > k; deque dq;..

문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 생각 처음 봤을 때 어떻게 해야 할지 막막했다. 다른 사람의 코드도 읽어 봤는데 이게 어떻게 잘 굴러가는 건지 잘 모르겠어서 그것을 참고만 하고 나의 새로운 코드를 작성했다. 먼저 배열을 다 받은 다음에 정렬을 시킨다 전의 끝나는 시간보다 현재의 시작하는 시간이 더 작고 현재의 끝나는 시간이 전의 끝나는 시간보다 작거나 같으면 끝나는 시각을 현재의 끝나는 시각으로 최신화해준다. 전의 끝나는 시간보다 현재의 시작하는 시간이 크거나 같으면 회의가 새로 생기는 것이기 때문에 카운트를 하나 늘려준다. 코드 #include #include #include using namespac..

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 생각 다섯 가지 도형을 모두 만들어서 2차원 배열을 순회하는 것은 좀 아니라고 생각해서 DFS로 4개의 정사각형을 돌면 엿 모양을 뺀 모든 도형이 나온다. DFS로 구현을 한 다음에 엿모양의 도형 4가지를 순회하게 했다. 코드 #include #include #include using namespace std; int n, m; int map[501][501]; bool vst[501][501] = {false}; int dx[4] = {1, -1, 0, 0}; ..

오늘은 당직을 가야 하니 간단한 1 문제만 풀고 가야겠다. 재귀를 통한 순열 구현문제이다 이제부터는 순열 관련 문제들이 꽤 포스팅될 것 같다. #include using namespace std; int n; int arr[9]; bool visited[9]; int m; void dfs(int num, int cnt) { if(cnt == m) { for(int i = 0; i < m; i++) cout m; dfs(1, 0); }

예전에 못 풀었던 문제를 다시 풀어보았다. 다른 분들의 코드를 참고해서 모르는건 검색해봤다. #include #include #include using namespace std; int main() { vector v; vector org; int n; cin >> n; for(int i = 0 ; i > a; v.push_back(a); org.push_back(a); } sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); for(int i = 0; i < org.size(); i++) { int a = org[i]; int pos = lower_bound(v.begin(),v..

처음에 브루트포스로 안풀었더니 시간초과가 나와서 검색을 동원해 결국 브루트포스로 풀었다. 아래는 브루트포스로 푼게 아닌 답이다. #include #include using namespace std; int main() { int n; cin >> n; int m; cin >> m; bool arr[10]; for(int i = 0; i > a; arr[a] = true; } if(n == 100) { cout

이렇게 길게 쓸 필요가 없는 문제인 듯 하지만 당장 생각나는게 없다. 적록색약이 아닐때 R, G, B 적록색약일 때 (R, G), B 함수를 따로따로 만들어 count 했다. #include #include #include using namespace std; int n; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; string map[101]; bool vst[101][101] = {false}; bool CBvst[101][101] = {false}; queue q; void rcheck() { while(!q.empty()) { auto[y, x] = q.front(); q.pop(); for(int i = 0; i < 4; i++) { int n..