[GAEBAL Blog]

문제 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 풀이 쉬운 그래프 탐색 문제 ! 인접 리스트 배열로 풀든, 인접 행렬로 풀든 상관은 없을 것 같음! 방문하지 않은 노드가 있으면 dfs를 시작하고 그 안에서 연결이 되어있고 방문하지 않은 애들이면 탐색을 시작함 자세한건 주석으로! 코드 // 11724번 연결 요소의 개수 // https://www.acmicpc.net/proble..

문제 https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 풀이 쉬운 문제인듯? 걍 문제대로 풀면 됨 나는 그냥 문제대로 풀었지만, dfs로 depth == 2 면 탈출하게 해서 풀어도 될 듯??? 자세한건 주석으로! 코드 // 5567번 결혼식 // https://www.acmicpc.net/problem/5567 package BAEKJOON; import java.io.BufferedReader; import java.io.IOE..

문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si { // (o1, o2): 오름차순으로 정렬한다 if (o1[0] == o2[0]) { return Integer.compare(o1[1], o..

문제 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 전에 비슷한 문제를 풀어봤던 것 같다! 암튼 그래서 쉽게 풀었음 ㅎㅎ 동적계획법 문제가 나오면 평소처럼 생각하지 말고 거꾸로 생각하거나 밑에서부터 계산해보거나 처음 결과를 가지고 다음 계산에 이용한다거나 등의 접근 방식이 필요하다 이 문제에서는 위에서 아래 층으로 내려온다고 나와있지만 밑에서 부터 올라가는 식으로 계산을 하면 어떨까... 하는 생각으로 풀었다! 자세한건 주석으로! 코드 // 1932번 정수 삼각형 // https://www.acmicpc.ne..

문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 최소한으로 부술 수 있는 벽의 개수를 구해야 하는 문제이다. 문제를 읽자마자 최소 비용(벽의 개수) 문제라는 것을 알아서 다익스트라 알고리즘이 떠올랐다. 전에 풀었던 https://seokmimmmmmmmm.tistory.com/84 [백준]4485번 녹색 옷 입은 애가 젤다지? - Java 문제 https://www.acmicpc.net/problem/4485 4..

문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 처음에 연산자 뿐만 아니라 숫자들도 다 자리를 바꿀 수 있는 줄 알고 대략적으로 시간 복잡도를 계산하고 있었는데 너무 어마무시하게 나와서 헤맸다,,, 근데 다시 읽어보니까 숫자는 고정이고 연산자만 위치를 바꾸면 되는 문제였다... ㅎㅎㅎ 나새끼 문제 좀 잘 읽자 완전 탐색으로 다 돌려보면서 탈출 조건(index == N)이 되면 최..

문제 https://www.acmicpc.net/problem/1347 1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net 풀이 지금까지 풀었던 문제들은 미로라면 미로, 지도라면 지도가 주어지고 그 미로나 지도 위에서 찾고자하는 무언가를 찾는 방식이였는데 이 문제는 이동한 칸이 먼저 나오고 미로의 모양을 출력해야 되는 문제라 신박했다. 포인트는 제한사항에서 홍준이가 적은 내용의 길이가 0보다 크고 50보다 작다고 적혀있어서 미리 미로의 최대 크기를 정해놓고 접근해야 함 지도의 시작점과 끝점을 이동할 때마다 최신..

문제 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 풀이 프로그래머스에서도 비슷한 문제를 풀었던 것 같다! 포인트는 맵을 이용해서 같은 종류의 옷이면 갯수를 증가시켜주어야 한다는 것 (HashMap.put(key, HashMap.getOrDefault(key, 0) + 1) 얘를 잘 알아놓자!) 마지막에 옷의 종류가 한가지일 경우와 한가지 이상일 경우..

문제 https://www.acmicpc.net/problem/17073 17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net 풀이 처음엔 무슨 소린가 했는데 결국 리프 노드(자식이 없는 노드)의 수로 총 빗물의 양을 나눠주면 답이다! 그러므로 리프 노드를 어떻게 판별할지가 포인트인데, 트리에선 자신과 연결된 노드가 하나밖에 없는 경우가 리프 노드이다. (2개 이상이 연결되어 있으면 자식 노드가 존재하는 것이니까) 이 점을 이용하여 풀었다. 자세한건 주석으로! 코드 // 17..

문제 https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 풀이 피보나치 수열을 응용한 문제임 피보나치나 뭐 파도반 수열인가 이런거처럼 메모리가 초과될 위험이 있을 것 같다? 그럼 문제의 조건이나 문제를 잘 읽어서 대충이라도 시간복잡도를 계산해보고 괜찮겠다 싶으면 해야된다. 안 괜찮으면 DP 등으로 풀어야 됨. 이 문제는 순열에다가 피보나치 수열이라서 가지치기와 DP로 어떻게 푸냐가 포인트임! 3

문제 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 풀이 며칠 전에 푼 '탈출'이라는 문제랑 완전 비슷하다!!! https://seokmimmmmmmmm.tistory.com/123 [백준]3055번 탈출 - Java 문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 ..

문제 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 시뮬레이션 문제이다. 주사위를 어떻게 굴릴지만 구현하면 된다! 나는 주사위 전개도를 2차원 배열로 보고 동서북남 방향으로 굴릴 경우, 어떻게 전개도가 바뀔지 생각해서 구현했다. 1차원 배열 2개로 전개도를 구현하거나, 클래스를 만들어서 주사위의 윗면, 아랫면, 앞면, 뒷면, 왼쪽면, 오른쪽면을 구현해도 같은 결과를 얻을 ..

문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 bfs 문제임! 주의할 점은 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 이렇기 때문에 물을 먼저 bfs로 퍼지게 하고 그 후에 고슴도치를 bfs로 이동시켜야 한다! 나는 큐를 두개 만들어서 풀었지만 큐 하나로도 가능할 것 같다!! 자세한건 주석으로! 코드 // 3055번..

문제 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 풀이 걍 흔한 dfs나 bfs 문제이다! 나는 dfs로 풀었음! 정답은 음식물 쓰레기의 최대 크기이므로 static 변수로 선언해서 dfs한번이 끝나면 음식물 쓰레기의 크기를 측정하여 최신화해주는 방식을 사용했다. 자세한건 주석으로! 코드 // 1743번 음식물 피하기 // https://www.acmicpc.net/problem/1743 packag..

문제 https://www.acmicpc.net/problem/5212 5212번: 지구 온난화 첫째 줄에 지도의 크기 R과 C (1 ≤ R, C ≤ 10)가 주어진다. 다음 R개 줄에는 현재 지도가 주어진다. www.acmicpc.net 풀이 그냥 이차원 배열 돌면서 3면 이상이 바다면 땅을 물에 잠기게 해주면 된다. 새로운 정답 2차원 배열 지도를 만들어서 물에 잠긴 땅이 다음 칸에도 영향을 주지 않게 하였음! 정답 지도를 그릴 때는 다시 정답 배열을 돌면서 범위 체크를 위한 변수를 최신화하고 그 범위 내의 지도만 그려줌! 위의 두 가지만 조심하면 어렵지 않게 금방 풀 수 있는 문제임!!! 자세한 건 주석으로!! 코드 // 5212번 지구 온난화 // https://www.acmicpc.net/pro..

문제 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 처음에 어떻게 풀지 설계를 안하고 풀다보니까 중간에 한번 엎었다... 문제 좀 똑바로 읽고 풀자 쫌...!!!!! 쭈욱 돌면서 뿌요가 있으면 같은 색의 뿌요가 4개 이상 인접해있는지 dfs()로 판단하다가 4개가 넘어가면 그 위치에서 다시 dfsBomb()를 돌려서 연결되어 있는 뿌요를 다 없앰! 그리고 다른 색의 뿌요도 4개 이상이 인접해 있는 경우가 있으니까..

문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 아 처음에 톱니바퀴의 위치에 따라서 옆 톱니바퀴가 회전하는지 안하는지를 생각을 안해줘서 너무 노가다로 풀었다,,,, 진짜 너무 빡침 ㅠ 이래서 설계가 중요하구나 느꼈음./... 중간에 코드 짜다가 아 이렇게 풀면 안되는구나 하고 알았는데 톱니바퀴 4개라서 노가다도 될 것 같고, 이미 돌아가기엔 너무 늦었으니까 이렇게 풀고 다음에 톱니바퀴2 문제나 이 문제 한번 더 풀어야 겠다 라고 ..

문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 https://seokmimmmmmmmm.tistory.com/98 [백준]7576번 토마토 - Java 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000.. ..

문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 뭐 여러가지 방법을 풀 수 있겠지만 인접 행렬로 풀면 쓸데없는 메모리 활용이 좀 있을 것 같다. 그래서 ArrayList를 활용한 인접 리스트로 풀었음. 방문 체크 배열을 이용해서 이미 방문한 곳은 체크를 하고 인접한 애들 중 방문하지 않은 애들인 경우에만 answer++하고 dfs를 한번 더 탔음! 밑에 코드 참고! 코드 // 2606번 바이러스 // https://www.acmicpc.n..

문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 시뮬레이션 문제이다. 뱀을 큐로 생각했고, 다음 칸의 좌표를 뱀 큐에 넣어주고 그 칸이 사과면 큐의 길이를 줄이지 않고(poll()하지 않고) 사과가 아니면 큐의 길이를 줄였음(poll()했음). 그리고 방향 전환은 4방향을 시계방향으로 해줬음(시계 반대 방향이여도 상관 없음). 4방 탐색이므로 +를 해서 4가 넘어가면 %4 연산을 통해서 방향이 돌고 돌 수 있게 해줌 이것들만 생각하면 잘 풀..