알고리즘49

• 

  [백준 Java] 10942 팰린드롬? 자바 10942 팰린드롬 dp https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 시간제한이 0.5초이고 메모리 제한이 커서 dp를 이용해서 저장해 두고 테스트 케이스에 대해서 계산된 값을 출력해야겠다고 생각했다. dp 테이블에는 팰린드롬이라면 1을 저장하고 아니면 0을 저장하였다. 포인트라고 생각한 아이디어는 i ~ j 까지가 팰린드롬인지를 확인하기 위해서 input[ i ]와 input[ j ]를 비교하고 i+1과 j-1까지가 팰린드롬 인지를 확인하면 된다. 예를 들어 만약 테스트 .. 알고리즘 2022. 10. 13.

• 

  [백준 JAVA]1806 부분합 [문제 링크] 백준 자바 1806 부분합 투포인터 누적합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net [생각 흐름] 투 포인터를 활용하여 문제를 해결했다. 먼저 만약 입력 값이 이미 원하는 값 이상이면 최소 길이가 1 임으로 브레이크하고 반환하였다. 그 이후에는 먼저 원하는 목푯값보다 클 때까지 right를 오른쪽으로 이동하면 더해간다. 만약 현재 값을 더했을 때 목푯값보다 커진다면 길이를 right-left+1과 ans 중 .. 알고리즘 2022. 10. 7.

• 

  [백준 JAVA] 2239 스도쿠 풀이 [문제 링크] 자바 2239 스도쿠 java 풀이 백트랙킹, 구현 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net [생각 흐름] 여러가지가 있다면 사전식 출력을 원하고 있어서 1~9까지 모든 숫자를 가능하면 넣어 보는 식으로 해결했다. 먼저 칸이 빈칸이라면 arraylist에 넣어두고 DFS를 첫 빈칸부터 시작하도록 하였다. 현재 채울 칸의 가로와 세로, 정사각형 칸을 비교하고 가능하면 넣었다. 그리고 다음 빈칸 을 진행할 수 있도록 하였.. 알고리즘 2022. 10. 5.

• 

  [백준 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.

• [백준]9465_스티커_dp [문제 링크] https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net [생각 흐름] dp 방법으로 해결하였다 선택할 수 있는 방법이 (1번 줄, 2번 줄) OX, XO, XX 세 가지를 가질 수 있으므로 (O는 스티커가 있다, X는 스티커가 없는 경우) 각 경우에 맞춰서 초기값을 계산하였다. 그리고 아래의 코드와 같이 ox-> xx , ox->xo, xx-> ox, xx->xo, xx->xx , xo->ox , xo->xx로 7가지의 경우로.. 알고리즘 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.