문제 링크 Gold 4 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net https://mag1c.tistory.com/452 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘 그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로, mag1c.tistory.com 풀이 방향..

문제 링크 Silver 1 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 문제의 조건은 선택한 스티커의 상하좌우 스티커는 선택할 수 없다. 라고 하였다. 아래 문제 예시를 보자. 50 10 100 20 40 30 50 70 10 60 위의 예시에서, dp를 사용하여 최대값을 어떻게 구할 수 있을까 왼쪽부터 시작해서, 하나씩 선택해보았다. 50 10 30 50 50 10 30 50 첫 번째 idx의 값을 선택할 수 있다. 두 번..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12983?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 DP를 사용하여 Bottom Up으로 풀이했고, 문제 예시에서의 banana로 예를 들어보자. b ba ban bana banan banana dp배열의 각 idx는 위의 값들을 만족하는 최소값들로 채워나갔다. strs의 원소에서, t의 인덱스마다 같은 substring이 있는지 확인하였고, 같다면 dp배열에 입력해나갔다. //strs에서 선택한 문자열과 ..

문제 링크 Silver 3 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 풀이 문제 티어는 낮지만 DP문제라서 냉큼 공부 처음에는 아래처럼 해당 idx의 제곱값을 구하여 greedy처럼 풀어내려고 했으나 int[] arr = new int[(int) Math.sqrt(n) + 1]; for (int i = 0; i < arr.length; i ++) { arr[i] = i * i; } 모든 상황에 만족하지 ..

문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 자기 전에 문제 하나 풀고 자야지~~ 하면서 풀었던 문제 실버 3 문제라 DP로의 접근은 쉬웠으나, 뜻하지 않게 ArrayIndexOutOfBounds Exception으로 고생했음.. 반 졸린 상태에서 풀어서~~ 라고 핑계를 대보지만. 실수를 줄이기 위해 항상 신경써야겠다고 다짐한 문제로. 상기시키기 위해 포스팅.... import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; publi..

Uncrossed Lines - LeetCode Can you solve this real interview question? Uncrossed Lines - You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines. We may draw connecting lines: a straigh leetcode.com 풀이 DP배열의 idx의 값은 해당 idx까지 서로 탐색을했을때, 겹치지 않는 최대 경우의 수를 나타낸다. class Solution { public int maxUncrossedL..

https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 첫 풀이 최소 반복 횟수를 구하는 문제이기 때문에 Bottom-Up방식을 활용해서 8번 반복할 때까지 해당 해가 있는지 찾고, 반복횟수가 9번째가 될 때 answer = -1로 리턴해주게 하자.. 라고 생각하며 코드를 작성했다. (DP공부를 한 뒤, 간단한 문제들을 풀고 처음으로 푸는 높은 난이도(??)의 문제라 설명이 부족할 수 있음.. 지나가던 고수분들 계시면 고쳐주시면 감사하겠습니다. 많은 ..