반응형 백준알고리즘68 [백준] 1920번 - 수 찾기 (Java)(○) https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 선형탐색으로 풀면 시간초과가 발생한다. 이분탐색으로 풀어보자. 1. N개의 수를 입력받아서 오름차순으로 정렬을 해야 한다. 2. M의 수를 하나씩 이분탐색으로 찾아보자. import java.util.*; import java.io.*; /* [백준] 1920번 - 수 찾기 (Java) */ public class Main { static int N.. 2022. 9. 22. [백준] 1541번 - 잃어버린 괄호 (Java) 1. 첫번째 수는 무조건 양수가 온다고 했으니 그 수에서 뺀값이 가장 작으려면 뒤에 -가 붙는 수가 가장 큰수여야 한다. 2. - 기호가 나오면 그 뒤로 나오는 수들을 모두 더해서 음수로 된 최대값을 만들어야 한다. 3. - 기호가 나오기 전까지의 숫자는 계속 더해주다가 - 기호가 나오면 거기서 괄호를 쳐서 모두 더해서 빼면 된다. ex) 55-50+40 = 55 - (50 + 40) = 55 - 90 = -35 10+55-50+40 = 10+55 - (50+40) = 65 - 90 = -25 1. 3개의 구현이 필요하다. 1-1. 입력 받은 문자열을 -를 기준으로 잘라서 문자열 배열에 담는 작업 1-2. 자른 문자열을 +를 기준으로 수를 뽑아내어서 더하는 작업 1-3. 각 취합된 수를 빼는 작업 2. .. 2022. 9. 19. [백준] 2839번 - 설탕 배달 (Java) https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 재귀나 반복문으로 푸는 문제가 아니다. 따라서 수들을 늘어서놓고 법칙을 찾아야 한다. N 3 4 5 6 7 8 9 10 11 12 봉지수 1 2 N / 5 1 2 N % 5 3 4 0 1 2 3 4 0 1 2 N 13 14 15 16 17 18 19 봉지수 3 N / 5 2 3 N % 5 3 4 0 1 2 3 4 1. 법칙성을 찾기 위해 N/5와 N%5의 값들을 구해본다. N 3 4 5 6 7 8 9 10 .. 2022. 9. 14. [백준] 2178번 - 미로 탐색 (Java)(◎) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1. 미로에서 처음에서 끝까지 가는 최단거리를 구하는 문제이다. 2. 미로 입력에 공백이 없으므로 한줄 씩 string 문자열로 받고, 한글자씩 배열로 저장한다. 3. 방문체크를 위한 visited 배열을 준비하고, 첫 시작인 (1, 1)을 true로 설정한다. 4. BFS 알고리즘으로 상/하/좌/우로 탐색해서 1이면 이동하고 0이면 스킵한다. 5. 최단거리를 구하기 5-1. map 배열의 다음 탐색지에 누적거리+1을 덮어쓰면서.. 2022. 9. 6. [백준] 11725번 - 부모의 트리찾기 (Java)(○) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net [첫번째] 1. 입력함수에서 인접행렬로 정점과 간선을 표현하자. 2. 방향이 없기 때문에 양쪽 모두 행렬로 표현해야 한다. 3. dfs 파라미터는 다음 정점 번호를 넘겨주자. 4. 1번의 루트 고정이므로 2번 정점부터 각 정점의 부모 노드가 뭔지 출력하면 된다. 5. 위의 출력 예제에서 2번 정점의 부모는 4번, 3번의 부모는 6번인 셈이다. 6. 1번부터 dfs 탐색을 해서 이미 방문한 노드가 부모인 셈이므로 그 번호를 출력하면 된다. 더보기 import j.. 2022. 9. 3. [백준] 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. [백준] 2468번 - 안전영역 (Java)(○) https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1. 빗물높이는 주어지지 않으니 1~100까지 증가시키면서 섬의 개수를 탐색해서 가장 큰 수를 도출하자. 2. 상/하/좌/우로 탐색하면서 DFS 함수 내부에서 빗물높이와 비교해서 낮으면 스킵하는 식으로 구현하자. 3. 아무지역도 물에 잠기지 않을 수도 있다가 뜻하는 케이스는? 1. 빗물높이를 1부터 시작해서 TC 중 실패하는게 있었다. 2. 아무지역도 물에 잠기지 않을수도 있다는 노트가 빗물높이를 0으로.. 2022. 9. 1. [백준] 10026번 - 적록색약 (Java)(○) https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. R / G / B를 별도의 그룹으로 구분해서 탐색한 결과와 R과 G를 동일 그룹으로 묶어서 탐색한 결과를 도출하는 문제이다. 1. 상하좌우 탐색을 하는 DFS 알고리즘 문제이다. 2. DFS 함수를 2가지 종류로 만들어서 R/G/B를 모두 구분하는 함수와 R-G / B 로 구분하는 함수로 만들어서 순차적으로 호출한다. 더보기 import java.util.*; /* [백준] 10026.. 2022. 9. 1. [백준] 4963번 - 섬의 개수 (Java)(◎) https://www.acmicpc.net/problem/4963 1. 상하좌우대각선까지 탐색해야 한다. 2. w와 h가 0 0이면 테스트케이스를 종료한다. 1. map에서 상하좌우대각선을 탐색한 후 1이면 방문처리한다. 2. 메인함수에서 for문을 돌려서 1을 발견하면 dfs를 돌리고 섬개수를 ++한다. 1. 입력함수를 TC를 while문으로 받고 w와 h가 0이면 break 하는 식으로 구현 2. 확장할 때 새 지점이 섬인지 바다인지 체크하는 구문 빼먹음. if (A[nx][ny] == 0) 더보기 import java.util.*; /* [백준] 4963번 - 섬의 개수 (Java) */ public class Main { static int w, h; static int A[][]; static .. 2022. 8. 31. 이전 1 ··· 4 5 6 7 8 다음 반응형
