거의 알고리즘 일기장

https://codeforces.com/problemset/problem/189/A Problem - 189A - Codeforces codeforces.com 풀이방법 시간은 1초, n,a,b,c는 최대 4000이다. 조건은 1. piece는 무조건 a or b or c 2. 최대로 자를수 있는 값을 구하라 완전탐색으로 할시 최악의 경우 ( a,b,c가 1, n이 4000일때 ) 4000! * 3일수 있다. 그러므로 완전탐색은 탈락이고 시간을 줄일수 있는 dp를 써보자. dp[value] : value일때 최대로 자를수 있는 개수 그리고 a, b, c를 하나씩 순서대로 밑의 조건대로 넣어보자. 1. value % piece (a or b or c) == 0 일때 dp[value] = max(dp[va..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 풀이방법 완전탐색으로 푼다면 16!로 말도안되는 시간이 걸린다. 그러므로 dp를 추가해서 적절히 중복되는 연산을 저장하고 그 값을 이용함으로써 연산을 줄이는 방법이 필요하다. 예를 들어 1 2 3 4 5 6 7 1 2 3 4 5 7 6 1 2 3 4 6 5 7 1 2 3 4 6 7 ..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이방법 https://kunkunwoo.tistory.com/60 프로그래머스_가장 긴 팰린드롬 https://programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업.. kunkunwoo.tistory.com 이 문제와 유사하다. 자세한 설명은 위에 해놨으니..

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활�� www.acmicpc.net 풀이방법 냅색 알고리즘의 일종이라고 한다. (알고싶다면 밑의 블로그 참조할것) https://namnamseo.tistory.com/entry/%EB%83%85%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 냅색 알고리즘 냅색 문제는 유명한 다이나믹 문제 중 하나이다. (사진 출처 wikipedia.org) 가장 유치하지만 또 가장 많이 쓰이는 설명으로는, 한 가게..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지 www.acmicpc.net 접근 주어진 조건들을 먼저보자. 시간은 2초, MxN 행렬 (M, N [백준][1520번][DP] 내리막길 내리막길 https://ww..

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다. www.acmicpc.net 주의사항 1. 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 2. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다. 풀이방법 https://kunkunwoo.tistory.com/101 백준 11066번 _ 파일 합치기 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 주의사항 소설이므로 장이 섞이면 안된다. -> 그러므로 바로 옆에 있는것하고만 파일을 합칠수있다! 접근 총 파일이 4개라고 하면 ..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이방법 예시인 1 ,2 5원으로 10원이 나올수있는 동전의 경우의 수를 잘 생각해보자. 일단 1원만 사용했을경우 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1, 2원 사용했을 경우 1 2 3 4 5 6 7 8 9 10 1 2 2 3 3 4 4 5 5 6 1, 2, 5원 사용했을 경우 1 2 3 4 5 6 7 8 9 10 1 2 2 3 4 5 6 7 8 10 잘 보면 ..

https://www.algospot.com/judge/problem/read/WILDCARD algospot.com :: WILDCARD Wildcard 문제 정보 문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다. 와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자 www.algospot.com 풀이방법 1. * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다. 2. ? 는..