본문 바로가기
반응형

알고리즘/BAEKJOON88

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.
BOJ 5465 : 곰돌이 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/5465 queue에는 좌표 (r, c)와 depth(곰이 움직인 거리)를 담을 수 있도록 구조체를 아래와 같이 선언한다. typedef struct st { int r; int c; int depth; }QUEUE; QUEUE queue[MAX * MAX]; int wp, rp; 주어지는 input의 알파벳은 숫자로 변경한다. 그리고 곰돌이의 최초 위치와 도착해야하는 집의 좌표는 따로 (sr, sc), (er, ec)에 저장한다. void input() { int change['Z' + 1] = { 0 }; change['T'] = -1; /* 나무 */ change['G'] = 0; /* 빈 칸 */ change['H'.. 2021. 6. 12.
BOJ 1717 : 집합의 표현 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1717 유니온 파인드를 이용하여 문제를 풀 수 있다. 각 원소들의 부모를 자기 자신으로 초기화하고 입력을 받으면서 집합을 만든다. find를 이용하여 같은 집합에 포함되어 있는지 체크하면 된다. #include int N, M; int parent[1000100]; int find(int x) { if (x == parent[x]) return x; return parent[x] = find(parent[x]); // 경로 압축 } void makeUnion(int x, int y) { x = find(x); y = find(y); if (x != y) parent[x] = y; } int main(void) { scan.. 2021. 6. 10.
BOJ 2606 : 바이러스 (유니온 파인드 Union Find) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2606 유니온 파인드(Union Find)를 이용하면, 원소가 어떤 집합에 포함되어 있는지 알 수 있다. 유니온 파인드에서는 2가지 연산이 필요하다. find(x) : x가 포함된 집합을 찾는다. (root 원소를 찾는다.) makeUnion(x, y) : x와 y가 같은 집합에 포함되도록 합친다. parent[y] = x가 된다. 그리고 각 원소별로 자신의 부모를 저장할 parent 배열이 필요하다. 바이러스 문제는 그래프(링크드 리스트)를 만드는 기본 문제지만, 집합으로도 해결 가능하다. 이 문제에서는 1번 컴퓨터와 연결된 컴퓨터의 수를 찾아야 한다. Find( 2 ~ N ) 과 Find( 1 )의 집합이 같으면 1번.. 2021. 6. 8.
BOJ 2805 : 나무 자르기 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2805 정답을 X라고 가정하자. 즉, X 만큼 자를 때, 적어도 M 미터의 나무를 집에 가져간다. 그러면 X - 1 만큼 나무를 자르면 M 미터 보다 더 많은 나무를 가져가게 되고, X + 1 만큼 나무를 자르면 M 미터 미만의 나무를 집에 가져가게 된다. 따라서 BOJ 1939 : 중량제한처럼 이분 탐색을 이용하여 X를 찾을 수 있다. 먼저 적당한 값 m으로 나무를 잘라보고, 이 값이 M보다 크면 m 보다 큰 값에서 다시 적당한 값을 정한다. 이 값이 M보다 작으면 m보다 작은 값에서 다시 적당한 값을 정한다. 주어지는 나무들의 길이가 1,000,000,000이고 N이 최대 1,000,000이므로, long long t.. 2021. 6. 5.
BOJ 14442 : 벽 부수고 이동하기 2 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/14442  BOJ 2206 : 벽 부수고 이동하기에서 벽을 K번 부술 수 있도록 코드를 수정하면 된다. 최대 10번까지 부술 수 있으므로 visit 배열을 10개 이상으로 만든다.//int visit[2][MAX][MAX];int visit[10 + 2][MAX][MAX]; BFS에서 out.k == 0인 경우를 out.k visit[0]을 visit[out.k]로 visit[1]을 visit[out.k + 1]로 변경한다.if (out.k  최종 코드는 아래와 같다.#include #define MAX (1000 + 10)int N, M, K;int MAP.. 2021. 6. 2.
BOJ 2206 : 벽 부수고 이동하기 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2206  BOJ 2178 : 미로 탐색에서 BFS를 이용하여 길찾기 문제를 해결할 수 있었다.벽 부수고 이동하기의 경우는 벽 1개를 부술 경우 최단 거리가 달라지기 때문에 난이도가 약간 더 높다. 먼저 방문 여부를 위해 visit 배열을 사용한다.이 때, visit[0][MAX][MAX]는 벽을 0번 부순 visit 배열이고,visit[1][MAX][MAX]는 벽을 1번 부순 visit 배열로 가정한다. 아래의 미로에서 (1, 1)부터 미로를 탐색한다고 가정해보자.visit[0]의 (1, 1)은 1로 시작하게 된다. 보통 다음 좌표가 벽이 있는 경우, q.. 2021. 5. 30.
BOJ 11005 : 진법 변환 2 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/11005 BOJ 2745 : 진법 변환의 역연산이다. 여기서 change 배열은 정수를 문자로 바꾸는 역할을 한다. #include int N, B; char ans[10000]; char change[36]; int main(void) { scanf("%d %d", &N, &B); for (int i = 0; i < 10; i++) change[i] = '0' + i; for (int i = 10; i = 0; i--) printf("%c", change[ans[i]]); putchar('\n'); } return 0; } 2021. 5. 26.
BOJ 1939 : 중량제한 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1939 문제의 답이 되는 최대 중량을 X라고 하자. 그리고 두 섬이 연결되어 있는 것은 DFS를 이용하자. 섬 1과 섬 2가 중량 X로 다리를 건널 수 있다면, DFS(X, 섬 1)은 섬 2로 연결된다. 그러면 DFS(X, 섬 1)은 true다. DFS(X + 1, 섬 1)은 반드시 false가 된다. 이유는 문제의 답이 되는 최대 중량이 X이므로, X + 1의 중량을 견딜 다리가 없기 때문이다. 반대로 DFS(X - 1, 섬 1)은 반드시 true가 된다. 중량 X를 견디는 다리는 최대 중량 X보다 작은 값도 견딜 수 있기 때문이다. 따라서 정답 X에 대해 X보다 작거나 같은 값은 섬을 연결할 수 있고, X보다 큰 값은.. 2021. 5. 22.
반응형

티스토리툴바