알고리즘 썸네일형 리스트형 16234번 16234번 - 인구 이동 어제 시험장에서 풀었던 문제고, 그때 풀었던 방식 그대로 다시 제출해봤다. 다른 문제는 약간의 시간이 필요한 노가다여서 다시 풀기 귀찮.. 기본적인 토대는 BFS를 바탕으로, 큐에 들어갈때 조건을 어떤 방식으로 하느냐의 문제였다. 그냥 while 문을 통해서 시간을 증가시켜주면서, 각 점에서 BFS를 수행한다. BFS는 구역을 나누는 용도로 사용된다. 그리고 만약 BFS 큐에 들 어가지 않는다면 이는 더이상 이동할 수 없다는 뜻이므로 break 문을 통해서 시간을 측정한다. 그리고 큐에 넣으면서 나중에 바꿔줘야 하는 구역들의 값과 개수를 따로 저장해서 문제를 해결했다. 실제 시험장에서는 내가 sum과 cnt 배열의 크기를 2500까지 했었는데, area 가 1부터 시작하기 때문.. 더보기 9944번 9944번 - N*M 보드 완주하기 어떻게 풀지 고민하다가 그냥 완전탐색을 하는 방법으로 문제를 풀었다. 사실 움직이는 모습이 DFS와 유사하지만, 막힐 때까지 한쪽으로만 쭉 움직인다는 점을 이용하면 문제를 풀 수 있다. 사실 완전탐색으로 풀려고 마음을 먹으면, 시간 복잡도를 우선적으로 판단해야 했다. N,M 의 범위가 30이기 때문에 만약 DFS로 하면 시간초과가 날 수 있었지만, 이건 한쪽방향으로 쭉 이동하는 방식을 띄기 때문에 정확하게 판단은 못해도 시간이 꽤나 많이 단축될 것 같아서 완전탐색을 시도했다. 이 문제의 더 많은 테스트케이스는 -> https://ncna-region.unl.edu/ 문제를 풀면서 예외케이스가 있었는데 바로 맵 전체에서 딱 한칸만 비어있는 경우였다. 나는 처음에 이 경우.. 더보기 14442번 14442번 - 벽 부수고 이동하기2 기존의 벽 부수고 이동하기 문제랑 비슷하다. 기본개념은 BFS인데 BFS를 어떤 방식으로 사용할지 정하면 된다. 이때는 부수고 이동하는 개념을 맵에서 한차원 늘린다고 생각하는게 쉽다. 즉 이차원 평면이 아니라 삼차원 평면에서 BFS를 실행한다고 생각 하면 된다는 뜻이다. 처음에 하나의 평면에서 시작하면서 BFS를 진행하다가, 벽이 생기고 그 벽이 방문한 적이 없고 아직 벽을 부실 수 있는 횟수가 남아있다면 다른 차원의 이차원 평면으로 올라가는 것이다. 이런 삼차원 평면 방식의 문제가 있었던 것 같은데 문제번호는 잘 기억나지 않는다. 아무튼 이런식으로 BFS에서 조건을 체크하면서 진행하면 벽을 부수고 이동할 수 있게 된다. 1234567891011121314151617.. 더보기 16198번 16198번 - 에너지 모으기 완전탐색을 통해서 쉽게 정답을 구할 수 있다. used 배열을 만들어서 제거한 원소들을 체크한다. 그리고 find 함수에서는 선택된 지점에서 앞 뒤로 탐색하면서 앞의 값과 뒤의 값을 구하고, 그것을 곱한 값을 리턴해준다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include using namespace std;int N;int W[11];int used[11];int ans = 0;int find(int n){ int front; int back; for (int i = n - 1; i >= 0.. 더보기 16197번 16197번 - 두 동전 동전을 최대 4가지 방향에 대해서 10번까지 던질 수 있으므로, 최악의 경우 O(4^10) 이 된다. 따라서 완전탐색으로 주어진 시간 내에 문제해 결을 할 수 있다. 두 가지 동전을 동시에 이동시키면서 조건에 따라서 나누었다. 벽이 있는 경우와 벽이 없는 경우 조건문을 이용해서 나누었 다. 그리고 기저 조건에서는 지금 구한 정답보다 더 던졌는지, 10번 넘게 던졌는지, 둘다 범위를 넘는지, 하나만 범위를 넘는지를 체크해준다. 만약 정답을 구할 수 없는 경우에는 ans 가 초기값인 INF 로 설정되어 있으므로, -1로 바꿔준 후 정답을 출력하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041.. 더보기 14225번 14225번 - 부분수열의 합 단순한 조합 문제였다. 수열의 갯수도 최대 20개 이므로 시간복잡도는 O(2^20)이 된다. 따라서 완전탐색으로 충분히 해결할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839#include using namespace std;#define MAX 2000001int N;int S[20];int num[MAX];void go(int k,int sum){ if (k == N) { num[sum] = 1; return; } go(k + 1, sum + S[k]); go(k + 1, sum); }int main(){ cin >> N; for (int i = 0; i > S[i]; go(0,0);.. 더보기 2422번 2422번 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 처음에는 오름차순으로 모든 경우의 수를 구하고, 기저 조건에서 모든 M번의 for문을 수행하면서 섞으면 안되는 조합이 있는지를 검사하는 방식을 구현했었다. 그런데 최악의 경우 200개 중에서 3개를 고르는 조합의 수 * 10000번의 for문을 돌게 되면 시간초과가 발생하게 된다. 따라서 M이라는 변수는 배열을 이용해서 저장하고, 최대한 200이라는 N의 값을 이용해서 문제를 풀어야 했다. 그래서 3개의 아이스크림만 고르면 되기 떄문에 first second third 를 재귀함수를 이용해서 구하면서 마지막에 먹어도 되는 조합인지 아닌지 를 판단하는 방식으로 코드를 구현했다. 12345678910111213141516171819202122232.. 더보기 3184번 3184번 - 양 해당 영역마다 BFS를 이용해서 문제를 풀 수 있었다. 처음에 탈출하는 영역 예외 처리를 해줘야 한다고 생각했는데, 문제를 읽어보니 양과 늑 대는 모두 영역 안에 존재한다는 조건때문에 그냥 각 영역에서 BFS를 실행하면 되는 문제였다. 각 영역에서 BFS를 실행하여, 해당 영역의 양의 수와 늑대의 수를 구하고, 늑대가 많거나 같으면 늑대를 최종 늑대 개수에 더해준다. 그 반대 의 경우에는 양의 수를 최종 양의 개수에 더해준다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include#i.. 더보기 이전 1 2 3 4 ··· 46 다음