목록Algorithm/baekjoon문제풀이 (70)
Dolphins의 HelloWorld
문제 링크 : https://www.acmicpc.net/problem/11725 #include #include #include #define SIZE 100001 using namespace std; vector tree[SIZE]; //주어진 트리 int ans[SIZE]; //ans[i]는 i 노드의 값을 의미 bool check[SIZE]; //방문한 노드를 check void function() { queue q; q.push(1); // node 1 부터 시작하므로 큐에 push check[1] = true; //1번 노드는 방문했으므로 check while (!q.empty()) { int x = q.front(); q.pop(); //큐에서 하나 꺼냄 for (int i = 0; i < ..
문제 링크 : https://www.acmicpc.net/problem/2146 #include #include #include using namespace std; int map[100][100]; //지도 int group[100][100]; //섬 별로 그룹화한 모습 int dist[100][100]; //거리 int N; //지도의 크기 int cnt = 0; //그룹화 하기위한 변수 int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,1,-1 }; void grouping(int x, int y) { //BFS를 통해 각각의 섬을 그룹화 한다. group[x][y] = ++cnt; //첫번째 좌표 group값 cnt로 설정 dist[x][y] = 0; //dist값은 ..
문제 링크 : https://www.acmicpc.net/problem/7576 #include #include #include using namespace std; int arr[1000][1000]; int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,1,-1 }; int N, M; int result; void BFS(queue *q) { result = 1; //가장 마지막 날을 저장하기 위한 변수 while (!(*q).empty()){ int x = (*q).front().first; int y = (*q).front().second; (*q).pop(); for (int i = 0; i < 4; i++) { //for문이 한번 돌 때마다 아직 익지 않은 인접 토마토..
문제링크 : https://www.acmicpc.net/problem/2178 이 문제에서는 BFS를 쓰면서 길이를 같이 계산할 수 있는 장치를 함께 두어야한다. 길이를 구하기 위해 만약 현재 좌표에서 갈 수 있는 다음 좌표가 아직 탐색되지 않았다면 현재좌표 + 1을 다음 좌표에 주는 방식으로 진행하였다. 그렇게 진행하다 보면 도착점이 탐색되자마자 설정된 숫자가 최단 길이가 된다. #include #include #include using namespace std; int arr[100][100]; int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,1,-1 }; int N, M; int BFS() { queue q; q.push(make_pair(0, 0)); int x, y..
문제링크 : https://www.acmicpc.net/problem/2667 BFS를 사용하여 문제를 풀어보았다. 반복문을 돌며 만약 해당 좌표에 아파트가 있다면 그 좌표를 중심으로 BFS를 수행하였다. 그리고 숫자를 세면서 검사한 좌표를 모두 0으로 바꿔주어 중복하여 세지 않도록 하였다. 이런식으로 하게되면 BFS를 한번 돌렸을 때 해당 단지의 숫자를 알게되며 그 단지의 좌표는 모두 0이 되기 때문에 한번 검사했던 단지의 아파트를 다시 검사하지 않게 된다. 이런식으로 끝까지 검사를 수행하면 원하는 답을 얻어낼 수 있다. #include #include #include #include using namespace std; int arr[25][25]; int dx[4] = { 1,-1,0,0 }; in..
문제링크 : https://www.acmicpc.net/problem/9466 생각보다 푸는데 어려움을 느꼈던 문제이다. 원래 DFS를 푸는 방식을 조금 변형할 필요가 있다. 예를들어 1 -> 3 , 3 -> 5, 5 -> 3 이라고 가정할 때 기존의 방법대로 탐색을 하면 1 -> 3 -> 5 에서 5의 다음 노드가 3이고 3은 이미 지나간 노드이기 때문에 이제 처리를 해야한다. 여기서 이 문제만의 독특한 점은 이 탐색 안에서 따로 cycle을 찾아야한다는 것이다. 그러니까 위의 예시로 치면 3 -> 5 -> 3을 발견해야하며 숫자가 많아질 수록 복잡해질 것이다. cycle을 어떻게 찾을까에 대해 생각해보면 명확한 점은 한번씩 탐색을 한 다음 이미 지나간 노드라고 처음 인식한 지점이 실제 cycle의 첫..
문제 링크 : https://www.acmicpc.net/problem/2331 수열중에서 만약 새로 나온수가 이전에 나온수와 하나라도 같게되면 무조건 반복될 것이기 때문에 나는 일단 map함수를 사용하여 새로 나오는 수를 key, 누적 갯수를 value로 해서 수열의 숫자가 누적 갯수를 함께 가지고 있도록 하였다 그래서 만약 같은 숫자가 나온다면 그 숫자가 가지고있는 value에서 -1한 값을 결과값으로 내놓도록 하였다 #include #include using namespace std; int pow(int x, int p) { //각 자릿수를 p만큼 곱하도록 하는 함수 int ans = 1; for (int i = 0; i < p; i++) { ans = ans * x; } return ans; }..
문제링크 : https://www.acmicpc.net/problem/10451 #include #include using namespace std; int arr[1001]; bool check[1001]; int point; //맨 처음 cycle이 시작한 시작점 저장 bool DFS(int start) { check[start] = true; int next = arr[start]; if (check[next] == false) return DFS(next); //다음 노드가 탐색된 노드가 아니라면 탐색 else { //다음 노드가 이미 탐색된 노드일 때 if (next == point) return true; //시작 노드와 다음 노드가 같다면 cycle이 맞음 else return false; ..
문제링크 : https://www.acmicpc.net/problem/1377 먼저 이 문제에서 출력하고자하는 i가 무엇인지에 대해 분석을 하면 버블소트를 하면서 정렬이 된 시점을 말한다는 것을 알 수 있다. 즉 버블소트로 1번 돌렸더니 정렬이 다 된다면 i = 1, 2번 돌렸더니 정렬이 다 된다면 i = 2가 되는것이다. 어떻게 하면 버블소트를 돌리지 않고 i를 구할 수 있을까를 알아보기 위해 버블소트가 작동하는 과정을 한번 주목해서 보자 문제의 예제대로 한다면 10 1 5 2 3 i = 1 1 5 2 3 10 i = 2 1 2 3 5 10 이런식으로 최종 정렬이 되는데 우리가 알 수 있는것은 큰 숫자는 한번에 끝까지도 이동할 수 있지만 작은 숫자는 한번 버블소트가 돌 때 한칸씩밖에 움직이지 못한다는 ..
문제 링크 : https://www.acmicpc.net/problem/11004 sort함수를 쓰는 방법에 대해서만 알고 있다면 크게 어렵지 않은 문제이다. sort함수 사용법 : http://dolphins-it.tistory.com/108 #include #include #define SIZE 5000000 using namespace std; long long tmp[SIZE]; int main() { long long N, K; scanf("%lld %lld", &N, &K); for (int i = 0; i < N; i++) scanf("%lld", &tmp[i]); sort(tmp, tmp + N); printf("%lld\n", tmp[K - 1]); }