문제https://www.acmicpc.net/problem/2146 여담전에 풀었을 때는 맞았었는데 이번에는 틀렸다 ^^... 각각의 육지에서 탐색을 해야 하는데 한 섬에서 최단 거리의 다리를 찾는 방식으로 수행했었다. 그렇게 하면 최단 거리를 기록하는데 오류가 생기기 때문에 올바른 답이 나오지 않는 것이었다.. 잘 생각해 보면 당연히 틀린 풀이인데 검증하지 않고 무작정 코딩을 해서 그런 것 같다.. ㅜㅜ 풀이섬 사이의 최단 거리를 구하기 위해 BFS 탐색을 수행하면 된다. 우선 섬들이 모두 1로 주어지기 때문에, BFS 탐색을 통해 각 섬을 구분해야 한다.  그 후, 각각의 좌표에서 ((0, 0) ~ (N - 1, N - 1)) BFS 탐색을 수행해서 다른 섬에 도착하는 경우에만 최단 거리를 갱신하면..

문제https://www.acmicpc.net/problem/9466 여담처음에 BFS 방식으로 사이클을 찾으려고 했다가 계속 시간초과가 발생했다. 찾아보니 사이클을 판별할 때는 DFS 탐색을 사용해야 한다고 한다.. 그래프 탐색으로 사이클을 찾을 때는 DFS 탐색 & 배열 2개를 기억하자! 풀이프로젝트를 함께 하고 싶은 학생을 선택한 것을 연결했을 때, 사이클이 발생하면 하나의 팀을 구성할 수 있다.1번 학생이 2번 선택, 2번 학생이 3번 선택1 → 2 → 3 ... (단방향) 사이클을 탐지하기 위해 DFS 탐색 시 방문 여부를 기록하는 visited 배열과 팀 구성 여부를 기록하는 check 배열, 즉 총 2개의 배열을 생성해야 한다. 우선 선택의 결과를 입력받고 팀 구성이 완료되지 않은 학생만 D..

