[GAEBAL Blog]

문제 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 처음에 문제를 읽었을 때 정말 쉬운 문제라고 생각했음 근데 또 문제 안읽어서 주어지는 수들의 범위를 체크를 못함 또 또또 ㅠㅠㅠㅠ 1번 방법(오답) 그냥 높이별 부딪히는 횟수를 계산할 배열을 만들고 2중 for문을 돌면서 해당 배열에 저장해줌! 이렇게 풀면 당연히 시간초과,,,, 2번 방법(정답) 이분 탐색! 오답 코드 // 3020번 개똥벌레 // https://www.acmicpc.ne..

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 전형적인 삼성 기출 문제 중 하나인 것 같다. 최근에 삼성 기출 문제를 몇개 접했는데 다 너무 어려워서 손도 못대거나 못풀거나 했다. ㅠㅠㅠ 그래서 자신감도 없고 이런 문제만 보면 기가 죽었는데 최근에 풀었던 삼성 문제들 중에는 쉬운 편에 속하는 것 같아서 어찌저찌 풀었다. 문제에 조건들을 보면 숫자가 크지 않으므로 완전탐색이 가능하다는 것을 알 수 있고, 그냥 막 돌리면 되겠다 싶어서 ..

문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 토마토가 다 익는데까지 며칠이 걸렸는지 출력하는 문제이기 때문에 DFS로 풀면 답을 찾기 힘들 것이다. 그래서 BFS로 풀었음! 1번 방법(오답) BFS할 때 사용하는 큐의 Tomato 클래스는 익은 토마토의 위치와 며칠째에 익었는지를 나타내는 day를 멤버변수로 함! 큐에서 하나씩 빼서 다음 칸으로 갈 수 있는지 검사하며, 다음 칸을 큐에 넣어줄 때 day+1을 하면서..

문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 허허,,, 풀긴 풀었는데 너무 더럽게 푼 것 같다,,, 느낌만 그런건가...?? 조합 + DFS로 풀었음! 중간에 막힌 부분이 있었는데 dfs돌려서 안전 영역 최대값을 조사한 후 map 배열을 초기화 해줄 때 초기화 시점이 헷갈려서 자꾸 벽을 하나도 안세울 때로 초기화를 해버려서 좀 시간이 걸렸다 ㅠㅠ 그래서 벽을 2개 세웠을 때의 map을 tempMap에 잠시 저장해놨다가 벽 3개 세우고 dfs돌..

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 문제를 읽어보면 딱 다익스트라 쓰면 풀 수 있겠구나 하고 감이 온다. 출발지랑 도착지가 정해져있고 최소 비용을 구하는 거니까! 도로를 복구하는 시간 말고 최단 거리 같은 조건은 없으니까 별 다를게 없는 그냥 다익스트라 문제이다. https://seokmimmmmmmmm.tistory.com/84 [백준]4485번 녹색 옷 입은 애가 젤다지? - Java 문제 https://www.acmi..

문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 후,,, 나는 구현 문제가 왜 이렇게 어려운지 모르겠다 ㅠㅠㅠ 많이 풀어봐야 될 듯하다,, 음 뭐랄까 dfs인데 횟수 제한이 있는 dfs 문제?? 2a번 단계가 4번 연속으로 실행되면 멈추거나 후진해야되니까? 개인적으로 포인트는 1. 왼쪽으로 돌거나 뒤로 후진할 때의 방향 설정이랑 2. return을 해줘야하는 위치 라고 생각한다! 걔네들을 어떻게 했는지는 밑에 코드의 주석을 보면 알..

문제 https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 크기 10인 1차원 배열을 만들어서 반복문을 돌면서 인덱스에 해당하는 번호가 나올 때마다 증가를 시켜줌 반복문이 끝마녀 그 중 최댓값을 출력하면 되는데, 6이나 9인 경우에는 int temp = arr[6] + arr[9]; temp = temp / 2 + temp % 2; 6이랑 9를 뒤집어서 사용할 수 있으므로 이렇게 해줘야 됨 그 후에 다시 최댓값을 찾아서 출력하면 끝! 아예 처음에 배열을 크기 9로 만들고 입력받을 때 6이랑 9를 같은거라고 인식해서 입력 받아서 풀 수도 있을 ..

문제 https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 풀이 처음엔 문제를 읽고 너무 어렵게 생각해서 DP 문제인가 아니면 재귀로 접근해야하나 고민했는데 S가 10인 경우, 100인 경우를 예시로 생각해보니까 단순히 계산해주면 될 것 같아서 단순 계산 문제로 접근했다. 그런데 분명히 답은 맞는데 런타임 에러가 나서 다시 문제를 읽어보니까 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 범위가 딱 long 타입의 범위였다. 그래서 sc.nextLong으로 받아서 해결! 코드 // 1789번 수들의 합 // https://www.acmicp..

문제 https://www.acmicpc.net/problem/14720 14720번: 우유 축제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 풀이 쉬운 문제임 주석 참고하셈! 코드 // 14720번 우유 축제 // https://www.acmicpc.net/problem/14720 package BAEKJOON; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer..

