목록알고리즘 (22)

Hello World!

[BOJ] 1963번 - 소수 경로

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/1963 1963번: 소수 경로 문제 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 www.acmicpc.net 요즘 왜인지 무기력해서 문제 푸는게 힘들었는데 오랜만에 새로운 문제를 풀었다. 물론 쉬운 문제여서지만 첫 시도에 AC를 받으니 기분이 좋다. 제일 먼저 에라토스테네스의 체를 통해 네 자리수 소수를 모두 표시했다. 또한 비밀번호는 한 번에 한 자리만 변경할 수 있으므로 단계마다 최대 $9^4$가지의 경우의 수가 있는데, 그 경우의 수를 쉽게 구하기 위해 string을 이용했다. 현재..
알고리즘/baekjoon 2020. 5. 18. 02:05
[BOJ] 7569번: 토마토

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 처음 bfs에 입문했을 때 풀었던 문제다. 상차가 h층만큼 존재하기 때문에 1층만 있는 문제와 다른점은 한 지점에서 이동할 수 있는 방향이다. 2차원에서와 다르게 위, 아래로도 이동할 수 있으므로 총 6가지 방향에 대한 배열을 선언해주었다. 개인적으로 tuple을 사용하면 값에 대한 접근 방식이 귀찮아서 구조체를 더 애용하는 편이다. /* 20200..
알고리즘/baekjoon 2020. 5. 17. 21:59
[BOJ] 2293번: 동전 1

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 아주 아주 유명한 dp 문제다. dp[$k_j$] = 가치의 합이 $k_j$원이 되게 하는 경우의 수 즉, dp[5]의 경우 5원을 만들 수 있는 경우의 수를 저장한다. 이 문제를 풀기 위한 점화식은 dp[$k_j$] = dp[$k_j$] + dp[$k_j$ - coin[i]] 이때 주의할 점은 초기값 dp[0]을 설정해줘야 함이다. 그 값을 뭘로 설정해줘야 할지는 조금만 ..
알고리즘/baekjoon 2020. 5. 16. 20:29
[BOJ] 2565번: 전깃줄

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net LIS 문제였다. LIS에 대한 자세한 설명은 아래 글에 있다. https://hellooworld.tistory.com/21 [BOJ] 11053번: 가장 긴 증가하는 부분 수열 문제 링크: 백준/BOJ https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프..
알고리즘/baekjoon 2020. 5. 12. 18:08
[BOJ] 11053번: 가장 긴 증가하는 부분 수열

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 아주 전형적인 LIS 문제였다. LIS는 Longest Increasing Subsequence의 준말로, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제이다. 부분 수열은 연속적일 필요가 없다는 것을 명심하자. 만약, 부분 문자열(substring)이었다..
알고리즘/baekjoon 2020. 5. 12. 00:49
[LeetCode] 1004번: Max Consecutive Ones 3

문제 링크: https://leetcode.com/problems/max-consecutive-ones-iii/ Max Consecutive Ones III - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 학교 실습에서도 슬라이딩 윈도우 문제가 등장했기 때문에 더 중요성을 체감하는 중이다. 이 문제는 학교 실습 문제보다는 훨씬 간단한 슬라이딩 윈도우 문제였다. 두 포인터 start와 end는 모두 인덱스 0을 가리키는 상태에서 시작한다. 만약 end포인터가 가..
알고리즘/leetcode 2020. 5. 10. 21:54
Prev 1 2 3 4 Next