매일 조금씩

문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 간선 정보가 명시적으로 주어지며, 다익스트라 알고리즘으로 풀 수 있는 문제이다. 1. 다음 노드와 다음 노드로 이동 시의 가중치 값을 저장할 Edge 클래스를 구현한다. public static class Edge { int to; int weight; public Edge(int to, int weight){ this.to = to; this.weight..

문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 오랜만에 다익스트라 알고리즘 문제를 풀어 보았다. 나는 아래와 같이 풀었다. 1. 간선에 대한 정보가 명시적으로 주어지지 않기 때문에 직접 만든다. 배열을 순회하면서 상하좌우를 체크하여 접근 가능한 좌표라면 현재 배열 좌표에 인접한 좌표라고 볼 수 있다. 이때 인접한 좌표의 배열 값이 해당 좌표를 가기 위한 가중치 값이 된다. for(int i = 0; i < N; i..

문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 밑이 같은 두 거듭제곱의 곱은 밑은 그대로 쓰고 지수만 더해준다는 지수법칙을 활용한다. 예를 들어 2의 10제곱은 2^10 = 2^5 * 2^5 로 분할 할 수 있다. 그러면 2를 10번 곱하는게 아닌 2를 5번 곱한 값을 가져와서 제곱을 하면 된다. 2^5 또한 아래와 같이 분할 할 수 있다. 2^5 = 2^2 * 2^2 * 2 이렇게 지수의 거듭제곱을 절반 씩 분할 하면서 제곱 계산의 수를 현저히..

문제 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 단순한 재귀 용법으로 해당 문제를 푸는 것은 불가능하다. n이 무려 1,000,000,000,000,000,000이다. 두 가지 내용을 이해하면 문제를 풀 수 있다. 1. 피보나치 수를 행렬의 곱을 통해 구할 수 있다. 2. 제곱을 구할 때, 지수를 반으로 나누어 곱하는 방식으로 재귀횟수를 줄일 수 있다. 아래 문제 참고 2021.11.18 - [Problem Solving/BOJ] - [BOJ 1629] 곱셈 (Java) [BOJ 1629] 곱셈 (Java) 문..

문제 https://programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 풀이 구현 문제이다. 아스키 코드를 이용하여 Map에 각 알파벳에 해당하는 색인 번호를 저장해두고 시작한다. 마지막 인덱스 경계값을 신경써서 구현해야 한다. 풀이는 소스코드에 주석을 달아놨다. 소스코드 import java.util.*; class Solution { public int[] solution(String msg) { ArrayList list = new ArrayL..

문제 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거..

문제 https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 풀이 대표적인 분할 정복 문제로, 재귀 함수를 사용하여 작게 쪼개면서 푼다. 아래와 백준 문제와 풀이가 동일하다. 2021.11.16 - [Problem Solving/..

문제 https://programmers.co.kr/learn/courses/30/lessons/17683 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 풀이 왜 이렇게 말을 꼬아놨는지 문제를 이해하는데 너무 오래걸린다. 이 문제는 단순 구현 문제로 어려운 문제는 아니다. '#' 기호가 음악 매칭할 때 걸리적 거릴게 눈에 훤해서, 애초에 내가 기억한 멜로디에서 해당 기호를 떼고 다 소문자로 치환해주었다. MusicInfo는 클래스를 생성하였다. 이 때에도 '#'기호를 떼줘야 한다. 문자열 덩어리..

문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 이분 그래프 개념을 알아야 풀 수 있다. 그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다. https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 이분 그래프..

문제 https://programmers.co.kr/learn/courses/30/lessons/17680