https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. Logic 기본 DFS, 백트래킹 문제지만 시간복잡도때문에 메모이제이션을 활용하여 시간복잡도를 줄여줘야 한다. 즉 DFS와 DP를 합친 문제. 여기서 dp배열이 의미하는 것은 input[ny][nx]까지 갈 수 있는 경우의 수이다. 그리고 원래 DFS에서는 갔던 곳을 또 가지 않도록 무한루프에 빠지지 않도록 vis배열을 갱신해줘야 하지만 여기서는 항상 작은곳으로만 가기 때문에 vis배열을 갱신해 ..
백준
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 1. Logic 펠린드롬을 확인 할 때 문자를 뒤집어서 봤을 때 똑같으면 펠린드롬인데 이렇게 구현해버리면 시간복잡도가 2000 * 1000000 == 약 20억 정도 나오기 때문에 제한 시간 안에 풀지 못한다. 그래서 나는 재귀를 통해서 인덱스를 +1 -1씩 해주었고 펠린드롬이면 dp[start][end]에 1을 아니면 0을 넣어서 메모이제이션 해줬다. 2. Code #include using namespace std; int dp[2..
https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 1. Logic 각 PD들이 뽑은 가수의 순서대로 공연순서를 정하는 것이기 때문에 순서를 정할 때 사용하는 위상 정렬을 사용할 수 있다. 처음 입력을 받을 때만 잘 받아주면 어려움 없이 풀 수 있다. 테스트케이스를 예시로 보면 1 > 4 > 3 순서대로 받아줘야 하기때문에 1 > 4 4 > 3 끊어서 입력받아줘야 한다. 2. Code #include using namespace..
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 1. Logic 이 문제를 풀 때 중요한 키포인트는 두 가지 이다. 1. 1번 건물의 건설이 완료되어야만 2번과 3번 건물의 건설을 시작할 수 있다. 2. 2번과 3번의 건설을 동시에 진행 될 수 있다. 1번 건물의 건설이 다 끝나고 2번과 3번 건물을 건설하지만 3번 건물을 지을동안 2번 건물이 완성되더라도 아직 3번 건물이 다 안지어졌기 때문에 4번 건물을 짓지 못한다. 이 말은 항상 최..
https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 1. Logic 비숍이 움직일수 있는 특징은 검은색 칸은 흰색에 흰색은 검은색에 서로 영향을 주지 않는다. 그렇기 때문에 관점을 두개를 같이 보지말고 검은색은 검은색끼리 흰색은 흰색끼리 봐야한다. 이 특성을 이용하여 비숍을 놓기 위해서는 비숍을 놓을 위치의 대각선 방향에 다른 비숍이 있는지 없는지를 알고있어야 한다. N * N의 체스판에서 생기는 대각선의 갯수는 2N -1개이므로 N의 최대가 10이기 때문..
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 1. Logic - 구현은 항상 느끼는 거지만 문제에 있는 그대로 구현만 잘 하면 된다ㅋㅋㅋㅋ근데 실수하지 않고 구현하는게 어렵다ㅜ 풀이 로직을 보자면 한번 키보드를 누를 때 마다 블럭들을 이동시키면서 합칠게 있으면 합쳐줘야한다. 5번 옮길 수 있다고 했기 때문에 재귀를 사용하여 5번 움직이는 동안 블럭들을 상하좌우 옮겨주고 5번이 됐을 때 계산해서 블럭의 Value의..
https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. Logic LCS1 문제에서 구현한 것을 반대로 재귀호출을 한 다음 return 하면서 해당하는 문자 값을 출력하는 문제. LCS를 구할 때는 topdown으로 풀었는데 여기서 지나온 경로를 찾으려니 잘 안되어 다른 블로그를 참고하여 bottomup 방식으로 풀이했다 지나온 경로를 찾는 원리는 LCS를 구하는 과정에서 str1[s1-1] == ..
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. Logic 스탠다드한 이분탐색 문제이다. 주의할 점은 문제에서 포커스를 맞춰야 할 곳이 절단기에 설정할 높이를 구하는 것이고, 절단기에 설정한 높이를 나무의 길이에서 빼준 값으로 비교해야 한다는 점이다. 이분탐색이 이해가 잘 안간다면 아래의 알고리즘 설명글을 참고하면 좋을 것 같다! https://go2gym365.tistory.com/87 [Algor..
https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 1. Logic - 기본적인 LIS문제이다. 이 문제가 LIS인 이유는 전깃줄이 교차하지 않아야한다는 것은 이전 전깃줄의 번호가 다음 전깃줄의 번호보다 커지면 안되고 항상 작은 번호여야하기 때문에 증가하는 부분수열이 될 수 밖에 없다. 다른 LIS문제와 다른점은 단지 입력 값을 pair로 받아 준 다음 A를 기준으로 오름차순 정리해주고 B를 기준으로 LIS를 찾아주면 된다. 공부겸 시간복잡도가 O(nlo..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 1. Logic 기초적인 Tow pointer 문제지만 여기선 세개의 용액을 구해야하기 때문에 아이디어가 필요하다. 문제를 처음 보고 떠오른 아이디어는 한용액은 고정으로 하고 나머지 두개만 고르면 되겠다! 이거였다. 그리고 내가 생각한 아이디어가 맞았다. 기본 로직을 적어보자면 1. 0번째 인덱스부터 n - 2번째 인덱스 까지 for문을 돌면서 고정할 용액을 정한다. 2. 남..
