문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 두 수열의 공통 부분 수열 중 가장 긴 것을 찾는 문제였다. 문제 풀이 dp를 사용해 풀었다. dp 점화식을 말에서 식으로 바꾸는 것이 조금 헷갈렸지만 표를 그려보니 바로 이해가 됐다. 주어진 예시를 이용해 dp 배열을 만들면 위와 같은 모양이 된다. 0행 1열은 AC와 C의 LCS 길이, 1행 2열은 ACA와 CA의 LCS 길이가 된다. 그 ..
문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 얼리 아답터가 아닌 사람은 자신의 친구가 모두 얼리 아답터인 경우에 아이디어가 전파되는 상황에서 얼리 아답터의 최소 수를 구하는 문제였다. 문제 풀이 처음에 u - v의 관계가 항상 u가 부모, v가 자식이라고 생각하고 단방향 그래프를 만들어 풀었는데 그게 아닐수도 있었다. 처음의 풀이는 루트 노드를 찾은 다음 레벨 별 순회를 하며 해당 서브트리의 dp를 갱신해줬다. 하지만 무방향 그래..
문제 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 게임을 진행하면서 움직일 수 있는 동전의 최대 횟수를 구하는 문제였다. 문제 풀이 많은 시행착오가 있었고, 결국 다른 블로그를 참고해서 해결했다. 처음에는 단순히 백트래킹을 이용했는데, 6%에서 시간 초과가 나타났다. 이를 해결하기 위해서 좌표와 횟수, 방향 정보를 우선순위 큐에 넣어 bfs를 돌렸는데 해결되지 않는 경우가 있었다. 그리고 map의 각 칸에 set을 만들어 이전에 방문한 적이..
문제 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 각 도시별 홍보 비용과 이 비용으로 유치할 수 있는 고객이 정해져 있을 때, 호텔 고객을 C명 이상 늘리기 위해 투자해야 하는 비용의 최솟값을 구하는 전형적인 DP 문제였다. 문제 풀이 점화식을 세워서 dp 값을 계속 갱신했다. i는 비용이고 각 dp[i]의 값은 해당 비용으로 늘릴 수 있는 최대 사람 수로 정했다. 이때 dp 값이 C 이상일 때의 i가 정답이 된다. dp[i] = max..
문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 서로 붙어있지 않은 스티커를 골라 가장 높은 점수를 구하는 문제였다. 문제 풀이 N이 100000이라 완전탐색으로 풀면 시간 초과가 날 것 같아서 dp로 풀었다. 처음에 예시만 보고 점화식을 만들어 풀었더니 틀렸다고 나와서 반례를 찾아 점화식을 수정했다. 0 : 50 1 : 100 50+50 vs 10 -> 100 2 : 200 100+100 vs 50+70 -> 200 3 : 2..
문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 상담을 잡아 최대 이익 구해 출력하는 문제였다. 문제 풀이 문제를 보자마자 dp로 푸는 것은 알았는데, dp 식을 어떻게 짜야 할지 감이 잘 안잡혔다. 다른 사람의 코드를 참고했는데 왜 뒤에서부터 dp를 채울 생각을 못했을까..! 그래도 이번에 뒤에서부터 채우는 dp 문제를 풀어서 다음에는 괜찮을 것 같다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; ..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 모든 문제를 풀 수 있는 알고력과 코딩력을 구하는 데 걸리는 최소 시간을 구하는 문제였다. 문제 풀이 DP로 풀었다. cost 1로 알고력 1 올리기 cost 1로 코딩력 1 올리기 문제를 풀어 알고력/코딩력 올리기 처음 풀이로는 효율성 테스트 10번이 어떤 수를 써도 시간 초과가 나서(450 * 450 * 6) maxAlp * maxCop * problems 만큼 걸리도록 다시 풀었다. ..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/12971# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 원형 배열에서 스티커의 최대 합을 구하는 문제였다. 문제 풀이 dp를 이용해 풀었다. 첫 번째 스티커를 뜯는 경우와 뜯지 않는 경우를 나눠 dp를 구하고 max 값을 구했다. N이 1부터 시작인 것을 놓치고 sticker 배열의 size가 1,2인 경우에 예외처리를 해주지 않아서 2개 정도의 테케가 틀렸다고 나왔었다. 주어진 입력값의 범위를 항상 주의해서 보자! #include #inclu..
