티스토리

서랍장

검색하기

블로그 홈

서랍장

terajh.tistory.com/m

기록해놓는 서랍장입니다.

구독자: 2

방명록 방문하기

주요 글 목록

[백준-23296] 엘리베이터 조작 2021 APC (아주대학교 프로그래밍) 대회 문제중 하나였다. 예전에 엘리베이터 관련 문제를 카카오 2차 기출에서 본 듯해서 그걸로 푸는건가? 했지만 해당 문제는 단지 dfs 탐색을 통해 일일이 체킹만 해주면 되는 문제이다. 다만 한가지 집고 넘어가야할 점이 있다. dfs 로 일일이 순회를 해주다가 해당 층에 사람이 없는 경우가 생기게 된다. 이렇게 되면 사람이 있는 층들 중에 한 곳으로 가야하는데 어떤 기준으로 갈 곳을 정해줄까? 에 대한 문제이다. 위상정렬 알고리즘에서 힌트를 가져왔다. 각 층을 원하는 사람의 수를 배열 하나 두어서 체킹해준 다음에 원하는 사람이 작은 층을 갈 곳으로 정하면 된다. 이렇게 되면 중간에 건너띄는 층 없이 모든 층을 깔끔하게 순회할 수 있기 때문이다. 이 점때문에 골드 .. 공감수 2 댓글수 0 2021. 11. 7.
[백준-23295] 스터디 시간 정하기 1 해당 문제는 아주대 프로그래밍 경시대회 div 1 문제 였다. 대회 때 문제를 보자마자 누적합이라는 걸 캐치한 뒤 빠르게 푼 기억이 있다. 일단 문제를 푸는 로직은 다음과 같다. 입력받는 스터디 시간들을 +1 -1 prefix 로직을 통해 체킹을 해준다. 체킹을 모두 완료한 뒤에 각각 시간대의 사람 수를 계산하고, 그 계산한 값으로 누적합 배열을 초기화해준다. 위 과정을 통해 누적합 배열을 초기화해주었다면 그 다음에는 m 만큼의 슬라이딩 윈도우를 만들어 O(N)의 복잡도로 가장 많은 사람들이 있는 시간 구역을 찾으면 끝이다. #include #include using namespace std; typedef long long LL; LL arr[200000]; LL cnt[200000]; LL sum[2.. 공감수 0 댓글수 0 2021. 11. 5.
[백준-1939] 중량제한 간단한 BFS + 이분탐색 문제였다. 일단 입력 값을 보았을 때, node 의 개수가 10000개에 다리의 개수가 10만개이다. 때문에 전체를 다 탐색하게 되면 시간 초과가 발생할 수 있다. 때문에 다음과 같은 로직으로 푸는게 안전하다. 최소, 최대 cost 값을 찾은 다음에 이분탐색으로 적절한 cost 값을 찾는다. 각 cost 값 마다 bfs 를 통해 start - finish 경로가 있는지 확인한다. #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; int check[100001]; int start, finished; vector v[10000.. 공감수 0 댓글수 0 2021. 10. 21.
[백준-17135] 캐슬디팬스 시뮬레이션 + 백트래킹 문제이다. 1차적으로 궁수 3명을 N+1 번째 행에 3명을 조합의 경우의 수로 세워둔다. 그 다음 2차적으로 시간을 N까지 증가시키면서 적들을 아래 칸으로 한칸씩 움직이도록 한다. 3차적으로 한 칸씩 움직인 적들 중 각 궁수에게 가장 가까운, 거리가 같다면 제일 왼쪽에 있는 놈을 찾는 O(NlogN) 로직을 짜준다. 그 후 하나하나 죽이면서 죽는 놈들을 세어주면 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #define MAX_NUM 1000000009 using namespace std; typedef long long LL; typ.. 공감수 0 댓글수 0 2021. 10. 3.
[백준-3020] 개똥벌레 해당 높이에 몇개의 장애물이 있는지 누적합을 사용하는 문제이다. +-prefix 를 사용하여 어디서부터 어디까지 +인지 체크해주면 간단하게 누적합을 구할 수 있으며, O(N)의 복잡도로 문제를 풀 수 있다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; int sum[500001]; int main() { int n, m, a, b, c; scanf("%d %d", &n, &m); for (int i = 1; i 공감수 0 댓글수 0 2021. 10. 1.
[백준-14391] 종이조각 백트래킹 문제이다. 일단 2차원 위치를 하나의 num으로 두고 나머지와, 몫으로 좌표를 설정하도록 한다. 그 후 하나씩 돌아가면서 해당 수만 직사각형 종이에 포함할 것인가 해당 수의 아래를 직사각형 종이에 포함할 것인가 해당 수의 오른쪽을 직사각형 종이에 포함할 것인가 를 하나씩 처리해주면서 문제를 풀면 간단하다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; // 입력값이 100만 -> nlogn 으로 끝내야 한다. int arr[5][5]; int check[5][5]; int dx[] = { -1, 0 }; int dy[] .. 공감수 0 댓글수 0 2021. 10. 1.
[백준-19951] 태상이의훈련소생활 +-누적합 문제이다. 값의 변경을 일일이 배열에 체킹해주면 터지게 된다. 때문에 이를 +-누적합을 통해 구해줄 수 있다. ground : 첫 값이 들어가있는 배열 arr : "+ -" 체킹 배열 sum : 최종적으로 몇 만큼 변경해야하는지 들어있는 배열 #include using namespace std; typedef long long LL; int sum[100001]; int arr[100002]; int ground[100002]; int main() { int n, m, a, b, c; scanf("%d %d", &n, &m); for (int i = 1; i 공감수 0 댓글수 0 2021. 9. 30.
[백준-10800] 컬러볼 20만의 입력값에 대응하기 위해 nlogn 또는 n의 복잡도로 문제를 풀어야 한다. 이를 위해 누적합을 통해 문제를 풀 수 있다. 다만 전체 합에 대한 누적합과 각 색상에 대한 누적합을 따로 구하여 해당 값을 처리해주면 된다. 이를 2가지 방법으로 구현하였다. 각 색상에 대한 누적합을 구해놓고, 각각의 답을 구할 시에 이분탐색을 돌린다. 모든 명령어를 정렬한 뒤 색에 대한 누적합과 전체에 대한 누적합을 동시에 진행해준다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; typedef long long LL; typedef pair pii; LL input; LL arr[2001]; LL all_.. 공감수 0 댓글수 0 2021. 9. 30.
[백준-10986] 나머지 합 누적합과 조합 계산식이 필요한 문제다. 일단 입력값을 보면 100만임을 봐서 최소 O(NlogN) 의 복잡도 내로 끝내야 함을 알 수 있다. 허나 이 문제의 경우 각 누적합을 통해 O(N) 복잡도로 끝낼 수 있다. 로직은 다음과 같다. 입력되는 배열을 순서대로 sum 배열에 넣되 m으로 나눈 나머지 값을 쭉 넣어준다. sum 배열을 순회하면서 원소를 pai 배열에 체킹해준다. pai 배열에 체킹된 순서로 순회하면서 조합식을 더하면 답이 된다. 이렇게 pai 배열을 둔 이유는 sum[i] - sum[j] = 0 이 되는 경우의 수를 찾아야 하는데 결국 sum[i] == sum[j] 인 경우를 찾는 것과 다름이 없다. 따라서 같은 값을 가지는 sum 배열의 원소들을 쭉 체킹해준 다음 nC2의 조합식에 따라 .. 공감수 0 댓글수 0 2021. 9. 29.
[백준-11659]구간합구하기4 구간합을 구하는 간단한 문제였다. 세그먼트 트리 나 누적합 으로 풀면 간단하게 풀린다. 누적합 로직은 다음과 같다. (a~b)의 합 = b까지의 합 - (a-1)까지의 합 코드는 두가지 버전으로 작성해보았다. // 세그먼트 트리 로직 #include using namespace std; typedef long long LL; LL tree[300000]; LL query(int node, int s, int e, int l, int r) { if (e < l || r < s) return 0; if (l 공감수 0 댓글수 0 2021. 9. 29.
[백준-15724] 주지수 카카오 6번 효율성 에 대해 검색하던 중 찾은 누적합 문제이다. 비슷하게 좌표를 통해 2차원 DP로 푸는 문제이다. 로직은 다음과 같다. (i,j) 까지의 누적합 = (i,j)의 값 + (i-1,j)까지의 누적합 + (i,j-1)까지의 누적합 - (i-1,j-1) 까지의 누적합 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #define MAX_NUM 1000000009 using namespace std; typedef long long LL; typedef pair pii; int arr[1300][1301]; int main() { int row, col, a;.. 공감수 0 댓글수 0 2021. 9. 28.
[백준-2473] 세 용액 약간의 기술이 필요한 투 포인터 문제였다. 일단 기본적으로 5000의 입력값에 1초의 제한시간이기 때문에 O(N^2) 의 복잡도까지는 잘 통과할 것이다. O(N*NlogN) 까지도 가능할거라 생각한다. 여튼 3개의 용액을 골라야 하므로 N의 복잡도는 첫 시작 용액을 고르는 것에, 나머지 N은 투포인터 탐색으로 나머지 2개의 용액을 고르는 것에 사용하여 O(N^2)의 복잡도로 끝마무리 할 수 있다. 로직은 다음과 같다. 첫 번째 용액을 순서대로 선택한다. 고른 용액 이후의 용액들 중 2개의 용액을 투포인터 탐색을 통해 찾는다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #inclu.. 공감수 0 댓글수 0 2021. 9. 23.
[백준-2467] 용액 전형적인 투포인터 문제이다. 10만의 입력값에 1초의 시간 제한을 보자마자 최소 O(NlogN)의 복잡도를 사용해야 한다는 것을 생각해야 한다. 또한 정렬이 되어있다는 조건을 본 후 이분탐색 또는 투포인터탐색을 떠올린 뒤 로직을 생각하면 된다. 이 문제의 경우 간단한 로직을 사용한다. lo, hi 를 양끝으로 잡은 뒤 값을 비교하며 투 포인터 탐색을 진행한다. 진행 시 계산한 값이 음수이면서 0에 가까운지 양수이면서 0에 가까운지 체크한다. 각 경우에 따라 lo를 증가시킬지 hi를 감소시킬지 정해주며 답을 찾아가면 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include.. 공감수 0 댓글수 0 2021. 9. 22.
[백준-1949] 우수마을 그래프 + dp 문제 이다. 이 문제를 풀기 이전에 dp와 dfs 를 같이 사용해서 생각하는 방법을 기를 수 있어야 한다. 일단 해당 문제는 top-down dp 방식으로 풀이할 수 있다. 예를 들어 7 부터 tree 를 순회한다고 할 때, 7번째 마을을 우수마을로 선정하는 경우 7번째 마을을 우수마을로 선정하지 않는 경우 2가지의 경우로 DP 상태를 선정할 수 있다. 또한 7번째 마을을 우수마을로 선정하기 위해서는 7번째 마을과 연결된 마을들이 선정되지 않는 경우를 알아야 하고, 7번째 마을을 우수마을로 선정하지 않기 위해서는 상관이 없다. 이를 이용해서 dp 로직을 구할 수 있다. 특정 마을이 선정되는 경우 = (자식 마을이 선정되지 않은 경우의 합) + 특정 마을의 인원수 특정 마을이 선정되지 않는.. 공감수 0 댓글수 0 2021. 9. 20.
[백준-17136] 색종이 붙이기 좀 단순한 dfs 탐색 문제였다. 각 크기의 색종이의 개수를 배열에 저장해둔 다음, 해당 위치 부터 차례대로 5, 4, 3, 2, 1 크기의 색종이를 대조하고, 다음 노드를 탐색하는 로직만 구현하면 된다. 전체 배열의 크기가 10*10 로 크지 않으며, 색종이의 종류 역시 5개이므로 시간 제한은 매우 널널하다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #define INF 100000000 using namespace std; typedef pair pii; typedef tuple tiii; typedef long long LL; int arr.. 공감수 0 댓글수 0 2021. 9. 5.
[백준-6443] 애너그램 간단한 탐색 문제이다. 바로 로직을 보면 다음과 같다. 입력받은 문자열을 알파벳 순으로 정렬해준다. map 을 두어 이미 체크한 문자열을 탐색하지 않도록 설정해준다. 그 후 문자열의 idx 에 대해 check 해주며 브루트 포스 탐색을 실시한다. 이러면 그냥 답이 나온다... 간단~ #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #define INF 100000000 using namespace std; typedef pair pii; typedef tuple tiii; int arr[100001]; int check[100001]; int visit.. 공감수 0 댓글수 0 2021. 9. 3.
[백준-9466] 텀 프로젝트 트릭이 필요한 탐색 문제였다. 일단 기존 DFS 를 사용해서 단순하게 check 하며 탐색한다. 이 때 cycle 이 생기는 경우 해당 cycle 에 포함되지 않는 노드의 개수를 구하기 때문에 visit 배열을 하나 더 만든다. 그 후 다음과 같은 규칙을 세운다. check는 color 로 칠하되 다른 컬러의 check 를 만났다면 그건 이미 만들어진 cycle 이므로 해당 color 구축시에는 cycle 노드 개수가 0이다. (0 return) check 가 0으로 되어있어 순회하는 경우 visit 배열에 몇 개의 노드를 탐색 중인지 메모해놓는다. check 가 color 로 칠해져있는 노드에 다시 한번 더 접근한 경우 해당 color 단계에서 cycle 이 발생했다는 것이다. 이 때 visit 에 저.. 공감수 0 댓글수 0 2021. 9. 3.
[백준-8111] 0과 1 시간 제한은 1초에 테스크 케이스의 개수가 1000개이니 각 테스트 케이스마다 최소 10만 이내의 복잡도로 끝내야 하는 문제이다. 이때 수가 20000까지의 수이기 때문에 반복문 2개를 놓는순간 제한에 걸리게 된다. 이 문제는 조건과 나머지의 규칙을 통해 풀 수 있다. 다음 식들을 쭉보자 10 = (1 * 7) + 3 100 = (10 * 7) + 30 101 = (10 * 7) + 31 ...... 이 식들을 보았을 때 나누게 되는 수가 10곱만큼 늘어나게 되면 나머지 역시 10곱만큼 늘어나게 된다. 또한 나누게 되는 수가 1만큼 늘어나게 되면 나머지 역시 1만큼 늘어나게 된다. 이를 이용해서 string, int 값을 queue 에 넣어가면서 나머지가 0이 될 때까지 탐색을 돌릴 수 있다. #defi.. 공감수 0 댓글수 0 2021. 9. 2.
[백준-4179] 불! 약간의 테크닉이 필요한 탐색 문제였다. 예전에 바이러스 관련해서 비슷한 문제를 푼거 같긴한데 로직은 다음과 같다. 불 위치에서 BFS 탐색을 시작해 번지는 시간대를 check 배열에 메모 메모된 check 배열에 따라 지훈이의 위치에서 탐색을 시작 양 모서리 지점까지 도달했으면 탈출한 것으로 체크 딱 봤을 때는 간단한데 1번과 2번을 연동시키는게 좀 생각하기 어렵다. 허나 여러번 풀어보면 간단해보이니 계속 풀어대자 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #define INF 100000000 using namespace std; typedef pair pii;.. 공감수 0 댓글수 0 2021. 8. 30.
[백준-16973] 직사각형 탈출 단순한 탐색 문제였다. 직사각형의 범위에 벽이 있나없나만 체크하며 queue 에 넣어주면서 탐색을 진행하면 풀리는 단순한 문제였다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #define INF 100000000 using namespace std; typedef pair pii; struct Square { int x, y; int tm; }; Square initSquare(int _x, int _y, int _tm) { Square tp; tp.x = _x; tp.y = _y; tp.tm = _tm; return tp; } int arr[1001][1001]; int ch.. 공감수 0 댓글수 0 2021. 8. 30.
[백준-17836] 공주님을 구해라! 전형적인 BFS 문제이다. 단순히 길만 따라서 check 배열에 메모 후 탐색, 메모 후 탐색 의 로직으로 문제를 풀게 되면 틀리게 된다. 탐색하는 경우의 수가 사실 2배 더 많기 때문이다. 칼이 있는지, 없는지에 대한 경우를 생각해야 하기 때문에 2배이다. 예를 들어 (2,3) 위치에 이동할 때, 칼을 가진 상태로 이동하는 것과 칼을 가지지 않은 상태로 이동하는 것은 명백히 다른 경우의 수이다. 떄문에 이 두 가지 경우를 다르게 봐야하고 그에 따라 check배열 또한 3차원 배열로 만들어주어야 한다. 그 후에는 다음 코드와 같이 단순히 BFS 탐색을 때리면 끝! #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #i.. 공감수 0 댓글수 0 2021. 8. 30.
[백준-13164] 행복 유치원 모든 경우이 수를 다 보는 것은 1초의 제한시간과 30만의 입력값을 보았을 때 당연히 되지 않는구나~ 라고 느껴야 한다. 때문에 뭔가 다른 방법을 생각해야 한다. 이 문제의 경우는 인접한 수끼리의 차를 정렬한 뒤 N-K 만큼 앞부터 원소를 고르는 식으로 집합을 생각하면 간단하다. 이와 같이 구현만 하면 문제는 간단히 풀린다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long LL; deque arr; int main() { ios_base::sync_with_stdio(false); cin.tie(NU.. 공감수 0 댓글수 0 2021. 8. 26.
[백준-21758] 꿀 따기 경우를 잘 나눠야 하는 문제이다. 일단 문제의 시간제한 1초를 봤을 때 10만의 입력값으로 통과하기 위해서는 답은 O(Nlog(N)) 의 시간 제한으로 풀 수 있어야 한다. 때문에 이분탐색, 세그먼트 트리 등등의 알고리즘을 떠올릴 수 있다. 이 문제의 경우에는 다른 자료구조가 필요한 것이 아니라 전체 경우가 최대값을 가지기 위해서는 특정 경우로 나뉜다 정도만 알면 풀 수 있다. 전체 최대값을 가질 수 있는 경우는 다음과 같다. "벌꿀 - 벌 - 벌" 순서로 있는 경우 "벌 - 벌 - 벌꿀" 순서로 있는 경우 "벌 - 벌꿀 - 벌" 순서로 있는 경우 각 경우마다 왼쪽 끝, 오른쪽 끝에 위치해야하고, 중간 특정 지점이 위치해야 한다. 위 3가지 경우에 대해 값을 다 확인하며 최대값을 구할 때 O(N) 의 복.. 공감수 0 댓글수 0 2021. 8. 26.
[백준-2696] 중앙값 구하기 heap 2개를 가지고 Nlog(N) 의 시간 내로 중앙값을 뽑아내는 로직을 사용하면 쉽게 풀린다. heap 2개는 다음과 같다. 절반의 작은 값들을 저장하는 max heap 절반의 큰 값들을 저장하는 min heap 이 때 min heap 이 max heap 크기 이상의 특징을 계속 가지도록 한다면 홀 수 개의 값이 입력되었을 때 min heap 의 top 을 출력하도록 하면 쉽게 풀린다. 예를 들어 입력되는 수가 1, 5, 4, 3, 2 라고 해보자. 1 이 들어오게 되면 먼저 min heap 에 넣는다. 그 후 5가 들어오면 size 가 작은 max heap 에 넣는다. 넣은 후 max heap 의 top과 min heap의 top 을 비교해서 max heap 의 것이 더 크다면 서로 top 을 s.. 공감수 0 댓글수 0 2021. 8. 23.
[백준-21939] 문제 추천 시스템 Version 1 시간 복잡도가 1초이고, 입력값이 10만개, query 의 값이 만개 이므로 각 query 마다 log(N) 의 복잡도 내로 답이 나오도록 처리해야 문제가 풀리게 된다. 이를 위해 입력 시에만 Nlog(N) 의 복잡도가 걸리고 query 에 따른 값을 뽑아 낼 때는 log(N) 의 복잡도를 가지는 min heap, max heap 2개와 solved 된 문제를 체킹하기 위한 배열 1개가 잇으면 간단히 풀리게 된다. 단, solved 된 문제를 체킹할 때 해당 문제의 난이도를 배열에 저장함으로써 이 후 top 의 값이 체킹해두었던 난이도가 아니라면 pop 하고 다음 수를 보는 로직을 통해 문제를 해결할 수 있다. #define _CRT_SECURE_NO_WARNINGS #include #include #i.. 공감수 0 댓글수 0 2021. 8. 23.
[백준-3109] 빵집 단순한 그래프 탐색을 진행하게 되면 바로 시간이 터지게 된다. 오른쪽위 → 오른쪽 → 오른쪽 아래 순으로 탐색을 하는 그리디 1, 빵집의 가스관 위쪽부터 차례대로 파이프를 연결할 수 있나? 없나? 를 확인하며 파이프를 만드는 방식의 그리디 2 총 2개의 2그리디 방식을 사용해야 한다. 첫 번째 그리디의 경우 어찌저찌 잘 생각할 수 있겠지만, 두 번째 그리디의 경우에는 생각하기 어려워서.. 매우 오랜 시간이 걸린 문제이다. 로직은 다음과 같다. 빵집의 가스관 위쪽 부터 dfs 탐색을 돌며 파이프를 만들 수 있는지 확인한다. ( 만들 수 있으면 response 에 +1, 없으면 +0 을 해준다. ) 그리디만 알면 생각보다 간단한 문제이나 생각하기 힘들다... #define _CRT_SECURE_NO_WARN.. 공감수 0 댓글수 0 2021. 8. 22.
[백준-1799] 비숍 시간 복잡도가 중요한 문제이다. 일단 제한 시간을 보면 10초인 것을 볼 수 있다. 허나 입력값이 100개인 배열에서 일일이 다 비숍을 넣어가면서 백트래킹을 하게 된다면 O(2^(10*10)) 이 되어 터져버리게 된다. 이를 위해 체스판의 특징을 생각해 흑,백 으로 나눠 로직을 짜보려고 한다. 이렇게 되면 복잡도가 O(2^(5*5)) 가 되어 문제 없이 제한시간을 맞추게 된다. 분할해서 생각한다면 로직은 일반 백트래킹과 다를바 없어 넘어가도록 하겠다. 다만 흑,백으로 나누어 check 배열을 두고 확인하는 로직만 유심히 보면 될것 같다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using na.. 공감수 0 댓글수 0 2021. 8. 21.
[백준-1562] 계단 수 DP 에 비트마스킹까지 포함시킨 문제이다. 일단 수를 일일이 다 확인해가면서 0부터 9까지 있는지 확인하는 작업은 복잡도 측면에서 몇십배 정도 더 늘어나게 된다. 때문에 이를 위해 비트마스킹 기법을 통한 체킹 로직이 필요하다. 추가로 DP 메모라이징 기법을 통해 이 문제를 비교적 간단하게 풀 수 있다. 처음에만 봤을 때 어렵지 한 번 이해하면 다음에는 쉽지(??!) 않을까 생각하는 문제이다. 다음에 한 번 더 풀어보는 걸로.. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long LL; int N; int.. 공감수 0 댓글수 0 2021. 8. 20.
[백준-16724] 피리 부는 사나이 구현 + DFS 문제였다. 네트워크 개수를 세는 듯한 문제인데 입력받은 U, D, L, R 에 따라 쭉~ 이어주는 동시에 다음 값이 현재 있는 값으로 들어올수도 있는지 확인하는 로직을 구현하면 간단한 문제였다. 다시 로직을 정리하면 다음과 같다. 지도 (0,0) 부터 check 되어있지 않으면 dfs 로 해당 지점으로부터 연결되어있는 모든 지도지점을 check SAFE ZONE 개수 한개 추가 그 후 check 안되어있는 지점으로부터 dfs 처리해서 똑같이 네트워크 check SAFE ZONE 한개 추가 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; typedef pair pi.. 공감수 0 댓글수 0 2021. 8. 20.
[백준-12852] 1로 만들기 2 단순 BFS 를 사용하면 100만 + 300만 정도의 복잡도가 나오게 되어서 전혀 복잡도가 터질 일이 없다. 따라서 BFS 를 따라 로직만 잘 처리해주면 된다. 로직은 다음과 같다. 처음 입력된 수와 비어있는 문자열을 queue 에 넣는다. 이 후 queue 의 front 를 빼고 3가지 연산 각각을 할 수 잇는지 확인하고 연산이 가능하면 연산된 값을 다시 queue 에 넣고 해당 숫자를 더한 문자열또한 queue 에 넣는다. 위의 과정을 1이 나올 떄까지 반복한다. 생각보다 간단한 알고리즘이다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; typedef pair pii; i.. 공감수 0 댓글수 0 2021. 8. 20.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.