.

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 2178번 미로탐색, 2667번 단지번호붙이기와 마찬가지로 이 문제도 bfs를 이용하면 된다. 자세한 코드 설명은 링크 참조 bfs를 진행하며 그림이 몇 개의 영역으로 보이는지 출력. bfs : 인접한 좌표에 현재 색과 같은 색이 있으면 방문한다. 두 가지 결과를 출력해야 한다. 적록색약이 아닌 경우 arr초기화 -> (0,0)부터 탐색 시작, 방문 안 한 좌표 bfs탐색 -> ..

문제https://www.acmicpc.net/problem/2667과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/2667" data-og-url="https://www.acmicpc.net/problem/2667" data-og-image="https://scrap.kakaocdn.net/dn/cdG7bK/hyVDxuEAXI/vTqCVxrjwqXxXpTFScZbIK/img.png?width=2834&height=1..

문제 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net N을 입력받고 N의자리수 중 신기한 소수에 해당하면 출력한다. 신기한 소수란? 예) 373은 신기한 소수다. 3도 소수, 37도 소수, 373도 소수이기 때문. 뒷자리부터 검사 (N자리수에 해당하는 모든 숫자 검사) - 시간 초과 처음에는 N의 자리에 해당하는 모든 수를 신기한 소수인지 검사하는 코드를 짰다. N의자리 숫자 중 가장 작은 수가 소수인지 확인 소수이면 (숫자/10)이..

문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 무방향 그래프에서 정점과 간선이 주어지고, 연결 요소 개수를 구하는 문제이다. 풀이 연결요소란? 만약 6개의 노드가 있고 위와 같이 간선이 연결되어있다면, 연결 요소는 (1, 2, 5) (3, 4, 6)두 개이다. 연결 요소는 모든 정점을 연결하는 경로를 가지고 있어야 한다. 아이디어 인접 행렬을 만든다. DFS 탐색을 한다. ..

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 최단거리는 BFS로 풀자 최단거리 찾기 문제는 BFS로 풀어야 한다. BFS는 같은 거리에 있는 노드들을 다 처리한 뒤에 다음 거리의 노드를 탐색하러 가기 때문에, 각각의 노드가 시작 노드로부터 얼마나 떨어져있는지 하나 하나 기록해나가며 탐색하면 탐색이 모두 끝났을 때 바로 최단거리를 알 수 있다. 반면 DFS는 분기점이 생길 때마다 마지막 노드까지 갔다가 다시 분기점으로 돌아와서 마지막 노드까지 탐색하기를 반복하기 때문에..

문제https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사www.acmicpc.net단순하게 입력받은 그래프를 dfs, bfs로 탐색한 결과를 출력하는 프로그램이다.풀이dfs는 재귀로, bfs는 Queue 인터페이스를 LinkedList로 구현해 사용했다.인접 행렬 : 그래프 각 정점 사이의 간선을 배열로 표현한다. 참고) 인접 행렬을 사용하는 경우, 간선 존재 여부를 상수시간 O(1) 안에 확인할 수 있으나, 정점이 많은 경우 메모리가 낭비된..

문제 https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 풀이 아이디어 첫 번째 줄 : 1/1 두 번째 줄 : 1/2 -> 2/1 세 번째 줄 : 3/1 -> 2/2 -> 1/3 네 번째 줄 : 1/4 -> 2/3 -> 3/2 -> 4/1 ... 홀수번째 줄 : (a/b)에서 a는 내림차순, b는 오름차순으로 변한다. 짝수번째 줄 : (a/b)에서 a는 오름차순, b는 내림차순으로 변한다. X가 몇 번째 줄에 있는 분수인지 구하는 방법: X-1이 2 이하이면 X는 두 번째 줄에 있다. X-1-2가 3 이하이면 X는 세 번째 줄에 있다. ... X가 3번째 줄에 있다면, 그 줄의 ..

문제 https://www.acmicpc.net/problem/2903 2903번: 중앙 이동 알고리즘 상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다. www.acmicpc.net 풀이 i 1 2 3 4 N 한 변에 있는 점 개수 2+2^0 = 3 2+2^0+2^1 = 5 2+2^0+2^1+2^2 = 9 2+2^0+2^1+2^2+2^3 = 17 2+2^0+2^1+...+2^N-1 = X 총 개수 3^2 5^2 9^2 17^2 X^2 코드 import java.util.*; import java.io.*; public class Main { public stat..

문제 https://www.acmicpc.net/problem/2720 2720번: 세탁소 사장 동혁 각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다. www.acmicpc.net 풀이 1) 쿼터를 Q, 다임을 D, 니켈을 N, 페니를 P라고 하자 1.24를 0.25, 0.10, 0.05, 0.01 각각 최소한 몇 개로 구성할 수 있을까? = 124를 25, 10, 5, 1 각각 최소한 몇 개로 구성할 수 있을까? 124에 25가 최대 몇 개 들어갈 수 있는지 구한다. Q = 124/25 = 4 124 - (25 * 4)에 10이 최대 몇 개 들어갈 수 있는지 구한다. C = 124 - (25 * 4) = 24 D = 24/10 = 2 ...

문제 B진법 수 N을 10진법으로 바꿔 출력하는 문제이다. B진법이 만약 10진법을 넘어간다면 A:10, B:11, ..., Z:35로 표현한다. 풀이 문제를 이해하지 못해서 여러 번 읽다가 풀이를 찾아봤다. 'ZZZZZ 36'을 입력받은 경우 : 36진법수로 표현한 ZZZZZ을 10진법으로 바꾼 결과를 출력해야한다. (35 * 36^4) + (35 * 36^3) + (35 * 36^2) + (35 * 36^1) + (35 * 36^0) = 60466175 'ABCD K'을 입력받은 경우 : K진법수로 표현한 ABCD를 10진법으로 바꾼 결과를 출력해야한다. (10 * K^3) + (11 * K^2) + (12 * K^1) + (13 * K^0) 코드 import java.util.*; import ja..