URL : https://www.acmicpc.net/problem/10158 [ 문제 푸는 방법 ]처음엔 그림에서 처럼 개미가 경로를 따라가게 코드를 짰다. 경로를 한칸씩 따라가면 시간이 오래 걸리므로 부딪히는 바깥선을 계산했다.그런데 더 좋은 방법이 생각났다. 개미의 X, Y좌표를 분리해서 보니 재미있는 현상이 보였다. 개미가 움직이는 X좌표만 따로 떼어서 보면 개미는 X축을 왔다갔다 왕복한다.그래서 t초 후에 개미가 X축 위의 어디에 있을 지 생각하기 더 쉬워졌다. ( p + t ) / w값을 x라 하겠다. x의 의미는 개미가 p위치에서 t초동안 너비 w를 몇번 움직였는지 계산한 값이다. x값이 홀수이면, 개미는 x = w축에서 x = 0으로 가는 도중에 멈출 것이다. 반대로 x가 짝수이면, 개미는..
주소 : https://www.acmicpc.net/problem/2606 [ 너비우선탐색(BFS) VS 깊이우선탐색(DFS) ]이 문제는 너비우선탐색(이하 BFS) 또는 깊이우선탐색(이하 DFS)로 문제를 해결할 수 있다. 두 가지 탐색방법은 그래프를 탐색할 때 사용하는 알고리즘 기법이다. 여기서 그래프는 간선과 노드로 이루어진 자료구조를 말한다. 이 말은 위 문제의 그림1에 대입해 볼 수 있다. 그림 1은 그래프 자료구조 형태이다. 숫자 1, 2, 3..을 노드라고 부른다. 그리고 각 노드를 연결하는 선을 간선이라고 한다. 그럼 그래프를 탐색하는 두 가지방법(BFS, DFS)를 설명하겠다. 첫번째 BFS는 시작 노드에서 사방으로 퍼지는 형태로 탐색하는 알고리즘이다. BFS를 그림1에 적용하면 아래와 ..
[ 해결 방법 ]제목처럼 플로이드 와셜 알고리즘을 이용해서 풀면된다. 줄여서 플로이드 알고리즘은 다이나믹 프로그래밍을 이용해서 모든 노드간의 최단거리를 구하는 알고리즘이다.다이나믹 프로그래밍을 구현하기 위한 점화식은 dp[i][j] = dp[i][k] + dp[k][j] 이다.여기서 i는 시작 노드, j는 도착 노드, k는 경유할 노드이다.i노드에서 k노드를 경유해서 j노드로 가는 경로가 i노드에서 j로 바로 가는 경로보다 짧으면 위의 점화식을 적용하면 된다. 문제에서 경로정보 중에 불필요한 정보가 들어온다.3 5 1로 들어온 입력 데이터가 나중에 3 5 10으로 들어올 때도 있다. 이 것만 걸러서 플로이드 와셜 알고리즘을 작성해주면 된다.[ 코드 ]#include #define MAX 101#defin..
[ 해결 방법 ]시작 점부터 끝점까지 이중 for문을 돌면서 모두 색이 같은지 판단합니다. 만약 색이 다르다면 이중 for문을 돌던 영역을 9등분해서 다시 이중 for문을 돕니다. 모두 같은 숫자의 종이가 될 때까지 계속 돌면 문제를 해결할 수 있습니다. [ 코드 ]#include #define MAX2500using namespace std;struct point{int x, y;}; int N, Type[3];int board[MAX][MAX]; void InData(){cin >> N;for(int i = 1; i board[i][j];} void DQ(point from, point to){int pcr, cr;pcr = board[from.y][from.x]; for(int y = from.y; y
[ 해결 방법 ]원판이 몇 개가 있든 1번 장대에 원판이 2개가 있는 것처럼 생각하면 된다.1번 장대에 원판이 2개 있다고 생각하면 처리 과정은 3단계이다. 1. 1 -> 22. 1 -> 33. 2 -> 3원판이 n개 있을 때는 어떻게 진행할까?제일 위에 원판 n-1개를 묶어서 움직이면 된다. 물론 그렇게 움직이면 안되지만 일단 가능하다고 생각을 해보자. 그러면 위의 경우처럼 3가지 밖에 안나온다. 앞에서 n-1개의 원판을 2번 장대로 옮긴다고 했는데 어떻게 가능할까? 1번장대에서 n-2개의 원판을 3번 장대로 옮겨놓고 제일 아래 원판을 2번장대로 옮겨놓고 다시 3번장대의 n-2개를 2번으로 옮기면 된다. 이것도 3번만에 가능하다.어떻게 해야할지 감이 오지 않나? 재귀적인 방법이 눈에 들어온다. 처음에 ..
[ 해결 방법 ]1에서 n까지의 합은 아래 식과 같다. 이런 식이 어떻게 나왔는지 살펴보자. 예를 들어 6까지 수를 나타내면 다음과 같다. 1, 2, 3, 4, 5, 6 위의 수열의 합을 다음처럼 쉽게 생각할 수 있다. (1 + 6) + (2 + 5) + (3 + 4) = 7 + 7 + 7 = 21 위 식을 자세히 살펴보면, 괄호 안에 첫번째 값은 1씩 증가하고 두 번재 값은 1씩 감소하기 때문에 계속 값이 같은 것이다.이렇게 같은 합의 갯수가 n / 2개가 있다. 당연히 모든 수열을 두 개씩 짝지었기 때문이다.수열의 개수가 짝수개 일때 아래의 식이 만들어진다.그러면, 수열의 개수가 홀수 개일 때도 위 식이 성립할까? 1, 2, 3, 4, 5, 6, 7이 수열을 다음처럼 배치하자. (1 + 7) + (2..
[ 해결 방법 ]재귀를 이용해서 문제를 풀었다. 재귀함수(시작점, 종료점)처럼 함수를 만들었다. 시작점부터 종료점까지 for문을 돌면서 색이 모두 같으면 그 색을 출력했고 다르면, 시작점부터 종료점까지의 면적을 4등분해서 4개의 재귀를 호출했다. [ 코드 ]#include #define MAX65using namespace std;int N;bool img[MAX][MAX];void div(int sx, int sy, int ex, int ey){bool p_cr, cr;int cnt = 0;p_cr = cr = img[sy][sx];for (int y = sy; y
[ 해결 방법 ]단순 BFS 문제이다. 현재 수빈이의 위치에서 갈 수 있는 방향(X+1, X-1, 2*X)을 큐에 넣고 K가 나올 때까지 계속 반복하면 된다. [ 코드 ]#include #include using namespace std;struct pos{int x, t;};int N, K, Max;queue q;bool visit[200001];int dir[3] = { -1,1,1 };int main(){cin >> N >> K;if (N == K){cout
[ 해결 방법 ]N을 몇 개 진행해보니까 피보니치 수열임을 알았다. 피보나치를 구현할 때 재귀로 구현하면 안된다. 이렇게 구현하면 불필요한 재귀를 호출하기 때문에 메모리 초과가 난다.fibo(10) fibo(9) fibo(8)fibo(8) fibo(7) fibo(7) fibo(6) 위에 그림처럼 fibo(8), fibo(7)을 이미 구했는데 불필요하게 호출한다. N이 커질 수록 이런 일은 더 많이 발생한다.생각해보면 피보나치는 fibo(n) = fibo(n-1) + fibo(n-2)이기 때문에 현재 값을 구하기 위해서 2개의 수만 알면된다. 이전값과 그 이전값. 그래서 변수 3개만 있으면 피보나치를 효율적으로 구현할 수 있다. 마지막으로 모듈러연산의 성질을 이용한다. 성질 1 : (a + b) % n =..