문제 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/15573 15573번: 채굴 첫째 줄에 N, M, K가 주어진다. (1 ≤ N, M ≤ 1000, 1 ≤ K ≤ N × M) 둘째 줄부터 맨 위의 광물들부터 순서대로 N줄 동안 M개의 광물의 강도 Si, j가 주어진다.(i = 1, 2, ..., www.acmicpc.net 채굴기의 성능 D보다 강도가 약하고, 공기와 맞닿은 광물만 채굴할 수 있을 때 K 이상을 채굴할 수 있는 최소 강도 D를 구하는 문제였다. 문제 풀이 D가 최대 1000000이고, map의 크기가 최대 1000000인 문제였기 때문에 완전 탐색이 불가능했다. 이전에 이와 비슷한 문제를 푼 적이 있어서 바로 이분탐색으로 D를 구하는 방법을 생각했다. 각 D마다 bfs를 진..
문제 https://www.acmicpc.net/problem/12892 12892번: 생일 선물 첫 줄에 친구의 수 N(1 ≤ N ≤ 100,000)과 미안함을 느끼게 되는 최소가격차 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 선물의 가격 P와 만족도 V(0 ≤ P ≤ 1,000,000,000, 0 www.acmicpc.net 가격의 차이가 D 미만이 되는 최대 만족도를 구하는 문제였다. 문제 풀이 투포인터를 사용하는 문제였는데 정렬을 한 후에 투포인터를 이용해 구간을 옮기며 해당 구간의 만족도를 구하고 최댓값을 갱신해 해결했다. /* 가격의 차이가 최대 D가 되는 최대 만족도 구하기 정렬 후 투포인터 */ int main() { int N, D; v..
문제 https://www.acmicpc.net/problem/12764 12764번: 싸지방에 간 준하 첫째 줄에 사람의 수를 나타내는 \(N\)이 주어진다. \((1 \le N \le 100,000)\) 둘째 줄부터 \(N\)개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 \(P\)와 종료 시각 \(Q\)가 주어진다. \((0 \le P \lt Q \le 1,000 www.acmicpc.net 모든 사람은 비어있는 자리 중 번호가 가장 작은 자리에 앉아야 한다. 다음과 같은 이용 규칙으로 모든 사람이 기다리지 않는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람이 사용했는가를 구하는 문제였다. 문제 풀이 처음에 비어있는 자리 중 번호가 가장 작은 자리에 앉는다는 규칙을 제대로 보지 않아서 틀렸었다. ..
문제 https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 내 친구의 친구는 내 친구이다. 내 원수의 원수도 내 친구이다. 해당 조건에 맞게 짠 가장 많은 팀 수를 구하는 문제였다. 문제 풀이 Union-Find 알고리즘을 이용해 풀었다. 친구와 원소 그래프 벡터를 따로 만들었고 조건에 맞게 makeUnion 해주는 과정을 반복했다. 친구끼리는 makeUnion을 해줬으며 원수일 경우에는 해당 원수의 원수 리스트 모두에 대해 makeUnion을 해줬다. team 개수를 찾을 때에는 set을 이용해서 다른 parent를 가진..
문제 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 체스판에 놓을 수 있는 비숍의 최대 개수를 구하는 문제였다. 문제 풀이 시간 제한이 10초나 되는 문제였지만 완탐으로 하니 시간 초과가 나왔다. 어떻게 줄여야 할지 감도 잡히지 않아 검색해 보니 비숍은 2가지 경우에는 절대 서로를 잡을 수 없다고 했다. 아래와 같이 o인 칸과 x인 칸은 아예 다른 경우로 생각하면 된다. 원래는 전체 칸을 다 살펴야 했지만 나눠 생각하면 o인 칸, x인 칸을 따로 생각..
문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 얼리 아답터가 아닌 사람은 자신의 친구가 모두 얼리 아답터인 경우에 아이디어가 전파되는 상황에서 얼리 아답터의 최소 수를 구하는 문제였다. 문제 풀이 처음에 u - v의 관계가 항상 u가 부모, v가 자식이라고 생각하고 단방향 그래프를 만들어 풀었는데 그게 아닐수도 있었다. 처음의 풀이는 루트 노드를 찾은 다음 레벨 별 순회를 하며 해당 서브트리의 dp를 갱신해줬다. 하지만 무방향 그래..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/1831 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N을 만들 수 있는 경우의 수를 구하는 문제였다. *++이 3단고음이고 *은 3을 곱하기, +는 1을 더하기이다. 3단고음 중간에 3단 고음을 실행할 수 있다. 문제 풀이 처음에 1에서 시작해 N을 만드는 방법으로 했는데, 시간 초과가 계속 났고 풀이를 참고해서 다시 풀었다.. N부터 시작해서 1까지 도달하게 했고, *는 3으로 나누기, +는 3으로 나눈 나머지를 빼도록 했다. 3으로 나눠진다..
