Hello World!

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

문제 링크: 백준/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..

문제 링크: 백준/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]을 설정해줘야 함이다. 그 값을 뭘로 설정해줘야 할지는 조금만 ..

문제 링크: 백준/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가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프..

문제 링크: 백준/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)이었다..

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹에 거의 정형화되어 있는 재귀 함수를 짜는 연습하기에 좋은 문제였다. 단, 문제에서 암호를 사전 순으로 출력하라 했으므로 재귀 함수를 호출하기 전에 문자들을 정렬해주었다. /* 20200401 baekjoon 1759번 암호 만들기 */ #include #include using namespace std; char arr[15]; char ans[15]; bool isC..