백준44

• 

  [백준 Java] 11053 가장 긴 증가하는 부분 수열 (DP) [문제 링크] boj 11053 가장 긴 증가하는 부분 수열 자바 풀이 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net [생각 흐름] dp(다이나믹 프로그래밍)을 이용하여 문제를 해결했다. 앞에서부터 arr[i]를 포함한다는 전제로(일종의 기준점) arr[i]보다 작고(arr[i]보다 작아야 arr[i]가 커서 증가하는 부분 수열 이므로) sum[j]( 0~j까지의 .. 알고리즘 2022. 10. 2.

• 

  [백준 JAVA]14502_연구소 [문제 링크] 14502 boj 연구소 자바 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [생각 흐름] 문제는 연구실에 바이러스가 최대한 안 퍼지게 할 수 있는 벽을 3개 세우는 문제이다. 처음에는 모든 경우에 3개 벽을 세우는 것을 계산하여 문제를 푸는 것인지 고민했다 (설마 완탐..? ) 예제를 보다가 내가 계산하는 것도 어렵게 느껴져서 그냥 완탐으로 풀이하였다. 일단 백 트랙킹을 이용하여 벽을 3개 어떻게 세울 건지 고려하고, 각각의 경우에 대해서.. 알고리즘 2022. 9. 29.

• [백준] 14938_서강그라운드_플로이드 워셜 [문제 링크] boj 14983 서강 그라운드 플로이드워셜 https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net [생각 흐름] 처음에는 예시에서 한 지점을 두고 설명하길래 다익스트라로 해결하는 문제인 줄 알았는데 input값을 보고 플로이드 워셜로 해결해야겠다고 생각했다. 플로이드 워셜로 위치에서의 가장 짧은 distance를 구한후에, 각 지점에서 탐색 가능한 범위인 경우 stock[city]를 더하여 저장하고 값들 중 최대값을 계산하여 출력하였다. [.. 알고리즘 2022. 9. 28.

• [백준]12851_숨바꼭질 2 [문제 링크] boj 12851 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net [생각 흐름] 이전에 숨바꼭질 문제 3번과 동일한 문제 유형이었다. 추가적인 문제 조건으로 몇 가지의 방법으로 최단시간에 도착할 수 있는지가 포인트였다. 먼저 동생보다 수빈이가 앞에 있다면 n-m을 리턴해준다, 만약 같은 자리에 있어도 바로 리턴해준다 여기서 가는 방법의 수는 한 가지이므로 한가지 이고, 이를 생각하.. 알고리즘 2022. 9. 28.

• [백준]10830_행렬 제곱_분할 [문제 링크] https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net [생각 흐름] n이 짝수인 경우에는 n/2를 계산한 만큼의 곱을 한 번 더 제곱하면 되고, n이 홀수인 경우에는 (n-1)을 반으로 나는 것을 제곱하고 후에 배열을 한 번 더 곱해주면 된다. 9인 경우 4*2와 1, 4인 경우 2*2, 2인 경우 1*2로 나누어 아래에서부터 차례로 올라가면 저장해둔 값을 곱해 준다. public static int[][] matrixSquare(int[][] ar.. 알고리즘 2022. 9. 27.

• [백준]14503_로봇청소기 [문제 링크] boj 14503 로봇청소기 구현 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [생각 흐름] 처음에는 문제의 조건대로 각 케이스별로 하려 하였으나 케이스를 묶을 수 있어서 묶어서 풀이하였다. 문제의 조건 2번의 말은 결국 현재 위치에서 왼쪽으로 돌면서 청소가 안되어있으면 가고 청소가 되어 있거나 벽이면 또다시 왼쪽으로 돌아서 확인한다는 것이다. 따라서 처음 시작 dir에서 왼쪽으로 돌아가며 벽이 아닌데 청소가 안되어 있는 경.. 알고리즘 2022. 9. 26.

• [백준]9935_문자열폭발_Stack [문제 링크] https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net [생각 흐름] 처음에는 자바에서 제공하는 replace를 반복하려 했으나 시간 초과 문제가 있다고 하여 스택으로 변경하였다 폭발하는 문자열의 마지막 문자열의 마지막 문자를 저장해 두고 그것과 같은 문자가 들어오는 경우 스택을 확인하는 방식으로 알고리즘을 구현하였다 푸는 중 2%에서 계속 메모리 초과 오류가 발생했는데 StringBuilder 클래스를 사용하여 마지막 스.. 알고리즘 2022. 9. 25.

• [Programmers]합승 택시 요금 [문제 링크] https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [생각 흐름] 플로이드워셜 알고리즘이용 start에서 i까지 같이 가고 i 부터 a,b까지 가는 경로 [코드] import java.util.Arrays; public class Main { public int solution(int n, int s, int a, int b, int[][] fares) { int arr[][] = new int[n+1][n+1]; int INF = .. 알고리즘 2022. 9. 23.