문제 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 여담진짜 바보인가? 왜 자꾸 중요한 조건을 놓쳐서 틀리는걸까 ㅎㅎ.... 풀이 방식 잘 생각해놓고 이렇게 어이없이 틀릴 때마다 답답.. 제발 문제를 똑바로 다 읽고 정리하고 끝까지 확인하는 습관을 가지자!!! 풀이N의 범위(2 ≤ N ≤ 15)도 크지 않기 때문에 완전탐색 방식으로 문제를 풀었다. (다른 풀이를 찾아보니 BFS 방식으로도 풀 수 있는 듯 하다. 이건 나중에..) 가장 고려해야 할 부분은 소용돌이 장애물이다. 소용돌이 장애물은 2초마다 나타나고 1초 사라지는 형식을 띄고 있다.0초&1초: 나타남, 2초: 사라짐, 3초&4초: 나타남, 5초: 사라짐..

문제 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 여담문제를 제대로 읽지 않았다..^^ 주변에 지뢰가 없는 것을 열면 끝이라고 생각했는데, 예시를 보니 "주변에 지뢰가 없는 것을 열었음 → 열은 칸 주변에도 지뢰가 없음 → 연속적으로 해당 칸 열기"를 하는 것이었다. 즉, BFS/DFS 탐색을 통해 푸는 문제였다...ㅎ 문제를 제대로 읽고 해석하는 것도 실력이니 꼭..! 문제를 꼼꼼히 읽자 풀이지뢰가 없는 칸을 모두 여는 최소 터치 횟수를 구하는 문제이고, 주변에 지뢰가 없는 것을 열었는데 새로 열은 칸 주변에도 지뢰가 없다면 연속해서 칸을 열어야 한다. 즉, 지뢰가 없는 칸을 여는 최소 터치 횟수 구하기 & ..

문제https://www.acmicpc.net/problem/1600 여담예전에 풀었던 문제라 그런지 푸는 방식을 약간 외워서 푼 느낌이다. 비슷한 유형의 문제가 나오면 좋겠지만 그럴 확률은 많지 않으니 다양한 BFS/DFS 문제를 접하도록 노력해야지..! 아무튼 이와 같이 기본 조건에 상태에 대한 조건이 추가적으로 있다면 "차원을 추가해서 각각의 상태를 관리"하면 된다는 것을 기억하자! 풀이맨 왼쪽 위에서 맨 오른쪽 아래로 이동하는 최단 거리를 찾는 것이므로 BFS 탐색을 수행하면 된다.  이때, 말처럼 이동하는 횟수에 따라 방문할 수 있는 지점이 달라지므로, 말이 이동한 횟수에 따라 각각 방문 처리를 해줘야 한다. 따라서 방문 처리 배열을 vistied[세로][가로][말처럼 이동한 횟수]와 같이 3차..

13549: 숨바꼭질 3🔗 문제 링크BFS 탐색으로 최소 시간을 구하면 됨순간이동은 0초, X+1 또는 X-1로 이동하는 것은 1초가 걸리므로 순간이동을 먼저 수행하는 것이 좋음더보기24.07.01 풀이import java.io.*;import java.util.*;public class Main { static final int MAX = 100_000; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br...

문제https://www.acmicpc.net/problem/1149 여담예전에 풀었을 때는 풀이를 참고해서 풀었는데 이번에는 스스로 풀었다..! 실력이 크게 는 것 같지는 않지만 그래도 좀 뿌듯 ㅎㅎ 근데 DP 문제라는 것을 알고 있어서 쉽게 풀었지, 몰랐다면 헤맸을 것 같다. 각 유형을 공부한 뒤에 랜덤으로 문제를 푸는 연습도 꼭 해야 되겠다..! 풀이모든 집을 칠하는 최소 비용을 구하기 위해 1번 집부터 N번 집을 칠하는 최소 비용을 누적하여 테이블을 채워 나가면 된다. 이때, 연속된 집은 같은 색으로 칠하지 못한다. 따라서 색칠하는 경우의 수는 다음과 같다.현재 집에 빨간색을 칠하는 경우이전 집은 초록색 또는 파란색이 칠해져 있어야 함dp[i][0] = Math.max(dp[i][1], dp[i]..

1463: 1로 만들기🔗 문제 링크1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우를 각각 나누어서 점화식을 세워야 함1을 빼는 경우의 값으로 초기화: dp[i] = dp[i - 1]3으로 나누어지는 경우의 점화식: dp[i] = Math.min(dp[i], dp[i / 3] + 1)2로 나누어지는 경우의 점화식: dp[i] = Math.min(dp[i], dp[i / 2] + 1)BFS 탐색도 가능할 것 같아서 시도했는데 BFS 탐색으로도 최소 연산 횟수를 구할 수 있음탐색하고 있는 수가 1이 되면 탐색을 종료해야 함dist[N]이 아니라, dist[1]의 값이 N에서 1까지의 최소 연산 횟수이므로 주의할 것!더보기24.06.24 풀이DP 풀이import java.io.*;public clas..

문제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를 사용하는 것으로 방법을 틀었다. 생각보다 시간이 많이 소요됐고 구현하는 것에서 문제가 있었기 때문에 빠른 시일 내에 다시 또 풀어봐야 되겠다..! 풀이이 문제는 그리디 알고리즘을 사용하는 문제로, 가장 중요한 것은 플러그를 빼는 횟수의 최솟값을 얻기 위해 어떤 행동을 해야 하는 가를 떠올리는 것이다. 빼는 횟수의 최솟값을..