Algorithm/BaekJoon

[JAVA] 백준 1963 : 소수 경로

문제 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 해결방법 문제를 읽어보면 가능한 비밀번호는 1000 ~ 9999 사이의 숫자이다. 그렇기 때문에 에라토스테네스의 채를 이용해서 9999까지의 소수를 찾아내고 현재 비밀번호에서 각 자리수를 하나씩 변경하며 그 수가 소수라면 다음으로 또 한자리는 변경하는 방식으로 목표 비밀번호까지 최소한의 횟수를 찾는 문제이다. 순서를 정리하면 1. 9999까지 소수를 찾는다. 2. 각 자리수를 변경하며 목표 비밀번호를 찾는데, 거쳐가는 비밀번호도 모두 소수인지 확인해야한다. 추가적으..

[JAVA] 백준 12781 : PIZZA ALVOLOC

문제 12781번: PIZZA ALVOLOC 입력의 첫 줄에는 도윤이와 친구들이 선택한 점의 좌표 x, y(-10,000 ≤ x, y ≤ 10,000)가 순서대로 4개 주어진다. x, y값은 항상 정수이다. www.acmicpc.net 해결 방법 CCW (Counter-ColockWise) 라는 알고리즘을 쓰는 문제인데, 처음 보는 알고리즘이라 기록해둘 겸 글을 작성하게 되었다. CCW는 '평면에 놓여진 세 점의 방향 관계를 구하는 알고리즘' 인데 CCW 식을 사용해서 양수가 나오면 이 그림과 같이 시계 반대 방향으로 향하는 방향 관계를 가지고 있다고 하고, 음수가 나온다면 이와 같이 시계 방향으로의 관계를 가지고 있다고 알 수 있다. 그러면 0이 나오는 경우는 뭘까? 그때는 세 점의 관계가 평행 즉, ..

[JAVA] 백준 1922 : 네트워크 연결

문제 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이방법 한 정점에서 모든 정점을 연결하는데에 드는 비용을 최소로 하는 문제이다. 크루스칼과 프림을 사용할 수 있는데, 프림을 안써본지 오래되어서 프림으로 코드를 구성해보았다. 인접리스트로 양방향 연결을 먼저 해준다음 임의의 시작점에서 출발시키면된다. 프림은 방문배열과 각 정점의 최소비용을 저장할 정점 크기만큼의 1차원 배열을 사용한다. 최소비용을 저장할 배열은 최대값으로 초기화해준다. 필자는 우선순위큐를 활용한 프림을 구성하였는데, 그렇기 때문에 비용에 따라 오름차순 정렬을 통해 비용이 적은 것 부터 탐색하도록하였다. 임의의 시작 정점을 정하였..

[JAVA] 백준 1194 : 달이 차오른다, 가자.

문제 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 해결방법 방문 체크가 중요한 문제이다. 열쇠가 a ~ f 가 존재하고 각 열쇠에 해당되는 문이 A ~ F가 존재한다. 방문 체크를 열쇠를 아예 들고 있지 않을 때, a만 들고 있을 때, a와 b를 들고 있을 때 등으로 나누어서 체크를 해주어야 한다. 그렇게 하면 총 6개 열쇠를 모두 방문 체크를 해주어야 되기 때문에 좌표값 + 6 해서 8차원 배열을 사용해야 한다. 그래서 비트 마스크를 사용한다. 비트마스크를 사용하면 아예 사..

[JAVA] 백준 2636 : 치즈

문제 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 해결 방법 조금 생각할 것이 있는 구현 문제이다. 필자는 다음과 같은 순서로 문제를 해결했는데, 1. 배열의 (0, 0) 부터 빈 공간인 0을 탐색, 만약 0의 상하좌우에 치즈 즉, 1이 있다면 Queue에 넣음. 모든 공간을 다 탐색하면 Queue에 넣어진 치즈들이 한 시간 후 녹을 치즈들이 됨. 재귀를 통해서 모든 치즈들이 없어질 때까지 탐색을 계속함. 2. Queue에서 치즈를 꺼내면서 빈공간으로 바꿔주면서 상하좌우에 있는 치즈를 찾음. 만약 치즈가 있다면 다..