문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 구현 + 백트래킹 문제 처음에는 입력을 받으면서 큐에 0인 칸의 인덱스(행, 열)을 넣어주었다. poll해서 해당 값을 사용하고 정답이 아닌 경우에는 재귀를 return해서 다시 그 값을 사용해야하는데 큐를 쓰면 그게 불가능해서 다시 구현했다. 다시 구현할 때에는 Queue가 아닌 ArrayList로 구현했다. ArrayList에 숫자가 채워지지 않은 칸(0인 칸)을 넣어주고 인덱..

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 1로 만들기 같은 유형의 DP 문제이다. https://seokmimmmmmmmm.tistory.com/82 [백준]1463번 1로 만들기 - Java 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 흔한 DP 유형의 문제임 하향식, 상향식 ..

문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 DP 문제임. 1차원 정답 배열(dp)를 만들어서 풀었음 하루가 지날 때마다 최댓값을 dp 배열에 갱신해주는게 포인트 ! 아직 헷갈려서 담에 한번 더 풀어봐야겠음 T, P, dp 배열을 N+6으로 크기를 설정해준 이유는 [맨처음 0번 인덱스 + (1 ≤ Ti ≤ 5)] 이거 때문이다. 코드 // 14501번 퇴사 // https://www.acmicpc.net/problem/14501 package BAEKJOON; import java.io.BufferedReader; import java.io.IOException; i..

문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 그냥 지금까지 많이 풀었던 탐색 문제이다. DFS로 풀었다. 음 뭐랄까 쉬워서 별로 할 말이 없다 https://seokmimmmmmmmm.tistory.com/42?category=1004588 [백준]2468번 안전 영역 - Java 문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서..

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 가중치가 있을 때 최단 경로를 구하는 경우 다익스트라 알고리즘을 많이들 사용한다. 근데 가중치가 음수라면 다익스트라 알고리즘을 사용하지 못하는데, 그때 사용할 수 있는 알고리즘이 바로 이 플로이드 와샬 알고리즘이다. 얘는 3중 for문을 돌리기 때문에 시간 복잡도는 O(N^3)이 나오지만(다익스트라 알고리즘도 인접 행렬을 이용하면 O(N^3)의 시간 복잡도가 나오기도 함) 구현이 간단해서..

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 유명한 DP 문제 유형이라고 한다. DP말고 부분 집합으로도 풀 수 있다. 하나하나 첨부터 끝까지 부분집합을 만들어서 가장 긴 증가하는 부분 수열을 뽑아내도 되는데 그렇게 하면 O(2^N)의 시간 복잡도가 소요된다. 개오래 걸리는거지 미친거지 그니깐 물론 뭐 공집합부터 탐색하는게 아니라 전체집합부터 탐색하면 조금 더 빨리 찾을 수는 있겠지만,,, 그니까 부분 집합말고 DP로 풀어야 시간 ..

문제 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 풀이 간단한 DFS, BFS 문제인 듯하다 그래서 DFS로, BFS로 각각 사용해서 풀어봤음 일단 DFS는 그냥 맨 윗줄에서 0이면 DFS 들어가고 돌면서 0인 칸을 2로 바꿔줌 위에서 0인 애들 다 돌렸으면 맨 밑줄에서 2인 애가 나오면 그건 전기가 통하는 거고 안나오면 안통하는거 그니까 2가 나오면 YES 출력하고 System.exit(0);으로 시스템..

문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 문제가 재밌음 그니까 문제 푸는게 재밌는게 아니라 문제가 그니까 그냥 읽는게 재밌다고 암튼 나는 다익스트라로 풀었음 그냥 뭔가 포인트나 함정같은 부분은 없는 기본적인??? 다익스트라 문제인듯???? 자세한 설명은 주석으로 코드 // 4485번 녹색 옷 입은 애가 젤다지? // https://www.acmicpc.net/problem/4485 package BAEKJOO..

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 얘도 DP 문제임 모든 최적해를 구해야하는데 새로운 2차원 배열에 저장을 하면서 구한다고 생각하면 편함 이런 유형의 문제를 많이 풀어놔서 익숙하게 만들어 놔야 겠음 ㅎㅎ 코드 // 1149번 RGB거리 // https://www.acmicpc.net/problem/1149 package BAEKJOON; import java.io.*; import java.util..

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 흔한 DP 유형의 문제임 하향식, 상향식 두 가지 방식으로 풀었음! 처음 생각하는 방식이 좀 어렵고 떠올리기만 하면 쉽게 풀 수 있는 듯??? 코드 // 1463번 1로 만들기 [DP(동적계획법) - 1로 만들기 문제] // https://www.acmicpc.net/problem/1463 package BAEKJOON; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public c..

문제 https://programmers.co.kr/learn/courses/30/lessons/43105?language=java 풀이 DP 문제임. DP 문제는 보면 뭔가 DP 문제 같은데 어케 푸는지 모르는 경우가 허다한 것 같음 ㅠ 근데 오랜만에 맞춰서 좀 좋았음 ㅎㅎㅎㅎㅎ 삼각형의 위에서 부터 내려오면서 더해주는게 아니라 새로운 2차원 배열을 만들어서 거꾸로, 그니까 밑에서 부터 올라가면서 비교하면서 새로운 배열에 최대값을 저장해주는 식으로 풀었음! 어떻게 푸는지 떠올리기만 하면 쉽게 풀리는게 DP의 매력아닌 매력인 것 같음! 코드 // 코딩테스트 연습 - 동적계획법 - 정수 삼각형 // https://programmers.co.kr/learn/courses/30/lessons/43105?lan..