https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 1. Logic 이 문제는 유니온파인드 알고리즘으로 풀 수 있다. 그 이유는 한명이 거짓말을 듣게 되면 다른 사람도 거짓말을 알기 때문에 알고있는 사람 모두 노드로 연결하여 처리해 주는 것이다. 그리고 나중에 연결된 노드들에서 진실을 알고있는 사람이 있다면 제외해주면 된다. 2. Code #include using namespace std; int n, m, k; int node[51]; vector par..
Algorithm/Beakjoon
https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. Logic 완전탐색으로 이 문제를 풀게되면 2^40을 하면 약 1조정도가 나와 당연히 시간초과가 당연히 뜰것같았다. 그래서 시간복잡도가 O(logN)인 이분탐색을 써서 풀면되겠다는 생각을 했다. 이분탐색을 input의 반을 나눠서 왼쪽과 오른쪽 부분에 대해 탐색을 돌고 0~n/2까지의 구간의 부분수열의 합을 map에 넣어준다. n/2~n까지의 구간의 부..
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..
