# acmicpc

90개의 포스트
post-thumbnail

배열 B의 값

그림을 그려보면 어렵지 않게 풀 수 있다.임의의 체스판이 주어졌을 때 각 원소가 몇 번씩 더해지는지를 그림으로 표현해보면 아래와 같다.황색 영역 : 1번 더해짐청색 영역 : 2번 더해짐적색 영역 : 3번 더해짐아무런 변경을 하지 않은 상태에서 B의 합을 B_init이라

2일 전
·
0개의 댓글
post-thumbnail

체스판 여행 1

처음에 DP + Floyd로 해결할 수 있을 것이라고 착각했다가 꽤 오랜 시간을 허비했다.문제를 잘못 이해했을 뿐 나름 나쁘지 않은 접근이었기 때문에, 제대로 된 풀이를 기술한 뒤에 DP + Floyd 풀이와, 왜 안되는지를 적어보고자 한다.제대로 된 풀이를 기술하면,

2022년 1월 14일
·
0개의 댓글
post-thumbnail

서울 지하철 2호선

DFS를 활용해서 그래프에서 사이클에 포함된 정점들을 검출한 뒤 해당 정점의 dist를 0로 초기화하여 Dijkstra를 통해 풀어주었다.무방향 그래프에서 DFS를 통한 사이클 검출에 은근히 애를 먹었는데, 인점한 정점이 부모 였을 경우는 사이클로 치치 않아야 하는 것

2022년 1월 14일
·
0개의 댓글
post-thumbnail

구슬 탈출 4

구슬들의 위치가 동일한 경우를 2번 탐색하는 것은 바보 같은 짓 이다. 따라서, 구슬들의 위치를 status로 하여 BFS를 수행해주면 되는 문제로 아이디어 자체는 매우 간단하다. 구현이 짜증나는데, 구현이 귀찮을 것이 예상되는 경우(빡구현...) 미리미리 OOP를

2022년 1월 14일
·
0개의 댓글
post-thumbnail

종이 조각

입력의 크기가 작으므로 간단한 백트래킹을 통해 풀어줄 수 있다.row major order로 각 위치에 대해서 배치할 수 있는 경우의 수를 한 번씩 시도해주면 된다.한 편, 가로로 연결한 칸을 1로, 세로로 연결한 칸을 0으로하여 비트마스킹으로도 풀어줄 수 있는데, 입

2022년 1월 14일
·
0개의 댓글
post-thumbnail

숫자 맞추기

13392번 문제인 방법을 출력하지 않는 숫자 맞추기 문제에 백트래킹만 추가해주면 되는 문제이다.상세한 풀이는 13392번 문제의 풀이를 참고하도록 하자.그래도, 아무것도 안 적어놓기는 멋쩍으니 아래와 같이 풀이를 적어 놓는다.Top-down DP를 활용하면 되고, 아

2022년 1월 14일
·
0개의 댓글
post-thumbnail

방법을 출력하지 않는 숫자 맞추기

Top-down DP 문제로, 역시나 내가 가장 취약한 부분답게 꽤 고전했다.Top-down DP 풀이를 바로 기술하는 것은 취약점 개선에 아무런 도움이 되지 않으므로, 최종 답안까지 가는 아이디어를 하나하나 차근차근 기술해보도록 하겠다.문제를 잘 관찰해보면 아래와 같

2022년 1월 14일
·
0개의 댓글
post-thumbnail

ABC

딱봐도 내가 잘하지 못하는 유형(DP + 백트래킹)의 문제임을 알 수 있어서 순간 쫄았었다.하지만, 마침 14238번 출근 기록 문제를 푼 직후라서 그런지 나름대로 빠른 시간 내에 풀 수 있었다.출근 기록 문제에서와 유사하게(사실 그렇게 비슷하지는 않지만) Top do

2022년 1월 14일
·
0개의 댓글
post-thumbnail

출근 기록

문제를 보고 2-30분 가량 감을 못 잡아서 문제 분류를 보았다.문제 분류는 다이나믹 프로그래밍으로 되어 있는데, 더욱이 감을 잡기가 어려워서...결국엔 답을 보았다.결론적으로는 재귀를 활용하는 Top-down DP 문제였는데, 골3인데도 헤매인 것 보면 이 부분에 대

2022년 1월 14일
·
0개의 댓글
post-thumbnail

텔레포트

