본문 바로가기
반응형

골드49

[백준] 1253번 - 좋다 (Java)(○) https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net N : 수의 개수 : 1 ~ 2,000 Ai : 정수 : 1 ~ 1,000,000,000 1. N개의 수 중 2개를 골라서 그 수의 합이 다른 어떤 수와 같다면 그 수를 GOOD이라고 한다. 2. 투 포인터를 이용해서 A[i] 값을 순차적으로 M으로 대입해서 투포인터 알고리즘으로 A[s] + A[e] == M 인 경우의 수를 찾는다. import java.io.BufferedReader; import java.io.Input.. 2022. 12. 28.
[백준] 2665번 - 미로만들기 (Java) https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 검은 방을 변경하는 로직을 어떻게 가져 가야할 지 고민이 되었다. 처음엔 백준 14502 연구소 문제와 비슷한 유형으로 생각하고 아이디어를 생각해보았다. 랜덤하게 검은방 하나씩 변경하고 BFS탐색을 하는 식으로 진행해 봤는데 14502와는 차이점이 그 문제는 문 3개가 되면 탐색을 시작한다는 명확한 재귀탈출 조건이 있었고, 이 문제는 조건 세우기가 애매했다. 검은방의 위치, 갯수... 랜덤하게 진.. 2022. 10. 27.
[백준] 9663번 - N-Queen (Java) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹의 대표 문제이다. 퀸은 상하좌우 대각선으로 거리제한 없이 움직일 수 있다. 그 동선에 걸리지 않도록 다른 퀸을 N개 배치를 하는 경우의 수를 구하는 문제이다. 각 행별로 놓을 수 있는 위치가 발견되면 재귀호출을 해주고, N개 만큼 배치가 되었다면 count+1을 해준다. * 두가지 문제 1. 재귀호출을 어떤 방식으로 할 것인가 2. 퀸을 놓을 수 있는 위치인지 어떻게 판단할 것인가 * 체스판의 퀸을 일차.. 2022. 10. 13.
[백준] 3055번 - 탈출 (Java) https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 지도는 R행 C열로 이루어짐. 비어있는 곳 '.' 물이 차있는 곳 '*' 돌은 'X' 비버의 굴은 'D' 고슴도치의 위치는 'S' 고슴도치는 매분마다 인접한 상/하/좌/우의 칸 하나로 이동할 수 있다. 물도 매분마다 인접한 비어있는 칸으로 확장한다. (이것도 상/하/좌/우?) 물과 고슴도치는 돌을 통과할 수 없다. 고슴도치는 물로 차있는 지역으로 이동할 수 없다. 물도 비버의 굴로 이동할 수 없다. 고슴도치는.. 2022. 10. 5.
[백준] 9935번 - 문자열 폭발 (Java) 1. 문자열을 폭발문자열로 split 한 다음 머지하자. 2. 머지한 문자열을 다시 재귀호출하자. 2-1. 문자열에서 폭발문자열이 없으면 문자열 리턴 2-1. 문자열의 사이즈가 0이면 "FRULA"리턴 import java.util.*; import java.io.*; /* [백준] 9935번 - 문자열 폭발 (Java) */ public class Main { static String str, bom; void InputData() { Scanner in = new Scanner(System.in); str = in.next(); bom = in.next(); } String DFS(String s) { if (!s.contains(bom)) { if (s.length() == 0) return "FR.. 2022. 9. 21.
[백준] 1753번 - 최단경로 (Java) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 다익스트라 알고리즘을 사용 2. 정점은 인접행렬로 구성하고, 방향이 있는 그래프이니 s -> e만 배열에 저장할 것. import java.util.*; /* [백준] 1753번 - 최단경로 (Java) */ public class Main { static int V, E, K; static int[][] map; static int[] visited; .. 2022. 9. 14.
[백준] 1707번 - 이분 그래프 (Java) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. 먼저 이분그래프에 대해 알아보자. 2. 인접한 정점은 다른 색상으로 저장하자. (1 or 2) 3. 방문하려는데 동일한 색상이 이미 칠해져 있으면 이분그래프가 아니다. 4. DFS(정점번호, 색상)을 넘겨주자. import java.util.*; /* [백준] 1707번 - 이분 그래프 (Java) */ public class Main { static int K, V, E; static in.. 2022. 9. 13.
[백준] 14502번 - 연구소 (Java)(△) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 바이러스가 퍼지는 걸 막으려면 벽을 세워야 하는데 벽의 개수는 3개이다. 2. 바이러스가 상하좌우로 번질 수 있다고 하니 BFS에서 큐에 넣은 것은 바이러스의 위치이다. 2-1. BFS 호출 전에 for문을 돌려서 바이러스(2)를 다 큐에 넣자. 3. 이 문제는 탐색을 2번을 해야 한다. (벽 3개를 세우는 경우의 수, 바이러스 확산의 경우의 수) 3-1. 벽 3개를 완전탐색(DFS)해서 하나씩 세우다가.. 2022. 9. 12.
[백준] 1987번 - 알파벳 (Java)(○) https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1. 세로 R, 가로 C로 된 맵이 있고, 대문자 알파벳으로 채워져 있음. 2. (1, 1)에 말이 있는데 상/하/좌/우로 움직일 수 있음. 그런데 이동한 칸의 알파벳은 이전 위치의 알파벳들과 달라야지 이동이 가능함. 3. 칸을 지날 때 마다 알파벳을 저장하는 배열이 필요하고, 새 알파벳과 비교하는 함수가 필요함. 4. 방문배열도 당연히 필요함. 5. dfs함수 파라미터는 좌표를 넘겨주자... 2022. 9. 2.
반응형

티스토리툴바