1926: 그림 🔗 문제 링크탐색하지 않았고 그림인 부분일 때 BFS 탐색하기가장 넓은 그림 찾기 ⇒  BFS 탐색하면서 그림의 넓이 구하기 & 탐색이 끝나면 최대 넓이로 갱신하기더보기24.06.17 풀이import java.io.*;import java.util.*;public class Main { static int n, m, maxArea = 0, pictureNum = 0; static int[][] picture; static boolean[][] visited; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStre..

문제https://www.acmicpc.net/problem/1700 여담풀이 방법은 떠올렸지만 구현하는 데에서 많은 시간을 썼다.. 처음에는 substring()을 사용해서 위치를 찾으려고 했는데 생각보다 고려해야 할 것이 많았고, 반례를 잡지 못했다. 다른 분이 ArrayList를 사용한 것을 보고 "이걸 왜 못 떠올렸지..?"라는 생각이 들었고, 결국 문자열에서 ArrayList를 사용하는 것으로 방법을 틀었다. 생각보다 시간이 많이 소요됐고 구현하는 것에서 문제가 있었기 때문에 빠른 시일 내에 다시 또 풀어봐야 되겠다..! 풀이이 문제는 그리디 알고리즘을 사용하는 문제로, 가장 중요한 것은 플러그를 빼는 횟수의 최솟값을 얻기 위해 어떤 행동을 해야 하는 가를 떠올리는 것이다. 빼는 횟수의 최솟값을..

문제https://www.acmicpc.net/problem/14719 여담좀 복잡하게 풀었다는 생각이 들어 다른 풀이를 참고했더니 역시 더 쉬운 방법이 있었다...^^ 시간 차이는 크게 나지 않았지만 다른 방법으로 풀어보니 확실히 내가 풀었던 방법이 더욱 복잡했다는 것을 깨달았다. 언제쯤 정석 풀이로 풀까..ㅎㅎ 그래도 풀었다는 것에 의의를 둬야지! 풀이간단한 버전이 정석으로 푸는 방법 같아서, 간단한 버전에 대해서만 설명을 진행하겠다. 빗물이 고이려면 현재 블록의 높이보다 높은 블록들로 둘러쌓여야 한다. 따라서 현재 블록의 왼쪽과 오른쪽을 탐색해야 한다. 즉, 빗물이 고이기 위해서는 다음의 조건을 모두 만족해야 한다.현재 블록의 왼쪽에 자신보다 높은 블록이 존재하는 경우현재 블록의 오른쪽에 자신보다 ..

11047: 동전 0🔗 문제 링크나누어 주는 동전의 개수가 최소가 되려면 가치가 큰 동전부터 나누어 주면 됨더보기24.06.02 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int n = Integer.parseInt(st.nextToken()); ..

문제https://www.acmicpc.net/problem/16926 여담저번에 풀려다가 복잡해 보여서 넘어갔던 문제..! 어려워 보였는데 차근차근 푸니까 나름 괜찮았다. 달팽이 문제와 비슷한 느낌?! 풀이회전을 1번하는 풀이 과정은 다음과 같다.회전시켜야 하는 그룹의 수(k) 구하기k = min(N, M) / 2min(N, M) mod 2 = 0이므로 가능한 것(0, 0), (1, 1), ... (k, k)를 시작점으로 선택해서 시계 반대 방향(↓ → ↑ ←)으로 회전하기시작점으로 돌아오면 반복을 종료하기우선 하나의 방향을 고정해서 배열을 회전시키다가, 범위를 벗어나거나 이미 기록한 위치면 회전 방향을 변경하기범위를 벗어난 경우: nx = N || ny >= M이미 기록한 위치: rotateArr[n..

문제https://www.acmicpc.net/problem/2961 여담하나의 재료에 포함된 신맛과 쓴맛인 줄 모르고 각각 나눠서 생각해서 헤맸다. 다행히 반례 예제가 주어져서 틀렸습니다를 마주하지는 않았다. 나름 다 정리하고 풀었는데 또 제대로 읽지 않았나 보다.. 차근차근 고쳐나가야지😢 풀이주어지는 재료의 수가 최대 10개이므로, 완전 탐색을 통해 풀이할 수 있다. 각 재료의 신맛과 쓴맛을 배열에 저장한 뒤, 완탐을 수행하면 된다. 풀이 로직은 다음과 같다.재료를 적어도 하나 사용했다면 신맛과 쓴맛의 차이가 더 작은 값으로 갱신하기minDiff = Math.min(minDiff, Math.abs(sTaste - bTaste))모든 재료를 다 탐색했으면 탐색을 종료하기해당 재료를 선택한 경우와 선택..

문제https://www.acmicpc.net/problem/14620 여담방문 처리가 제대로 되지 않길래 잘 작성했는데 대체 뭐지? 했는데 방문 처리하는 좌표의 값을 잘못 넣어준 것이었다.. 이런 실수가 대체 몇 번인지 진짜.. 백준 풀 때 아주 나쁜 습관만 들어서 큰일났다..ㅋㅋ 풀이화단의 한 변의 최대 길이가 10이고, 설치하는 꽃도 3개이므로 완전 탐색과 백트래킹을 사용해서 풀 수 있다. 설치한 꽃의 개수가 3이 될 때까지 완탐(=dfs 메소드)을 수행해서 최소 비용을 구하면 된다. dfs 메소드에서 중요한 부분은 방문 처리를 하는 부분이다. 꽃을 설치할 수 있을 때에만 방문 처리를 해야 하므로, 네 방향의 좌표를 저장하기 위한 배열을 하나 선언한다.Pos[] pos = new Pos[4] 그 후..

D21859. 백만 장자 프로젝트🔗 문제 링크백준의 11501: 주식 문제와 거의 동일한 문제매매가가 제일 높을 때 팔아야 하므로, 뒤에서부터 탐색하기 1 1 3 1 2와 같이 "1일차, 2일차 - 구매, 3일차 - 판매" & "4일차 - 구매, 5일차 - 판매"일 때가 최대 이익인 경우를 고려해야 하기 때문최대 매매가 최대 매매가 > 현재 매매가 ⇒ 구매하기더보기더보기import java.io.*;import java.util.*;class Solution{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in..