https://www.acmicpc.net/problem/19663 정말 어려웠던 세그트리 연습문제처음에는 뭔가 DP일 것 같았고, 실제로 분류에도 DP가 있어서 DP로 풀이를 짜고, 세그트리로 최적화시키는 건가 싶었다.하지만 아무리 고민해도 DP 점화식이 생각이 안났고, 세그트리로 구현하는 방법만 계속 떠올랐다. 문제 이해수열이 주어질 때, 주어진 수열에서 인덱스 순에 맞게 3개의 수를 뽑아 만든 임의의 튜플 (x, y, z) 에 대해, x  첫 번째 시도알고리즘 분류에 있는 '정렬' 에서 힌트를 얻어 먼저 데이터를 높이순으로 정렬한다.어떤 기준점 y가 정해졌을 때, 이 값보다 작은 값들 중, y보다 왼쪽에 있는 값의 개수, 오른쪽에 있는 값의 개수를 센 뒤,두 값을 곱한 결과를 정답에 더해주면 된다...

https://www.acmicpc.net/problem/11003 티어는 플레티넘 5인데, 우선순위 큐로 너무나도 간단히 풀리는 최강 날먹(?) 문제질문 게시판을 보니, 덱을 이용해서 O(n) 에 풀 수 있도록 최적화 하는 것이 이 문제의 의도같은데, 입출력값이 너무 많아서 O(N) 으로 딱 제한을 두기가 힘든 모양이다.. 그럼에도 불구하고 파이썬 시간 제한이 9초대도 통과되는 건 너무 봐준 것 아닌가 싶기도.. 우선순위 큐 풀이는 최소힙에 (원소값, 원소 인덱스) 튜플을 저장하고, 범위가 늘어날 때마다 현재 보고 있는 원소를 우선순위 큐에 넣은 뒤, 최소힙에서 최소값을 본다.만약 본 값이 현재 최소값을 찾는 범위에 있는 값이라면 출력하고, 아니라면 최소힙에서 빼는 과정을 반복한다. 결과적으로는 N번의..

https://www.acmicpc.net/problem/1600 3차원 BFS 문제이다.dist[i][j][k] 를 (i, j) 위치에 있을 때 현재 남은 말 이동 횟수가 k 인 경우 그때까지 최소 이동거리라고 정의한 뒤, 일반 이동을 하는 경우dist[next_i][next_j][now_k] = min(dist[next_i][next_j][now_k], dist[now_i][now_j][now_k] + 1) 말로 이동하는 경우 k 를 소모하므로dist[next_i][next_j][now_k-1] = min(dist[next_i][next_j][now_k-1], dist[now_i][now_j][now_k] + 1) 이렇게 식을 세운뒤, dist 배열은 초기값을 INF 값 (파이썬은 보통 9876543..

https://lynlab.co.kr/blog/52 AWS 라이브러리의 SignatureDoesNotMatch 해결 방법 | LYnLabAWS 클라이언트를 이용할 때 발생한 SignatureDoesNotMatch 에러의 원인과 해결 방법. 💡 이 글은 작성된지 1년 이상 지났습니다. 정보글의 경우 최신 내용이 아닐 수 있음에 유의해주세요.lynlab.co.kr 스프링 어플리케이션에서 이미지 업로드 코드를 작성 후, 포스트맨에서 테스트할 때 발생했던 이슈500 에러가 나오면서 서버 로그를 보니 글 제목과 같은 에러가 발생했다. 같은 백엔드 팀원은 잘 된다는데, 왜 나만 안될까 하면서 윈도우 억까 이슈이길 바라며 EC2에 배포했으나 우분투 서버에서도 여전히 실패..이것 저것 찾아보고 시도했지만 결국은 위 ..

https://www.acmicpc.net/problem/11780 학교 알고리즘 분석 전공 수업시간에 배웠던 내용을 그대로 이용하면 쉽게 풀 수 있는 문제이다.플로이드 알고리즘은 dp 를 이용하는 방법으로, node 개수가 많지 않을 때 사용할 수 있는 알고리즘이다.시간복잡도는 node 개수가 n개 일 때, O(n³) 의 시간복잡도를 갖는다. 두 노드 a, b 사이의 최단거리 a, b 를 dist[a][b] 라고 할 때,  dist[a][b] = min( for k in range 1 .. n, dist[a][k] + dist[k][b] ) 로 정의할 수 있다. 글로 정리하면, 두 노드 사이의 최단 거리는 그 노드 사이를 k 번 노드를 경유해서 갈 때 더 짧다면 그 값으로 갱신하는 과정을 거치면 된다...

