BOJ

풀이 아이디어 > 참고자료 종만북 velog - 가장 긴 증가하는 부분 수열 k 17411 풀이 과정 $k$번째 답을 구하는 문제를 풀기 위해서는 아래의 과정을 따른다. 답의 수를 세는 문제를 푼다. 답의 수를 기반으로 답안을 재구성한다. 이 문제는 단순히 답의

우선 문제가 너무 길어 조금 내 방식대로 문제 정의를 다시해보면경찰차 1, 2가 있고, 각각 (1, 1), (N, N)에서 시작한다.첫째줄에 N이 주어지고, 둘째줄에 처리할 사건의 개수 m, 그 이후로 m줄동안 처리할 사건이 발생한 지점의 좌표가 주어진다.두대의 경찰차

완전탐색으로 우선 만들었고 여기에 DP 적용

문제 링크 메모리: 34120 KB, 시간: 68 ms그리디 알고리즘콘센트의 개수만큼 0으로 초기화된 리스트를 하나 만들어주고 앞에서부터 리스트를 확인해 들어온다.만약에 콘센트가 0이라면 무조건 일단 꼽고 본다.(단 아래 테스트 케이스처럼 비어있는 중에 같은 번호의 전

문제 링크 메모리: 31256 KB, 시간: 52 ms다이나믹 프로그래밍어쩌다보니 회고에 모든 내용을 썼으므로, 경우의 수를 찾는 과정만 따라간다.타일이 $1\\times3$, $3\\times1$이고, 채워야 할 판은 $4\\times n$이므로, 3의 배수가 아닌

우선 모든 방을 완전탐색하며 연결된 방의 불을 켠다.(1, 1)을 Parent로 하는 트리를 만들어 분리집합을 생성한다.해당 트리에 연결된 노드의 수를 센다우선 위 코드에서 간과한게 있다. (또 문제를 마음대로 읽어버렸다.) 문제에서 요구하는것은 "베시가 불을 켤 수

문제 링크 메모리: 33324 KB, 시간: 96 ms자료 구조, 그리디 알고리즘, 우선순위 큐, 정렬맨 처음에는 단순히 생각했었다. 점수별로 sort하고 날짜별로 sort 하는 방식이었는데, 이 경우에는 날짜가 지난 뒤 과제를 포기하지 못하는 문제가 있었다.두번째로

문제 링크 메모리: 32276 KB, 시간: 224 ms다이나믹 프로그래밍우선 완전탐색으로 구현한 뒤 dp를 적용한다. 완전 탐색의 경우 코드를 이해하는데 크게 어렵지 않다. 아래는 dp를 적용하지 않은 코드이다.문제를 조금 바꾸어 와일드 카드 하나를 더 추가해보자.

문제 링크 메모리: 38892 KB, 시간: 216 ms그래프 이론, 위상 정렬위상정렬이라는 카테고리를 알고 시작해서 그런지 생각을 도출해내는 방법은 간단하였다. 기본적인 위상정렬 코드이다.이 문제에서 위상 정렬을 사용하는 경우이자 사용할 수 있는 이유는 정답이 가능한

@@ -0,0 +1,44 @@문제 링크 메모리: 34520 KB, 시간: 976 ms다이나믹 프로그래밍, 그래프 이론, 위상 정렬위상 정렬이라는 큰 틀에 약간의 트릭을 섞었다. 같은 indegree에 있다면 동시에 건설이 가능하며, 다음 indegree를 건설하기 위해

문제 링크 메모리: 148656 KB, 시간: 4548 ms다이나믹 프로그래밍2차원 리스트에 각 행과 열을 왼발과 오른발로 설정한 뒤 메모이제이션을 적용한다.각 움직임별로 가중치를 두는 함수인 get_distance 함수를 따로 만들어 호출한다.함수 점화식을 다음과 같

문제 링크 메모리: 121364 KB, 시간: 528 ms다이나믹 프로그래밍이런 문제는 완전탐색에 기반하여 생각해야한다.고려해야할 변수가 3개이므로 3차원 dp를 생각했다.동전 분할이랑 비슷한 느낌임.고민 많이 한 부분은 어떻게 변화한 배열을 유지시킬까이다. 배열을 모

문제 링크 메모리: 258724 KB, 시간: 2388 ms다이나믹 프로그래밍바텀 업으로 진행하였고, 다음과 같은 점화식을 지정하였다$$T(n) = 3T(n-1) + T(n-2) - T(n-3)$$또한 recursion제한을 정수범위 $1e6$까지 해제해주었다.규칙을

일단 되돌아가기 과정을 생각하지 말고 구현먼저 했다.우선 문제 자체는 기본적인 "DP", "GRAPH" 형식을 띄고 있다.함수의 역할은 다음과 같이 정의하였다.$$S(n, depth) \\rightarrow \\text{만나기까지 걸린시간: depth}$$기저사례를 먼

문제의 조건이 2개이다.승률을 만족할 때, 그 점수가 소수(Prime number)일 확률을 구하는 문제이다.우선 까맣게 잊고 있던 이항계수에 대한 내용을 다시 한 번 정리해본다.이항계수는 주어진 크기 집합에서 원하는 개수만큼 순서 없이 뽑는 조합의 가짓수를 일컫는다.

가장 먼저 금민수가 될 수 있는 숫자들을 생성하는 함수를 하나 만들어 보았다.두번째 코드는 갯수만 세는 코드인데 다음과 같다.마지막은 역추적이다. 선택한 경우 별도의 리스트에 저장하여 선택을 고르도록 하였다.숫자가 4와 7 두개로만 표현되기 때문에 이진수로 표현 가능하

처음 육각수의 개수 1, 6, 15, 28, 45, 66은 첫 항이 5이고 d가 4인 등차수열이다.수열을 만드는데 가장 큰 수가 n보다 작을떄까지만 생성한다.위 수식을 일반항으로 바꾸어보면 다음 식이 성립한다.$$n(2n - 1)$$이를 기반으로 수열의 최댓값이 $n$

문제 링크 메모리: 33320 KB, 시간: 56 ms다이나믹 프로그래밍별 테크닉 없이 금방 풀이한 문제.

문제 링크 메모리: 46928 KB, 시간: 1348 ms다이나믹 프로그래밍1X1부터 $min(n,m) \\times min(n, m)$ 까지 크기를 늘려가면서 탐색한다.1\. 기준이 될 왼쪽 위의 한 점을 구하고, 장애물이 나오기 전까지 늘려나간다.2\. 장애물이

문제 링크 메모리: 47512 KB, 시간: 204 ms자료 구조, 해시를 사용한 집합과 맵, 누적 합, 트리를 사용한 집합과 맵맨처음 딕셔너리 생성시 0을 1로 초기화해주지 않아서 중복되는 문제 발생하였음조금 신경써줄것.누적합 개념을 처음 공부해봤는데 생각보다 쉬운개

문제 링크 메모리: 31120 KB, 시간: 44 ms브루트포스 알고리즘, 기하학, 수학2023년 10월 11일 20:04:00맨 처음에는 선분간의 교차판정을 통해 하려고 ccw 알고리즘에 대해 알아봤는데 굳이 그럴 필요 없을 것 같아 기울기 판정으로만 문제를 풀이하였

문제 링크 메모리: 207616 KB, 시간: 1404 ms슬라이딩 윈도우, 두 포인터우선 코드부터 첨부한다.아이디어는 연속으로 먹은 초밥을 슬라이싱하고, 최대한 많은 종류의 초밥을 먹어야하므로, set을 이용해서 중복을 제거한 개수를 저장해주었다.지금 와서 보니까 문

문제 링크 메모리: 34856 KB, 시간: 2820 ms백트래킹, 비트마스킹, 브루트포스 알고리즘2023년 10월 9일 18:26:22일단 남극어는 anta - tica 구조이므로 집합 {a,c,i,n,t}를 제외한 나머지 조합탐색을 통해서 한다.무작정 찾게 되면 시

문제 링크 메모리: 33188 KB, 시간: 120 ms데이크스트라, 그래프 이론, 최단 경로2023년 12월 23일 13:18:40맨 처음 어떻게 최단경로를 집어넣을까 많은 고민을 했었다.다익스트라도 어찌보면 다이나믹프로그래밍의 일종이므로 완전탐색에서부터 찾아나가기로

문제 링크 메모리: 42172 KB, 시간: 116 ms이분 탐색, 정렬, 두 포인터양 끝단부터 탐색해오기 시작해서 탐색 값이 지금까지 탐색해온 값보다 작다면 mmin, r1, r2에 저장하고, 아니면 범위를 좁히는 방식으로 탐색하였다.이때 양 끝단의 합이 음수라면 s

문제 링크 메모리: 39268 KB, 시간: 1000 ms이분 탐색, 매개 변수 탐색최적화 문제를 결정문제로 바꾼다 라는 가장 기초적인 개념에서부터 아이디어를 구상하였다.start는 0으로, end는 모든 사람이 가장 오래걸리는 창구로 가는 $$m\*max(lst)$$

문제 링크 메모리: 43012 KB, 시간: 532 ms자료 구조, 분리 집합, 그래프 이론, 그래프 탐색처음 아이디어는 분리집합을 이용해 부모가 다른것을 선택하는 것 이었는데, set()이용 중복을 제거하고, 서로 다른 집합의 대표 노드를 뽑는 과정에서 잘못되었었다.

문제 링크 메모리: 57488 KB, 시간: 4568 ms이분 탐색, 매개 변수 탐색최대 거리를 lst\[0] 과 lst\[-1] 사이의 거리를 기준으로 mid를 구했을 때, 꼽을 수 있는 콘센트의 개수가 s 보다 크거나 같으면 upper_bound로 탐색범위를 재 설

Top-Down 방식으로서, 입력된 동전을 하나씩 빼는 과정을 통해 모든 경우의 수를 순회하고, DP를 통해 중복되는 계산을 제거한 뒤, 순서가 달라 중복되어 나오는 계산을 배제한다.순서가 달라 중복이 된다는 말은 아래 예시를 통해 알 수 있다.이 경우에 나올 수 있는

문제 링크 메모리: 38964 KB, 시간: 176 ms다이나믹 프로그래밍여러 시도 끝에 점화식 비스무리한 것을 만들어냈다$$F(n) = max\\begin{cases}S(n) + F(n-1)\\\\sum{S(i)} - S(n) |i\\in S\\end{cases}$$

문제를 풀기 위한 몇가지 조건을 생각해봤다.선택된 휴식지보다 높아야 한다.더 많은 길을 지나갈 수 있어야 한다.선행 조건으로는 그래프를 만들어서 연결성을 부여해주어야한다.보통 그래프를 구현할 때에는 인접행렬 또는 인접리스트로 구현 가능하다.그래프를 구현할 때 최대 크기

문제 링크 메모리: 213080 KB, 시간: 884 ms다이나믹 프로그래밍, 배낭 문제"탑다운"으로 풀고 싶다 라는 생각이 들었고, 배낭문제를 연습하려 했지만, 뭔가 일반적인 배낭문제와는 조금 다른 응용이라고 생각되었다. 지금 생각해보니 문제를 뒤틀어 생각하면 그냥

문제 링크 메모리: 33320 KB, 시간: 48 ms다이나믹 프로그래밍두 전깃줄이 교차한다는 것은 무엇일까.전깃줄 $A_i \\to B_i$와 $A_j\\to B_j$가 있을때 $A_i < A_j | B_j < B_i$ 또는 그 반대면 전선이 교차한다.예전

[Gold V] 귀찮은 해강이 - 24391 문제 링크 성능 요약 메모리: 46032 KB, 시간: 296 ms 분류 자료 구조, 분리 집합, 그래프 이론, 그래프 탐색 문제 설명 해강이는 앙중대학교에 다닌다. 해강이는 이번 학기에 강의코드 1번부터 N번까

문제 링크 메모리: 126920 KB, 시간: 620 ms자료 구조, 분리 집합, 그래프 이론, 그래프 탐색기본적인 Union-FInd 문제라 단순 구현만 하면 되었음.어제 오랜만에 Union-Find 문제를 풀어봤고, 재밌어서 날먹차 하나 풀어본 문제임. DP 골드에

문제 링크 메모리: 31256 KB, 시간: 68 ms브루트포스 알고리즘, 그리디 알고리즘, 정렬처음 생각한 아이디어는 각 시간에 대해 진행되는 파티의 가중치를 두고 (더 긴 파티의 경우 이른 시간에 더 큰 가중치를 두어 선택을 유보하는 방식이다.) 개수를 세어나가는

문제 링크 메모리: 119664 KB, 시간: 352 ms너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현쓸데없는 부분을 놓쳐서 시간을 허비한 문제..시간복잡도를 개선하기 위해서는 우선순위 큐를 사용하는 방법도 있으나, 파이썬으로도 돌아가는걸 보니 일단은 괜찮다.

[Gold V] 강의실 배정 - 11000 문제 링크 성능 요약 메모리: 73584 KB, 시간: 400 ms 분류 자료 구조, 그리디 알고리즘, 우선순위 큐, 정렬 문제 설명 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한

문제 링크 메모리: 39872 KB, 시간: 832 ms백트래킹, 브루트포스 알고리즘선생님이 볼 수 있는 구간을 모두 큐에 넣는다.그 구간에 학생이 걸린다면 바로 이전 칸에 장애물을 넣는다.만약 장애물을 모두 썼다면 피할 수 없음. (나머지 큐를 모두 돌아봄.)그러면

문제 링크 메모리: 34092 KB, 시간: 432 ms구현, 시뮬레이션우선 width, height대로 실제 그래프를 만들고, 빗물이 떨어진다면 아래의 조건을 만족한 경우 빗물이 고일수 있으므로 그대로 구현하였다.1\. 일단 비는 내린다2\. 양쪽이 막혔는지 확인한다

문제 링크 메모리: 51424 KB, 시간: 2168 ms데이크스트라, 그래프 이론, 최단 경로2023년 12월 19일 12:14:40다익스트라 기본 문제오랜만에 ps 포스팅인 것 같다.최단경로 공부하고 처음 풀어보는 문제.양방향 그래프인데 양쪽으로 업데이트해주는것을

문제 링크 메모리: 119716 KB, 시간: 1024 ms데이크스트라, 그래프 이론, 최단 경로2024년 1월 2일 13:36:37그래서 아이디어 검증 차 모든 점의 최단거리를 구하고 (적의 시야에 닿는 정점은 제외한다.) 출력하려는 찰나, 그렇게 하지 않아도 못가는

문제 링크 메모리: 31256 KB, 시간: 44 ms분할 정복, 재귀직관적으로 봤을때 아래 과정이 반복된다.x, y를 시작으로 한다x, y+1을 방문한다.x+1, y을 방문한다.x+1, y+1을 방문한다.따라서 분할 범위를 반씩 줄여나가다가, 크기가 1이 되면 카운트

문제 링크 메모리: 31256 KB, 시간: 56 ms분할 정복, 재귀이때까지 풀이한 문제랑 비슷하나, 출력 형식을 조금 고민해야 했던 문제.어떻게 나눌것인가가 중요한데, $n/2$로 분할하여, set을 이용해 집합에 같은 원소가 몇개인지 확인 후 그 크기가 1이거나

문제 링크 메모리: 31256 KB, 시간: 44 ms다이나믹 프로그래밍직접 종이에 규칙을 그려보았더니, N+1번째 행의 0번째 열이 N번째 행의 합과 같았다.직접 만든 점화식은 아래와 같다$$Ni = Sum((N-1)i:) \\rightarrow i=0\\Ni = N

문제 링크 메모리: 80948 KB, 시간: 740 ms그래프 이론, 그래프 탐색퓨처테크아케데미(주)는 올해로 4년째 엘리트 알고리즘 SW교육-「헬로알고」라는 브랜드로 국내는 물론 해외 14개국 청소년들을 대상으로 SW교육을 실시하고 있는 교육회사입니다. 또한 중소벤처

문제 링크 메모리: 63904 KB, 시간: 432 ms다이나믹 프로그래밍처음 DP라고 결정하고 문제를 풀기 시작하였다. 구하고자 하는 것이 m 이하의 수를 사용한 n 만들기인데, 따라서 필요한 변인이 2개 $$DP\\text{만들고자하는 수}$$로 결정내리고 2차원

풀이 아이디어 가장 먼저 생각난 것은 그냥 그래프 빡구현이였다. 단순하게 생각해서 유향그래프를 만든 뒤, 두가지 경우의 분기를 정해주었다. 해당 양동이에서 더이상 갈 수 있는 호스가 없는 경우 호스가 있어 아래로 흐를 수 있는 경우 1번의 경우 가장 밑바닥까지 내

문제가 요구하는 사항만 짧게 정리한다.카트는 (0, 0)에서 시작하며 (N, M)에 도달하면 프로그램을 종료한다.각 격자마다 아이템(부스터)의 개수가 주어지며, 부스터가 있다면 오른쪽 또는 아래쪽으로 최대 부스터 만큼 움직일 수 있다.이때 가장 최소 이동거리를 구해라문

문제 링크 메모리: 31256 KB, 시간: 380 ms백트래킹, 브루트포스 알고리즘백트래킹의 아이디어를 가지고 모든 경우의 수를 완전탐색 하였다.1\. DFS함수에 시작값을 집어넣는다. (매개변수는 인덱스 번호임.)2\. 만약 들어온 매개변수 값이 탈출조건을 만나면

Silver II 색종이 만들기 - 2630 문제 링크 메모리: 31256 KB, 시간: 80 ms분할 정복, 재귀 이 문제와 정확히 같은 풀이법을 사용하였다.문제를 보자마자 앗 이거다 라는 느낌이 와서 풀이하였다. 사실 그래프 형태의 분할정복은 다 이런 형태를 기

문제 링크 메모리: 369804 KB, 시간: 2744 ms분할 정복, 재귀문제에서 예시로 준 데이터를보면 위 그림과 같이 0의 개수를 센다.우선 찾을 정사각형의 가장 왼쪽 x,y 좌표를 찾은 뒤, 탐색하는 정사각형의 크기 N만큼 탐색하여 다른것이 있다면 재귀, 모두

문제 링크 메모리: 34332 KB, 시간: 140 ms너비 우선 탐색, 브루트포스 알고리즘, 그래프 이론, 그래프 탐색상어가 있는 칸을 기준으로 그래프의 값이 0인 부분이 나온다면 dep에 저장한다.나올 수 있는 조건은 아래 3가지 인데해당 구역을 방문 안한 경우방문

문제 링크 메모리: 32276 KB, 시간: 52 ms자료 구조, 구현, 시뮬레이션, 스택몇번 움직여보니까 필요한 전체 로직의 흐름은 다음과 같다.처음은 1번 bar에서 시작한다1번 bar에서 2번 bar로 원판을 옮긴다이때 원판의 크기를 $n$부터 역순으로 선택하여

문제 링크 메모리: 49444 KB, 시간: 408 ms이분 탐색최적화문제를 결정문제로 바꾸는것을 정하는것이 가장 중요하다고 판단.맨 처음에는 이걸 이분탐색으로 왜 풀지? 라는 생각을 했었는데, 입력한 값이 정말 너무너무 커질수가 있어서 납득..이분탐색으로 탐색할 부분

문제 링크 메모리: 31256 KB, 시간: 72 ms이분 탐색

문제 링크 문제 풀이 시간 : 6분 51초메모리: 31256 KB, 시간: 44 ms그리디 알고리즘, 구현, 시뮬레이션랑이 집사는 고양이들이 좋아한다는 캣닢을 직접 재배하려고 한다.일직선으로 놓여진 $N$개의 화분에 캣닢이 하나씩 심어져 있다.각 화분은 초기에 $K$만

문제 링크 메모리: 34168 KB, 시간: 440 ms너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색기본 BFS/DFS 문제이며 방문한 \`\`\`\`pythonfrom collections import dequedef bfs(graph, x, y, n

문제 링크 메모리: 41032 KB, 시간: 380 ms이분 탐색, 수학, 오프라인 쿼리, 두 포인터2차원 좌표 평면에 점 $N$개가 주어진다. $i$번째 점의 위치는 $(xi, y_i)$이고, $1 \\leq i \\lt N$인 모든 $i$에 대하여 $x_i \\lt

문제 링크 메모리: 73104 KB, 시간: 644 ms분할 정복, 재귀

문제 링크 메모리: 34128 KB, 시간: 76 ms그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색무난한 코드를 원한다면 BFS를 쓰면 될 것 같아 우선 그걸로 제출했는데, Union-Find를 이용 할 수 있지 않을까? 라는 생각이 들어 도전하게 되었

문제 링크 메모리: 31388 KB, 시간: 44 ms이분 탐색, 브루트포스 알고리즘, 수학아이디어 자체는 간단하다. 버스 도착 시간을 간격별로 버스 대수만큼 리스트를 만들어준다. 이때 만들어준 리스트는 오름차순이 보장되므로 따로 정렬 할 필요는 없다.버스 도착 정보

문제 링크 메모리: 114328 KB, 시간: 296 ms그리디 알고리즘맨 처음 아이디어로는 lst를 돌면서 만약 해당 인덱스에 있는 값이 목표 값보다 작다면 빼주는 방식으로 돌렸다두번째 (회고 란에 있는 코드)는 한번에 계산할 수 있는 만큼 돌렸다.1번 코드로 했을떄

문제 링크 메모리: 31256 KB, 시간: 56 ms임의 정밀도 / 큰 수 연산, 이분 탐색, 수학이걸 어떻게 풀까 라는 생각이 들었고, 그냥 sqrt()로 일단 질러보기로 했다. (파이썬은 위대하니까...!) 하지만 OVERFLOW가 났고, 이분탐색을 할 수 있는

문제 링크 메모리: 31256 KB, 시간: 48 ms이분 탐색, 수학위 벌집은 다음 수식을 따른다$$\\sum\_{n=1}^{1e18}6n$$일때 $$n$$즉, 이를 정리해서 이분탐색해 $$3n(n-1) + 1$$을 넘지 않는 $$n$$의 값을 찾는것인데 이를 코드

문제 링크 메모리: 33320 KB, 시간: 136 ms이분 탐색, 정렬bisect 모듈을 이용해 이분탐색을 구현하기로 했다.아래는 bisect에서 사용하는 함수들이다.위 두 특성을 이용하여 약간의 응용을 거쳤다.문제에서 요구하는 기능은 아래 3가지이다.k 보다 크거나

문제 링크 메모리: 32000 KB, 시간: 128 ms구현, 재귀우선 n=4일때 결과에 대해 보면 아래와 같다이를 유심히 들여다보니 아래 두 규칙이 합쳐진 형태이다1을 90도 회전한 모양이 두 규칙을 합치는 코드이며, 값을 저장하기 위해 배열을 이용하였다.규칙에 대한

문제 링크 메모리: 222252 KB, 시간: 1780 ms이분 탐색, 자료 구조, 해시를 사용한 집합과 맵, 두 포인터단순히 이분탐색 문제로 인식하였고, 문제에서 오름차순으로 주어진다고 하였으므로, 정렬은 따로 필요하지 않습니다.따라서 이분탐색의 시간복잡도인 $$O(

문제 링크 메모리: 31256 KB, 시간: 48 ms조합론, 다이나믹 프로그래밍, 수학DP를 처음 연습해보기 위해 풀이했던 기초 문제점화식을 아래와같이 작성하였고, Bottom Up 방식으로 반복문을 사용하여 풀이하였다.$$\\begin{cases}a{(0,0)} =

참가자의 수와 장르가 주어지고, 장르마다 각 참가자의 능력을 실수형 데이터로 나타냈다. 각 참가자는 하나의 장르만 부를 수 있으며, 한 장르는 여러 참가자들에 의해 불려질 수 있다. 이떄 능력의 합이 최대가 되도록 참가자와 장르를 선택해라.이래저래해서 풀었다.맨

실버 문제 풀이

기본적인 미로탐색 문제, 그래프의 1인 부분만 밟고 (0, i)에서 (N, i) | 0 <= i <= N 까지 가는 최단경로를 구하는 문제res의 최댓값을 대충 99999 로 정했다가 틀렸습니다가 나온 문제, 어렵진 않았는데 이런 사소한 실수때문에 한

문제 링크 메모리: 34072 KB, 시간: 64 ms0-1 너비 우선 탐색, 너비 우선 탐색, 데이크스트라, 그래프 이론, 그래프 탐색, 최단 경로2024년 1월 3일 11:19:54가중치가 0-1밖에 없었기에 0-1BFS로 풀이가 가능하다고 판단하고 설계하였다.감이

문제 링크 메모리: 64280 KB, 시간: 516 ms데이크스트라, 그래프 이론, 최단 경로2024년 1월 3일 17:55:18문제에서 정해준 "두 지점"을 경유해서 가면 되는데 설계에 대해 생각이 잘 나지 않았다.다익스트라 알고리즘을 우선 만들고 나서 생각을 시작했

문제 링크 메모리: 34240 KB, 시간: 944 ms데이크스트라, 플로이드–워셜, 그래프 이론, 최단 경로2024년 1월 4일 20:25:31당연히 다익스트라 문제에 조금 비튼 응용문제였다.각 출발점에서 모든 방에 대한 정보를 리스트로 반환하는 함수를 만든 뒤, 결

문제 링크 메모리: 35260 KB, 시간: 1292 ms데이크스트라, 플로이드–워셜, 그래프 이론, 최단 경로2024년 1월 5일 20:48:15다익스트라 사용후 disjoint set에서 부모 노드를 찾아가는 방식을 응용하여 가장 처음으로 지나가는 노드를 역추적하는

업로드중..문제 링크 메모리: 31120 KB, 시간: 44 ms게임 이론, 스프라그–그런디 정리2024년 2월 5일 18:37:04grundy 수에 대한 이론을 기반으로 풀이게임이론 중 그런디 수와 님게임에 대한 공부를 하고 풀이한 문제로,, 플레 4는 완벽하게 이론

$n \\times m$ 크기의 땅이 있을때 석유가 있는 땅을 1 그렇지 않은 땅을 0이라고 한다.석유 시추를 할 때 가장 많은 석유를 시추하는 땅을 고른다세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습

문제 링크 메모리: 34064 KB, 시간: 84 ms그리디 알고리즘, 정렬2024년 2월 9일 21:25:13새로 배운것은 cmp_to_key를 통해 정렬의 key를 커스터마이징 할 수 있다는 것을 알았다.이때 Tim Sort라는 방식으로 인덱스에 접근하고, 비교하는

BOJ-13305 S3🥈 주유소 풀이 소요시간 : 15분 ⏰ 회고 아이디어를 떠올리는게 어렵지 않았다. 풀고나서 알아보니 "스탈린 정렬🛠️" 이라는 이름이 있었다..ㅋㅋ 현재 지점의 주유소 가격이 다음 주유소 가격보다 비싸다면 다음 주유소에서 쳐낸다.

풀이 방법은 보자마자 떠올려서 분리집합을 사용하기로 하였다. 다만 두가지 부분에서 애를 먹었는데 우선 집합을 합친 다음 한번 find로 재탐색 해주어야 제대로 된 부모노드를 저장할 수 있고 다음으로 나눈 결과가 한개인 경우 마지막 리스트에 값이 9, 0 즉 한 뭉텅이로

안올리려다가 구현이 생각보다 복잡했어서 생각 정리할겸 블로그에 정리한다.문제에서 예제 출력만 꼭 정답이 아니라고 했으니 겹쳐있을 수 있는 모든 십자가 중 가장 큰 십자가를 찾아서 세어주는 과정을 반복해야 한다. \- 여기서 첫번째 실수 : 정답이 여러개라는 설명을 무

이번엔 다익스트라에 경로까지 탐색하는 방법이다.이전에 LIS나 경로 찾기에 관해 문제를 풀어본 경험이 있어서 대충 감은 왔는데 너무 오래되어 잊어버린 듯 하다.복기하면서 문제를 풀이하였고, 마지막에 출력하는 방법까지 숙지하였다.

이분탐색으로 풀이가 가능한듯하다.반례상황이 많아서 고생했다.찾아봐도 정답 코드가 안나와서 비교를 위해 자바 코드를 바꿔봤다.

DP는 사각형의 우측 하단을 기준으로 만들 수 있는 최대 크기의 정사각형의 크기를 저장한다.최대 크기의 정사각형을 찾는 방법은 오른쪽, 위쪽, 오른쪽 위의 DP를 확인하고 (사각형의 확장 가능성) 그 중 가장 작은 DP 값에 +1을 하면 됨.점화식은$$DPi = min