그냥 하는 노트와 메모장

* BOJ 3987 - VOYAGER (보이저 1호, https://www.acmicpc.net/problem/3987) [ 분류 없음 ] 지정된 좌표에서 시작해서 상하좌우 방향으로 진행할 때, 가장 많은 칸을 밟을 수 있는 것이 답이 된다. 이전 포스팅과 비슷한 문제이긴 하다. 방향이 좌표당 4개가 있기 때문에 해당 방향으로 또 방문한다면 이를 사이클로 보자. 사이클이 존재한다면 무한히 반복할 수 있기 때문에 Voyager를 출력해야 한다. 단, 그 무한히 반복할 수 있을 때의 처음 방향을 출력해야 한다. 가령 오른쪽으로 시작했을 때 반복이 된다면 아래처럼 출력한다. RVoyager - 코드 #include #include int main() { char board[500][501], dirp[]="U..

* BOJ 6084 - Laserphones (레이저 통신) [ 분류 - BFS ] 이 문제는 비슷한 문제가 있긴하다. 어떤걸 먼저 풀어도 상관은 없다. (거울설치 - https://www.acmicpc.net/problem/2151) 문제에서 요구하는 것은 C에서 C로, 레이저를 쏠 때 필요한 거울의 수다. 단 90도 로만 반사된다. 가령 d방향으로 레이저가 진행하고 있다고 가정해보자. 그렇다면 현재 바라보는 방향을 기준으로 직진, 좌우 밖에 갈 수 없다(180를 반사, 즉 오던 방향으로 쏠 순 없음). ↑ → / → ＼ ↓ → → → * 접근 방법 1. 두 개의 C 중 하나를 Source로 두고, 4 방향으로 레이저를 쏘는 것으로 시작한다. (시작할 때는 어느 방향이라도 가능하기 때문. 2. 막상 발..

* BOJ 5213 - TOTEM (과외맨) [ 분류 - BFS,DFS / 기타 최단경로 알고리즘 ] 주어진 문자들을 어떻게 노드로 정의할 것이며, 어떻게 자료구조를 설정할 것인지 물어보는 문제. 단순 최단경로 알고리즘을 사용한다면 별다를 문제는 없다. 문제에서는 타일은 두 개의 숫자로 이루어진다. 두 개의 숫자는 각자 '칸'을 의미하며 최대가 6이다. 인접한 타일과 같은 숫자로 접점이 있다면 두 타일은 이어져 있다고 볼 수 있다. * 접근 방식 1. 각 타일은 2개의 칸이고, 각 칸의 최대가 6이므로 두자리 수 하나로 퉁칠 수 있다. 2. 입력으로 주어지는 순서는 맨위 좌측 타일부터 맨 아래 우측 타일까지를 주어주므로 indexing 절차가 필요함을 알 수 있다. 즉, 단순 2차원 배열로 두고 접근할 ..

* BOJ 1765 - The Gangs (닭싸움 팀 정하기, https://www.acmicpc.net/problem/1765) [ 분류 - BFS, DFS/ DSU/ Hashing ] 이분 그래프가 여러개 생길 수 있는 구조를 생각하자. 조건에 따르면 특정 Component A에 대해 A의 적은 단 하나 밖에 존재하지 않는다. 따라서 자신의 적을 저장할 자료구조(Hashing)와 친구를 저장할 자료구조(인접 행렬 및 리스트/ DSU)를 정해야 한다. * 풀이 친구를 저장할 때는 인접 행렬 및 리스트로 저장하는 것은 꽤 간단하다. 하지만 적을 저장할 때는 어떻게 해야 할까? 이분 그래프이기 때문에 적을 단 하나만 저장한다. 이를 루트로 두고, 들어오는 데이터에 따라 자신의 적을 읽어들여, 적과 적을 이..

* BOJ 3964 - 팩토리얼과 거듭제곱 (https://www.acmicpc.net/problem/3964) [분류 - Mathematics/ GCD/ Sieve of eratosthenes ] 으음.. 생각해야할 부분이 굉장히 많은 문제다. 사실 어떻게 풀어야하겠다는 접근 자체는 다소 간단하다. 하지만 이 과정에서 발생할 수 있는 Overflow를 까다롭게 다뤄야 풀 수 있다. * 접근 방식 1. n!이 k^i에 나누어 떨어지기 위해서는 k^i = GCD(n!, k^i)이어야 한다. 2. 최대 공약수의 후보를 산출하기 위해서 k^i는 lg(k)의 시간이 걸리는 반면 n!은 lg(n!)이 걸린다. k^i가 lg(k)인 이유는 i제곱꼴은 k의 약수의 승수에 i를 곱하면 되기 때문. 따라서 후보를 추출하..

* BOJ 1103 - 게임 (https://www.acmicpc.net/problem/1103) [ 분류 - DFS/ Dynamic programming ] 여러분이 이 문제가 그래프임을 알았다고 가정하고 정리해보자. 1. 동전은 (0,0) 에서 시작한다. 2. 동전이 있는 지점에 있는 숫자만큼 상하좌우로 이동할 수 있다. 3. 구멍 H에 들어가거나 보드 밖으로 나가는 것도 동전을 움직이는 것으로 간주한다. 따라서 (0,0)부터 시작해서 상하좌우로 움직일 수 있는 곳의 최대치로 이동한다. 이는 memoization으로 구현할 수 있다. 하지만 무한번 움직일 수도 있는데, 바로 사이클이 생기는 경우다. 사이클이 하나라도 생긴다면 그 안에서 계속 움직일 수 있기 때문에 -1을 출력해줘야 한다. 따라서 me..

* BOJ 2981 - 검문 (https://www.acmicpc.net/problem/2981) [ 분류 - GCD ] 수학 개념이 필요한 문제다. 주어지는 N개의 수를 정렬한 수열의 결과를 a1, a2, ..., an 이라 하자. 임의의 정수 M으로 나눴을 때 수열의 나머지를 m라고 할 때, 수식을 아래처럼 나타낼 수 있다. 이에 대해 근접한 원소끼리 차이를 정리해보면, ... 서로 다른 두 원소 차이에 대해 "약수"로 M이 들어가 있는 것을 확인할 수 있다. 따라서 이 차이에 대해 최대공약수를 구하여 그것의 약수를 모두 출력하면 된다. - 코드 #include #include #include using namespace std; int gcd(int p, int q) { if (q == 0) ret..