https://www.acmicpc.net/problem/21606 모든 검은색 노드는 흰색 노드를 통과할 수 있고, 검은색 노드는 통과하지 못할 때,모든 이동 가능한 검은색 노드 사이 경로의 개수를 세는 문제이다. 이 문제는 그래프를 단순화시킨 뒤 순열과 트리의 특성을 이용해 개수를 세면 문제를 풀 수 있다. 그림과 같이 노드가 구성되어 있다고 해보자.우리가 구하려고 하는 것은 두 검은색 노드 사이의 경로가 존재하는지 파악하는 것이다.이 정보를 파악하는데 중요한 것은, 여러개의 인접한 흰색 노드는 우리가 구하려는 것을 찾는 과정에서 전혀 의미가 없다는 것이다.그러면 이 그래프를 다음과 같이 단순화할 수 있다.  흰색 노드의 번호는 더 이상 정답을 구하는데 있어 큰 의미가 없다. (코드로 구현할 때는 번..

https://www.acmicpc.net/problem/2618 질문게시판에서 힌트 하나를 얻고 푼 문제..처음에는 스티커 문제처럼 어떤 사건을 경찰차 1이 해결한 경우, 경찰차 2가 해결한 경우로 나누어서 테이블을 구성하고,dp[w][1] = 사건 w를 경찰차 1이 해결했을 때, 그때까지 두 경찰차의 최소 이동거리 합 =min( dp[w-1][1] + dist(w-1, w) , dp[w-1][2] + dist(w-1을 경찰차 2가 해결한 최적해에서의 경찰차 1의 위치, w) ) 로 두고 dp[w][1], dp[w][2] 로 이루어진 2차원 배열로 풀려고 했다. 이렇게 말로만 적어도 벌써부터 점화식이 복잡한데, 이 점화식은 안타깝게도 틀렸다.비교하고 있는 두 값이 '같은' 경우 어떤 값을 취할 지 정할..

https://www.acmicpc.net/problem/1450 문제 풀이 주어진 물건들을 가방 안에 담을 수 있는 모든 경우의 수를 출력하는 문제나이브하게 접근하면 물건이 최대 30개 있으므로, 2^30 조합을 모두 시도해보면 된다.하지만 이렇게 접근하면 최악의 경우 1,073,741,824 가지의 경우의 수가 나오기 때문에 시간초과가 발생한다.따라서 meet in the middle 테크닉을 이용하여 시간을 줄이는 것이 이 문제의 핵심이다. '중간에서 만나기' 라는 이름으로도 불리는 이 테크닉은, 사이즈가 큰 전체 대상을 처음부터 끝까지 직접 탐색하는 것보다,전체 영역을 반으로 나눈 뒤, 반씩 쪼개서 탐색한 결과를 조합하여 해답을 구하는 기법이다. 이 문제의 경우, 2^30의 조합을 모두 구하는 것..

https://www.acmicpc.net/problem/2179 가장 긴 prefix를 구하는 건 쉬운데, 입력된 순서상 앞선 조합을 골라내는 것이 까다로운 문제가장 긴 prefix를 구할 때는 단어를 정렬해서 한번 순회하면 O(n log n) 시간에 구할 수 있다. 이때 같은 길이의 prefix에 대해서 입력이 먼저된 단어를 출력해야 한다.그래서 단어를 저장할 때, 입력된 순번도 같이 저장했다. n = int(input())l = []for i in range(n): s = input().rstrip() l.append((s, i)) 단어를 정렬하고 순회하면서 prefix를 체크할 때는 별도 함수를 사용했다.이때 같은 prefix 를 갖는 단어들을 모두 저장하기위해 딕셔너리와 셋을 이용했다..

[ '돈의 시나리오 - 김종봉, 제갈현열' 을 읽고 생각을 정리한 글입니다. ] 이 책은 제목 그대로 자신만의 '돈의 시나리오'를 만들고 이를 기반으로 돈을 벌 수 있는 방향을 제시하는 책이다.그런데 돈과 관련된 내용보다 이 책에서 제일 기억에 남는 구문은 다음 구문이었다. 자신에게 온전히 시간을 쏟는 사람은 불행하지 않다.그 사람의 시간에 타인의 시선, 타인의 감정이 들어설 틈이 없기 때문이다....그리고 투자자에게 이 사실은 아주 중요하다.투자는 돈이 아닌 시간을 쏟는 행위이며투자자는 자신을 위해 시간을 쏟는 행위이다.나는 당신이 투자자가 되어야 한다고 주장할 참이지만많은 돈을 버는 사람이 되길 바라는 마음보다는스스로 만족하는 의미있는 삶을 살아갔으면 하는 마음이 더 크다.당신이 흔들리지 않고 자신의..