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]을 설정해줘야 함이다. 그 값을 뭘로 설정해줘야 할지는 조금만 ..

코로나 여파로 많은 일정에 차질이 생기고 있다. 특히 시험 일정.....ㅜ0ㅜ 정처기는 코로나로 개강도 밀리고 집에서 시간이 잘 안 가길래 남들 다 따는 거 한번 따 보자! 하는 마음에 공부를 시작했다. 1회 필기 접수를 할 때까지만 해도 코로나가 이렇게 길게 갈 줄 예상 못했었는데 어느덧 5월이라니. 정처기도 코로나를 피해 가지 못하고 이미 한차례 밀렸다. 다음은 큐넷 공지사항에 올라온 일정이다. 난 이미 2월에 1회를 접수했다가 취소한 상황이어서 접수 내역이 남아 있었기 때문에 1차 접수기간에 신청할 수 있었다. 만약 본인이 기접수자가 아니라면 사진이 안내하는 대로 14일부터 신청하면 된다.(단, 기사의 경우다.) 1회 신청 때도 신청 첫날부터 엄청 대기했던 기억이 있어서 오늘은 9시 30분에 알람까..

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