profile
Pseudo-worker
태그 목록
전체보기 (96)boj(84)acmicpc(83)design patterns(6)leetcode(3)cuda(3)11409(1)01933(1)16947(1)화성 지도(1)03948(1)05419(1)01644(1)06087(1)서울 지하철 2호선(1)10422(1)01689(1)11066(1)02170(1)파일 합치기(1)05069(1)12844(1)09566(1)공장(1)01939(1)02169(1)02631(1)01572(1)텔레포트(1)02166(1)전화번호 목록(1)제독(1)11758(1)01561(1)14238(1)register(1)11689(1)sp(1)01750(1)01947(1)01377(1)가장 긴 바이토닉 부분 수열(1)shared-memory(1)NxM 보드 완주하기(1)Thread Hierarchy(1)global memory(1)01328(1)Interface Segregation(1)02494(1)트리의 지름(1)01280(1)사회 연결망 서비스(SNS)(1)이분 그래프(1)17069(1)01931(1)01300(1)cmicpc(1)사탕상자(1)열혈강호 5(1)01248(1)02252(1)Warp Scheduler(1)구간 합 구하기 2(1)06549(1)01513(1)01738(1)Single Responsibility(1)02533(1)01208(1)놀이 기구(1)그래프 매칭(1)체스판 여행 1(1)중앙값(1)11444(1)longest palindromic substring(1)고층빌딩(1)3Sum(1)최대 증가 직사각형 집합(1)방법을 출력하지 않는 숫자 맞추기(1)팔굽혀펴기(1)도로 포장(1)배열에서 이동(1)11408(1)오아시스 재결합(1)02092(1)constant memory(1)01162(1)소수의 연속합(1)포스터(1)01666(1)경로 찾기(1)크리스마스 트리(1)부분 문자열(1)02336(1)Memory Model(1)11405(1)열혈강호 6(1)abc(1)validate binary search tree(1)SOLID(1)파이프 옮기기 2(1)집합의 개수(1)03015(1)17070(1)03197(1)01655(1)Dependency Inversion(1)다각형의 면적(1)다리 만들기(1)01234(1)욕심쟁이 판다(1)04485(1)09944(1)02749(1)선물 전달(1)최소 스패닝 트리(1)나무 심기(1)선 긋기(1)12969(1)책 구매하기(1)히스토그램에서 가장 큰 직사각형(1)스위치(1)13392(1)03644(1)16916(1)맞춰봐(1)레이저 통신(1)택배(1)북서풍(1)개발환경(1)텀 프로젝트(1)02250(1)02146(1)부분수열의 합(1)11054(1)16959(1)파이프 옮기기(1)xor(1)녹색 옷 입은 애가 젤다지?(1)나머지 합(1)10986(1)01395(1)01707(1)Liskov Substitution(1)서로소의 개수(1)미로에 갇힌 상근(1)05052(1)10564(1)07578(1)구슬 탈출 4(1)12908(1)가운데를 말해요(1)괄호(1)백조의 호수(1)sm(1)11437(1)트리의 높이와 너비(1)버블 소트(1)스카이라인(1)01719(1)GCD(1)15653(1)출근 기록(1)보석 도둑(1)Ceiling Function(1)02243(1)홍준이의 친위대(1)03392(1)골목길(1)k번째 수(1)12767(1)01167(1)Open/Close(1)01983(1)10999(1)LCA(1)03640(1)굉장한 학생(1)숫자 맞추기(1)중량제한(1)로봇 조종하기(1)14391(1)01937(1)종이 조각(1)01197(1)줄 세우기(1)피보나치 수 3(1)피보나치 수 6(1)숫자 박스(1)겹치는 선분(1)줄세우기(1)ccw(1)01202(1)13167(1)
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

CUDA Memory Model

현생다망하여 올해는 더 이상 공부한 내용을 진득히 정리할 시간이 없다고 생각했었다.다행히도, 올해를 딱 1주 남겨두고 조금은 여유가 생겨 공부한 내용을 정리할 수 있게 되었다.이번 포스팅의 목적은 CUDA Programming Model - Memory Hierarch

2021년 12월 24일
·
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개의 댓글