반응형 알고리즘/BAEKJOON87 BOJ 1261 : 알고스팟 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1261 ※ 다익스트라를 이용하여 최단 경로 이동하기는 유니티에서 확인할 수 있다. BOJ 11779 : 최소비용 구하기 2의 다익스크라(데이크스트라) 알고리즘을 2차원 배열에서 사용하면 된다. 2차원 배열의 각 인접한 노드는 dr, dc 배열로 탐색한다. int dr[] = { 0, 1, 0, -1 }; int dc[] = { 1, 0, -1, 0 }; 그리고 벽(1)이 비용이 된다. int MAP[110][110]; 거리를 저장할 2차원 배열과 방문 여부를 체크하는 배열, 그리고 최소 힙을 만든다. int distance[110][110]; int visit[110][110]; typedef struct st2 { in.. 2022. 7. 17. BOJ 11779 : 최소비용 구하기 2 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/11779 ※ 다익스트라를 이용하여 최단 경로 이동하기는 유니티에서 확인할 수 있다. 출발 도시에서 도착 도시까지 가는데 드는 최소 비용과 도시의 개수 그리고 최소 비용이 되는 경로도 출력해야 한다. 메모리 풀 방식으로 각 도시 간의 연결과 가중치를 저장한다. typedef struct st { int value; int weight; struct st *next; }NODE; NODE HEAD[1010]; NODE POOL[100100]; int pcnt; void Make(int p, int c, int w) { NODE *nd = &POOL[pcnt++]; nd->value = c; nd->weight = w; nd-.. 2022. 7. 16. BOJ 11004 : K번째 수 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/11004 O(NlogN) 정렬로 정렬한 후, A[K]를 출력하면 된다. 여기서는 merge sort를 사용하였다. 이때, K는 입력을 받은 후, 1을 빼야한다. #include int N, K; int A[5050000]; int B[5050000]; void merge(int* A, int start, int end) { int mid, i, j, k; mid = (start + end) >> 1; i = start; j = mid + 1; k = 0; while (i 2021. 7. 21. BOJ 2252 : 줄 세우기 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2252 A가 학생 B 앞에 서야 한다는 조건이 있으므로 위상 정렬을 이용하여 풀면 된다. 즉, A → B에 대해 B의 indegree가 1 증가하고, indegree가 0인 학생부터 BFS를 시작하면 된다. 설명은 BOJ 1005 : ACM Craft와 동일하다. #include int N, M, A, B; int indegree[32100]; int queue[100100]; int rp, wp; typedef struct st { int value; struct st *next; }NODE; NODE HEAD[32100]; NODE POOL[100100]; int pcnt; void Make(int p, int c) .. 2021. 7. 17. BOJ 1005 : ACM Craft 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1005 위 그림에서 2번, 3번 건물은 1번 건물이 완료되어야 건설을 시작할 수 있다. 4번 건물은 2번, 3번 건물이 완료되어야 건설을 시작할 수 있다. 따라서 각 node에 들어오는 화살표 (in-degree)가 작은 순서대로 건설이 시작된다. 이런 문제는 위상 정렬을 이용해서 풀 수 있다. 1번의 경우에는 들어오는 화살표가 없으므로 in-degree가 0이다. 2, 3번의 경우는 in-degree가 1이며, 4번은 2가 된다. 입력받을 변수와 in-degree를 저장할 배열, 그리고 건설 시간을 저장할 배열, 답을 저장할 배열을 선언한다. ans[node] = 해당 node 건물이 완료될 때 까지 걸린 시간이다. #.. 2021. 7. 14. BOJ 2531, 15961 : 회전 초밥 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2531 https://www.acmicpc.net/problem/15961 BOJ 2531 : 2 ≤ N ≤ 30,000 BOJ 15961 : 2 ≤ N ≤ 3,000,000 초밥의 종류가 가장 최대가 되도록 모두 구해보면 된다. 이 과정에서 슬라이딩 윈도우를 사용해야 N이 3,000,000인 경우에도 시간 내에 처리할 수 있다. 초밥 벨트에 놓인 접시를 담을 배열 arr와 먹은 초밥을 저장할 table 배열을 선언하자. 초밥의 가짓수가 최대 3000이므로 3000이상으로 잡는다. int arr[3010000]; int table[3100]; 회전 초밥이기 때문에 arr의 N ~ N + k 까지 앞부분의 초밥을 추가한다... 2021. 7. 4. BOJ 2096 : 내려가기 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2096 메모리가 4MB로 매우 작은 상태에서 다이나믹 프로그래밍으로 문제를 풀어야 한다. 아래의 4개의 배열로 문제를 풀 수 있다. int A[4]; /* 작은 값 저장 */ int B[4]; /* 큰 값 저장 */ int C[4]; /* 입력 값 */ int D[4]; /* temp 값 */ N번째 내려가기를 했을 때 얻을 수 있는 최소값은 3가지 경우로 나뉜다. 세 개의 수 중 첫 번째 수를 선택한 경우 - 이전 값에서 첫 번째 수/두 번째 수를 선택한 경우. 두 번째 수를 선택한 경우 - 이전 값에서 첫 번째 수/두 번째 수/세 번째 수를 선택한 경우. 세 번째 수를 선택한 경우 - 이전 값에서 두 번째 수/세 번째.. 2021. 6. 26. BOJ 1212, 1373 : 8진수 2진수, 2진수 8진수 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1212 https://www.acmicpc.net/problem/1373 8진수 0 ~ 7를 2진수로 변경하면 아래와 같다. 0 → 000 1 → 001 2 → 010 3 → 011 4 → 100 5 → 101 6 → 110 7 → 111 따라서 str8['8진수 문자열 0 ~ 7']이 000 ~ 111이 되도록 memo 해서 출력만 하면 된다. 단, 가장 처음에 나오는 8진수 0 ~ 3의 경우, 앞의 0은 출력하지 않기 때문에 예외 처리를 한다. #include char str[1001000]; int main(void) { char str8['9' + 1][5] = { 0 }; str8['0'][0] = '0'; st.. 2021. 6. 21. BOJ 1016 : 제곱 ㄴㄴ 수 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1016 에라토스테네스의 체와 같은 방법으로 구할 수 있다. 소수의 배수를 모두 지우고 남은 수가 소수가 되는 것처럼 제곱수의 배수를 모두 지우면 제곱 ㄴㄴ 수가 남게 된다. 1,000,000,000,000의 수에 대해 모든 제곱 ㄴㄴ 수를 구할 수 없으므로, MIN ~ MAX (최대 1,000,000 차이)까지만 구하면 된다. 따라서 100만개의 수 중 제곱 ㄴㄴ수를 구분하기 위해 배열을 100만개 잡는다. check[number] = 0 인 경우가 제곱 ㄴㄴ수이다. 이때, MIN번 째 수가 제곱 ㄴㄴ 수 인지 여부는 check 배열의 0번째 index를 본다. int check[1000100]; /* 0 = 제곱 ㄴㄴ .. 2021. 6. 18. 이전 1 2 3 4 5 6 7 ··· 10 다음 반응형
