알고리즘 문제풀이 썸네일형 리스트형 [SWEA][JAVA] 3124 - 최소 스패닝 트리 문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_mSnmKUckDFAWb&categoryId=AV_mSnmKUckDFAWb&categoryType=CODE&problemTitle=3124&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 설명 문제에서 나와 있듯이, Prim 또는 Kruscal 알고리즘을 그대로 구현해 보는 문제입니다. 저는 간선 리스트와 서로.. 더보기 [백준][JAVA] 1463 - 1로 만들기 문제 출처 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 N의 범위가 꽤나 크지만 시간 제한이 0.15초로 굉장히 짧은 걸로 봐서, dp문제임을 짐작할 수 있습니다. dp배열에 해당하는 d에는 각 인덱스에 해당하는 수를 1로 만들기 위해 필요한 최소 연산의 횟수가 각각 들어가 있고, 메모이제이션을 해 가며 답을 도출했습니다. 초기값을 d[3]까지 넣어준 다음, 4부터 N까지 반복문을 돌며 i가 2와 3으로 모두 나누어 떨어지는 경우, 2로만 또는 3으로만 나눠 떨어지는 경우 그리고 2와 3 모두 나누어 떨어지지 않는 경우로 나눴습니다. i는 .. 더보기 [백준][JAVA] 1149번 - RGB거리 문제 출처 : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 설명 전형적인 DP문제였습니다. 재귀처럼 FLAT하게 생각하는게 중요한 유형이죠. 여기에서 dp용 배열로 사용한 d는 1번 집부터 N번 집까지 집을 칠하는 비용의 최솟값이 들어있습니다. 예를 들어, d[N][0] 은 N번집에 빨간색을 칠했을 경우에 1번 집부터 N번 집까지 집을 칠하는 비용의 최솟값이 들어있는 것이죠. 그런 식으로 계속해서 min값만을 골라 거기.. 더보기 [백준][JAVA] 10026 - 적록색약 문제 출처 : https://www.acmicpc.net/problem/10026 문제 설명 R, G, B 군집들이 몇 개가 있는지 알아내기 위해 dfs를 구현했습니다. 그 다음에 기존 pic에서 R인 부분을 모두 G로 바꿔줌으로써 적록색약 환자 버전을 새로 만들었습니다. 그 후, 동일한 과정을 통해 G와 B의 군집들이 총 몇개 있는지 세어주는 방법을 통해 문제를 해결했습니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class BOJ10026_RGB { static char[][] pic; static boolean[][] visited; static int N, R.. 더보기 [백준][JAVA] 12927 - 배수 스위치 문제 출처 : https://www.acmicpc.net/problem/12927 문제 설명 실버4로, 평이한 난이도의 문제였습니다. 스위치를 앞에서부터 하나씩 비교해 나가면서, 스위치의 상태가 서로 다르면 뒤에 것을 눌러 그 배수의 스위치까지 모두 반전시켰습니다. 그렇게 해 나가면서 스위치의 끝까지 진행한 후에, 스위치가 모두 Y거나 N으로 구성된 상태라면 전구를 모두 끌 수 있다는 뜻이므로 cnt값을 출력했습니다. 그렇지 않다면 모두 끌 수 없는 상태라는 뜻이기 때문에 -1을 출력하도록 했습니다. 코드 import java.util.Scanner; public class BOJ12927_Switch { public static void main(String[] args) { Scanner sc = n.. 더보기 [백준][JAVA] 2559 - 수열 문제 출처 : https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 설명 가장 직감적으로 떠오르는 방법으로 구현을 했습니다만, 만약 N의 범위가 훨씬 커진다면 시간초과가 날 수 있는 코드입니다. 'Sliding Window'라는 기법을 이용한다면, window를 한칸씩 밀면서 공통되는 부분을 재사용하고 새롭게 빼지고 더해지는 원소만 계산함으로써 효율적으로 답을 구할 수 있습니다. 이와 관련된 코드는 제가 추후에 게시물을 올리면 밑에.. 더보기 [백준][JAVA] 2304 - 창고 다각형 문제 출처 : https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 문제 설명 실버2 문제치고 어려운 문제였습니다ㅠㅠ 코드에 최대한 주석 달아놨으니 참고해 주시면 좋을 것 같습니다. 이 문제의 핵심은 높이가 가장 높은 꼭대기를 구하는 것인데, 왼쪽에서 오른쪽 방향으로 진행해 나가며 current Top point를 변경시키면서 찾습니다. 꼭대기와 면적까지 계산한 뒤에, 구한 꼭대기를 기반으로 오른쪽에서 왼쪽 방향으로 아직 구하지 못한.. 더보기 [백준][JAVA] 2578 - 빙고 문제 출처: https://www.acmicpc.net/problem/2578 2578번: 빙고 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 www.acmicpc.net 문제 설명 단순 구현 문제입니다. 사회자가 부른 숫자를 자신의 빙고판에 표시하다가, 최소 12개 이상부터 빙고가 가능하기 때문에 12개 이후에는 사회자가 부른 수를 빙고판에 표시할 때마다 빙고 상태인지를 체크하게 했습니다. 여기서 중요한 점은, 빙고 체크가 한번 끝날 때마다 다시 cnt 변수를 0으로 초기화 해주어야 한다는 점입니다! 코드 import java.util.Scanner; public .. 더보기 이전 1 2 3 4 ··· 8 다음
