# acmicpc

123개의 포스트
post-thumbnail

불 끄기

Problme link: https://www.acmicpc.net/problem/14939행 단위로 각 행에 있는 전구를 누를지 말지 결정한다고 해보자.i번쨰 행의 j번째 열에 위치하는 전구를 고려할 때, 사실 얘를 누를지 말지는 i-1행 j열의 전구가 결정

2022년 4월 3일
·
0개의 댓글
·
post-thumbnail

가장 긴 증가하는 부분 수열 5

Problme link: https://www.acmicpc.net/problem/14003별로 특별할 것 없이 lower_bound를 사용해서 풀어주면 LIS의 길이까지는 무리 없이 구해줄 수 있다.여기서 실제 LIS를 재구성해내는데 조금 어려움을 겪었는데,

2022년 4월 3일
·
0개의 댓글
·
post-thumbnail

1로 만들기 2

Problme link: https://www.acmicpc.net/problem/12852포인트 냠냠을 위한 BFS 문제이다.숫자가 작아지면 작아지지 커질 수는 없다는 사실로부터 범위 내의 양수들만 접근하리라는 것을 알 수 있다.

2022년 4월 3일
·
0개의 댓글
·
post-thumbnail

본대 산책 2

Problme link: https://www.acmicpc.net/problem/12850Adjacent Matrix로 입력을 나타내고 이를 M이라고 하자.이때, M\[i]\[j]는 i번 건물에서 j번 건물에 도달하는 경우의 수를 나타낸다고 하자.이렇게하면,

2022년 4월 3일
·
0개의 댓글
·
post-thumbnail

가장 긴 증가하는 부분 수열 2

Problme link: https://www.acmicpc.net/problem/12015사람마다 푸는 방법은 여러가지가 있을텐데, 나는 그중에 가장 무지성으로 풀 수 있는(물론 복잡도는 다른 알고리즘에 뒤지지 않는다) lower_bound 풀이를 사용했다.

2022년 4월 3일
·
0개의 댓글
·
post-thumbnail

행렬 곱셈 순서

Problme link: https://www.acmicpc.net/problem/11049그닥 어려울 것 없는 DP 문제로 쉽게 쉽게 풀어줄 수 있다.아래와 같이 CACHE를 정의하자.CACHE\[s]\[e]: Matrix\[s]부터 Matrix\[e]까지

2022년 3월 23일
·
0개의 댓글
·
post-thumbnail

팰린드롬?

Problme link: https://www.acmicpc.net/problem/10942문제 설명이 조금 부족한데, 숫자 하나를 문자 하나로 취급해야 한다.여튼 노말하게 DP를 써주면 풀리는 문제이다.아래와 같이 CACHE를 정의하자.CACHE\[s]\[e

2022년 3월 23일
·
0개의 댓글
·
post-thumbnail

공항

Problem link: https://www.acmicpc.net/problem/10775이진 트리(i.e. std::set)을 활용해서 풀어주었다.쉽게 풀고나서 혹시나 하는 마음에 문제 분류를 보니 Disjoint Set을 활용해서도 풀어줄 수 있는 모양이

2022년 3월 18일
·
0개의 댓글
·
post-thumbnail

열쇠

Problem link: https://www.acmicpc.net/problem/9328빡 구현 문제이다.아래의 순서로 풀어주면 된다.더 이상 새로운 열쇠도 발견하지 못하고, 문서도 발견하지 못할 때까지 \- 있는 열쇠로 열 수 있는 모든 문을 열어버린다(

2022년 3월 16일
·
0개의 댓글
·
post-thumbnail

LCS 2

Problme link: https://www.acmicpc.net/problem/9252전형적인 DP문제이고, DP 완료 후 백트래킹 정도가 추가된 문제이다.아래와 같이 CACHE를 정의하자.CACHE\[i]\[j]: A\[0...i], B\[0...j]까지

2022년 3월 15일
·
0개의 댓글
·
post-thumbnail

행성 터널

Problme link: https://www.acmicpc.net/problem/2887문제를 보는 순간 바로 MST문제로 분류할 수 있었다.하지만, 입력이 사실상 fully connected graph이므로 Prim이건, Kruskal이건 바로는 사용하지

2022년 3월 13일
·
2개의 댓글
·
post-thumbnail

음악프로그램

Problme link: https://www.acmicpc.net/problem/2623간단한 위상정렬 문제로 볼 수 있다.각 가수를 그래프의 정점으로, 인접한 두 순서를 간선으로 표현한다면 입력은 그래프로 표현될 수 있다.그래프의 순서를 유지하는 위상정렬

2022년 3월 13일
·
0개의 댓글
·
post-thumbnail

세 용액

Problem link: https://www.acmicpc.net/problem/2473정렬된 배열에서 서로 다른 3개의 원소 a, b, c를 뽑아 a + b + c = 0이 되도록하는 경우를 헤아리는 문제와 비슷하다.a <= b <= c가 되도록

2022년 3월 6일
·
0개의 댓글
·
post-thumbnail

Dance Dance Revolution

Problme link: https://www.acmicpc.net/problem/2342그닥 어렵지 않게 풀 수 있는 DP 문제이다.아래와 같이 CACHE를 정의하였다.CACHE\[i]\[l]\[r] = i번째 입력까지 밟고, 오른발이 r, 왼발이 l에 있을

2022년 3월 5일
·
0개의 댓글
·
post-thumbnail

스도쿠

Problme link: https://www.acmicpc.net/problem/2239별 볼일 없는 백 트래킹 문제였다.포인트 냠냠

2022년 3월 5일
·
0개의 댓글
·
post-thumbnail

용액

Problem link: https://www.acmicpc.net/problem/2467노말한 투 포인터 문제로, 서로 반대 방향에서 출발하는 투 포인터 알고리즘을 사용해주자.

2022년 3월 5일
·
0개의 댓글
·
post-thumbnail

선분 그룹

Problme link: https://www.acmicpc.net/problem/2162문제가 어렵다기 보다는 자료구조를 여러개 써줘야한다.CCW를 활용한 선분 교차여부 판단을 위해서 벡터, 라인 자료구조를 사용하였고,그루핑을 위해 서로소 집합을 사용하였다.

2022년 3월 4일
·
0개의 댓글
·
post-thumbnail

두 배열의 합

Problme link: https://www.acmicpc.net/problem/2143각 배열의 모든 부분합들을 미리 구하여 저장해놓는다.이렇게 구해진 두 개의 부분합 배열을 각각 CAND_A, CAND_B라고 하자.두 부분합 배열을 정렬한 뒤에 서로 다른

2022년 3월 4일
·
0개의 댓글
·
post-thumbnail

외판원 순회

Problme link: https://www.acmicpc.net/problem/2098고전적인 문제이니만큼 DP를 잘 활용해서 풀어주면 무난하게 풀린다.단, 한 가지가 가물가물해서 조금 시간을 버렸는데 아래 사실을 유념하도록 하자.어느 도시에서 시작하는 순

2022년 3월 4일
·
0개의 댓글
·
post-thumbnail

부분합

Problme link: https://www.acmicpc.net/problem/1806같은 위치에서 출발하는 투 포인터를 써준다.

2022년 2월 23일
·
0개의 댓글
·