마치 입력이 그리드인 것 처럼 주어져서 조금 혼란스러웠으나, 고려할 가치가 있는 정점이 어디인가에 집중하면 쉽게 풀어줄 수 있다.아래와 같은 노테이션을 활용하도록하자.(Xs, Ys): 시작점(Xe, Ye): 도착점(X11, Y11): 1번 텔레포트 중 한 쪽 입구(X1

2021년 12월 24일
·
0개의 댓글
post-thumbnail

Ceiling Function

문제가 영어인 관계로 굳이 다시 한 번 문제를 적어본다.이 문제는 임의의 수열이 N개 입력될 때, 각 수열을 Binary Tree로 구성한다면, 트리의 모양이 몇 가지가 나올 수 있는지를 묻는 문제이다.Full binary tree를 생각한다면, 우리는 각 노드의 위치

2021년 12월 24일
·
0개의 댓글
post-thumbnail

CCW

외적의 부호를 사용해주자

2021년 12월 24일
·
0개의 댓글
post-thumbnail

GCD(n, k) = 1

그닥 어려운 문제는 아니었지만, 여러 개념들을 복기해내야해서 나름대로 애를 먹었다.배울게 많아 좋은 문제라는 생각이 들어 조금은 공을 들여 기록을 남겨본다.참고로, 이 문제는 Euler's phi 함수를 사용하면 매우 쉽게 풀 수 있다.다만, 함수를 사용해서 풀다보면

2021년 12월 24일
·
0개의 댓글
post-thumbnail

LCA

입력의 크기가 매우 작아서 단순한 알고리즘으로도 풀린다.우선, 입력에 별도로 부모 자식 관계가 주어지지는 않으므로 입력을 그래프로 간주하여 받은 뒤 루트를 1번 노드로하는 BFS 트리를 생성해준다.이 때 각 노드의 깊이를 함께 구해주도록 하자.만약, a와 b의 LCA를

2021년 12월 14일
·
0개의 댓글
post-thumbnail

파일 합치기

매우 간단한 DP 문제이나, 테스트케이스 수가 주어지지 않아 "이게 정말 TLE 안나고 풀릴까?"를 고민하게 만드는 문제이다.간단한 DP로 풀어주면 TLE 안나고 정답이 나온다.CACHE 정의는 아래와 같이 한다.CACHE\[i]\[j]: 파일 i ~ j를 합칠 때 최

2021년 12월 14일
·
0개의 댓글
post-thumbnail

가장 긴 바이토닉 부분 수열

간단한 DP를 2번 돌려서 풀 수 있는 문제이다.INCR\[i]: NUMBER\[i]에서 끝나는 최장 부분 증가 수열DECR\[i]: NUMBER\[i]에서 시작하는 최장 부분 감소 수열자명하게 답은 max(INCR\[i] + DECR\[i] - 1)이 된다.

2021년 12월 14일
·
0개의 댓글
post-thumbnail

나머지 합

초반에 DP 문제겠거니 생각해보다가 DP 문제가 아님을 깨닫는데까지 시간이 조금 걸렸다.결과적으로 문제는 스위핑의 아이디어를 활용해서 풀었다.주어진 입력을 통해 풀이를 살펴보면 아래와 같다.1 2 3 1 2 입력에 대해 아래와 같이 PSUM을 함께 구해서 테이블로 표현

2021년 12월 14일
·
0개의 댓글
post-thumbnail

팔굽혀펴기

(1)DP로 풀어야 한다는 것, (2)CACHE 정의를 어떻게 세워야 한다는 것, (3)점화식을 어떻게 세워줘야 한다는 것 모두를 어렵지 않게 떠올릴 수 있었다.하지만, Iterative bottom-up DP를 고집하는 바람에 시간초과를 2번이나 맞았다.때때로, It

2021년 12월 14일
·
0개의 댓글
post-thumbnail

괄호

DP의 고전 of 고전 카탈란 수 문제이다.별다른 풀이는 없지만, 기억 열화를 막고자 점화식을 떠올리는 방법을 아래와 같이 적어 놓는다.편의상 N이 6이었다고 할 때, 아래 경우의 수를 헤아리면 중복/빠짐 없이 모든 경우를 헤아리게 된다.( ) \_ \_ \_ \_(

2021년 12월 14일
·
0개의 댓글
post-thumbnail

NxM 보드 완주하기

평이한 구현문제로 백트래킹을 잘 써주면 된다.구현이 빡세보이면 일찌감치 OOP를 도입하자는 교훈을 얻었다.

2021년 12월 14일
·
0개의 댓글