알고리즘/BOJ 썸네일형 리스트형 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.. 더보기 15661번 15661번 - 링크와 스타트 '스타트와 링크' 문제랑 흡사하게 만든 다른 문제이다. 기존문제랑 다르게 이 문제는 팀을 절반으로 나누지않아도 된다. 그냥 1명이상 팀이 유 지되면 된다는 조건이 있기 때문에 약간 다르다. 나는 그냥 완전탐색을 통해, 1번팀으로 뽑는다/ 뽑지 않는다 이런방식으로 완전탐색을 진행하였다. 왜냐하면 N제한이 20이기 때문에 시간복 잡도가 O(2^20) 으로 충분히 실행이 가능하다고 생각했기 때문이다. 하지만 이런 방식은 중복되는 값들을 다시 한번 계산하게 되므로 좀 더 시간 복잡도를 줄여서 풀 수 있을 것 같다. ( 빨리 푸신 분들은 DP로 접근한 듯 하다) 중복된다는 것은 i번 사람을 1번 팀으로 뽑고, 전부다 2번 팀으로 뽑는 경우와 i번 사람을 2번 팀으로 뽑고, 나머지를 .. 더보기 이전 1 2 3 4 ··· 40 다음