컴맹에서 개발자 되기

백준 16197 두 동전 완전탐색으로 푸는 문제였고, 나는 자신있는 BFS로 풀었다. www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 풀이 방법 1) 원래 BFS 방법으로 푸는 건 똑같지만, 벽을 만나면 원래 좌표를 가져오는 것이 중요한 문제였다. 2) 원래 좌표를 사용하기 위해 cur 라는 구조체 변수를 한 개 두고, 현재 좌표를 가져왔다. #include #include #include using namespace std; int dx[5] = {1,0..

백준 2447 장군 재귀(recursion)와 분할 정복(divide and conquer)을 이용해야 되는 문제이다. 오랜만에 문제를 풀다보니 상당히 애를 먹었던 문제였다 ㅠㅠ www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 풀이 방법 1) 3*3 가운데가 뚫린 사각형이 존재하는 사각형이 반복되는 형태이다. 2) 이 문제를 해결하기 위해, 따로 2차원 배열을 생성하여 *문자를 저장하는 방법과 바로 출력하는 방법이 존재한다고 생각했..

백준 16509 장군 BFS를 이용한 문제이다 www.acmicpc.net/problem/16509 16509번: 장군 오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 www.acmicpc.net 풀이 방법 1) BFS를 통해 이동할 수 있는 거리를 탐색한다. (대각선 방향) 2) 큐에 넣기 전에 이동 경로에 장기가 있는지 확인한다. (이동 경로에 장기가 있다면 큐에 넣지 않는다) #include #include #include #include using namespace std; int dx[10] = {-3,-3,-2, 2, 3, 3, 2, -2}; int dy[..

백준 2638 치즈 BFS를 이용한 문제이다. https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 풀이 방법 1) 외부 공기와 내부 공기를 분리한다. (BFS 사용) - 함수명 outsideBFS() - 문제 조건에 맨 가장자리는 치즈가 놓이지 않는다고 했으니, 0,0을 큐에 넣어서 외부 공기를 체크한다. - 여기에 체크되지 않은 공간은 외부 공기가 아니다. 2) BFS를 통해 녹을 수 있는 치즈를 체크한다. - 함수명 : BFS => m..

백준 1600 말이 되고픈 원숭이 BFS를 이용한 문제이다. 말이 이동하는 경우, 원숭이가 이동하는 경우를 모두 계산해서 풀면 된다. https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다. www.acmicpc.net 풀이 방법 1) 3차원 배열을 이용해서, 말처럼 이동하는 경우를 고려해야한다. 2) 말 처럼 이동하는 경우만 ..

백준 1629 곱셈 재귀로 풀어야 풀 수 있는 문제이다. 재귀에 약한 나는 고생을 많이 했다 ㅠ https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 방법 1) 이 문제의 시간제한은 2초이다. 1초에 3~5억 번의 연산을 한다고 가정하면, 2초는 10억 번 안에 연산을 끝내야 한다. 2) 최악의 경우 O(n)이라면, 문제의 주어진 수가 최대 21억이기 때문에 시간 초과가 뜨게 된다. 3) 즉, O(n) 보다 낮은 알고리즘을 이용해한다. 4) b를 짝수 일 때, 홀수 일 때를 나눠서 생각해본다. 2^10이면 b..

백준 2644 촌수계산 완전 탐색 문제이다. https://www.acmicpc.net/problem/2644 문제풀이 1) 주어지는 좌표(촌수)에 대한 그래프를 생성한 후, 시작 좌표(촌수) 끝 좌표(촌수)의 거리를 구하면 되는 문제이기 BFS, DFS 둘 중 하나를 쓰면된다. 2) 나는 BFS가 더 편하기에 BFS를 사용했다.. #include #include #include #include #include using namespace std; int a[102][102]; queue q; int check[102]; int n, s, e, m, x, y; void input_data() { cin >> n >> s >> e >> m; for (int i = 0; i >..

백준 9466번 텀 프로젝트 시간초과에 주의해야되는 문제이다. https://www.acmicpc.net/problem/9466 풀이 방법 1) 한번에 탐색만에 사이클이 있고, 없고를 판단하면서 지나가야한다. 2) 1->2->3->4->5->4 라는 것이 있으면 4,5가 사이클이다. 여기서 4,5가 사이클임을 파악해야되고, 6번으로 바로 넘어가야 시간초과가 뜨지 않는다. #include #include #include #include using namespace std; int ans; int visited[100000]; //방문횟수 담는 배열 bool check[100000]; // 사이클을 찾았다는 뜻 int student[100000]; int T, number; void input_data() ..

백준 6593 상범 빌딩 3차원 bfs문제이다 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net 풀이 방법 1) bfs로 해결하면 된다. 2) 큐, 배열 초기화 잊지 말자 ! #incl..

백준 2146번 다리 만들기 BFS로만 풀 수 있지만, DFS와 BFS 둘 다 이용할 수 있는 문제이다. https://www.acmicpc.net/problem/2146 풀이방법 1) 각 나라를 구분짓기 위해 bfs나 dfs를 사용한다. 나는 bfs를 사용했다. 2) 각 나라를 구분지은 후, 나라와 나라 사이의 최단거리를 BFS로 구한다. 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 ..