본문 바로가기

전체 글

[알고리즘] 최장 공통 부분 수열 LCS - DP & 이진탐색 LIS (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 8. 10. [알고리즘] 최장 공통 부분 수열 LCS - DP & 이진탐색 LIS (Java) 최장 공통 부분 수열 LCS (Longest Common Subsequence) LCS(Longest Common Subsequence)는 LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 나타내지만 최장 공통 문자열(Longest Common Substring)을 말하기도 한다. 최장 공통 문자열(Longest Common Substring)은 반드시 부분 문자열이 연결된 형태여야한다. banana, vbankn 최장 공통 부분수열(Longest Common Subsequence)은 떨어져있어도 상관없다. bdanvv, vbkkanm 이번에 다룰 LCS 알고리즘은 최장 공통 부분수열(Longest Common Subsequence)이다. 이는 주어진 여러 개의 수열 ..
[BOJ] 백준 1600번 말이 되고픈 원숭이 (Java)
Dot Algo∙ DS/PS 2021. 8. 10. [BOJ] 백준 1600번 말이 되고픈 원숭이 (Java) #1600 말이 되고픈 원숭이 난이도 : 골드 4 유형 : 그래프 탐색/ BFS 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net ▸ 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애..
[BOJ] 백준 7576번 토마토 (Java)
Dot Algo∙ DS/PS 2021. 8. 9. [BOJ] 백준 7576번 토마토 (Java) #7576 토마토 난이도 : 실버 1 유형 : 그래프 / BFS 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ▸ 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의..
[알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 8. 9. [알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java) 가장 긴 증가하는 부분 수열 LIS LIS(Longest Increasing Subsequence)는 불연속 상관없이 가장 긴 증가하는 부분 수열을 구하는 알고리즘이다. 예시로, 수열 A = {10, 20, 10, 30, 20, 50}이 있다고 하면 해당 수열의 LIS는 {10, 20, 30, 50} 이다. 풀이 방법으로는 DP를 활용한 LIS, 이진탐색을 활용한 LIS 두 가지가 있다. DP는 단순하지만 시간복잡도가 O(n^2)을 가진다. 이진탐색을 활용하면 시간복잡도를 O(nlogn)을 가진다. 1. DP로 풀이하는 방법 dp는 1차원 배열로 dp[i]에는 0~i 증가하는 부분 수열의 크기를 나타낸다. dp[i] = 0~i의 증가하는 부분 수열 크기 수열 A = {10, 20, 10, 30, 20, ..
[BOJ] 백준 2294번 동전2 (Java)
Dot Algo∙ DS/PS 2021. 8. 8. [BOJ] 백준 2294번 동전2 (Java) #2294 동전2 난이도 : 실버 1 유형 : DP 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net ▸ 문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. ▸ 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는..
[BOJ] 백준 2293번 동전1 (Java)
Dot Algo∙ DS/PS 2021. 8. 7. [BOJ] 백준 2293번 동전1 (Java) #2293 동전1 난이도 : 실버 1 유형 : DP 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net ▸ 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. ▸ 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치..
[BOJ] 백준 1520번 내리막 길 (Java)
Dot Algo∙ DS/PS 2021. 8. 6. [BOJ] 백준 1520번 내리막 길 (Java) #1520 내리막 길 난이도 : 골드 4 유형 : DP / DFS 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net ▸ 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게..
[BOJ] 백준 12865번 평범한 배낭 (Java)
Dot Algo∙ DS/PS 2021. 8. 5. [BOJ] 백준 12865번 평범한 배낭 (Java) #12865 평범한 배낭 난이도 : 골드 5 유형 : DP/ 배낭문제 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net ▸ 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지..

티스토리툴바

티스토리툴바