백준 13398 (연속합 2) 문제 링크 문제 링크 : https://www.acmicpc.net/problem/13398 문제 접근 문제 풀기 전 풀어봅시다! 위 문제의 해설을 보려면 클릭하세요. 결론부터 말하자면, 인터넷에 떠도는 풀이랑 저의 풀이는 조금 다릅니다. 연속합 문제입니다. 근데 하나의 원소를 제거한 최댓값도 고려를 해야 합니...

백준 1912 (연속합) 문제 링크 문제 링크 : https://www.acmicpc.net/problem/1912 문제 접근 연속합 문제를 들고 왔습니다. 너무 대중적인 문제입니다. n개의 원소를 가진 수열에서, 연속된 몇 개의 수의 합의 최댓값을 구하는 문제입니다. 현재 우리가 모르는, 미지수로 두어야 할 특징은 1) 어디서 시작해서 2)...

백준 2293 (동전 1) 문제 링크 문제 링크 : https://www.acmicpc.net/problem/2293 문제 접근 반갑습니다. 오늘도 동적 계획법 문제를 들고 왔습니다. n가지 종류의 동전이 있습니다. 동전의 수는 제한이 없을 때, 적절히 사용해서 k원을 만드는 문제입니다. 아시는 분은 아시겠지만, 이 문제는 동적 계획법 국룰 ...

백준 백준 2023 (신기한 소수) 문제 링크 문제 링크 : https://www.acmicpc.net/problem/2023 문제 접근 반갑습니다. 오늘도 재밌는 문제를 들고 왔습니다. 문제를 간략하게 설명해보겠습니다. 수빈이는 소수를 좋아한다고 합니다. N자리 자연수 중, 왼쪽에서부터 1,2,3,..N자리 모두 소수인 신비한 소수를 구하는...

백준 2293 (동전 1) 문제 링크 문제 링크 : https://www.acmicpc.net/problem/2293 문제 접근 반갑습니다. 오늘도 동적 계획법 문제를 들고 왔습니다. 덧셈이 교환법칙이 성립하기에, 분리해서 사고를 해야 한다는 사실은 알겠음.

백준 1069 (집으로) 문제 링크 문제 링크 : https://www.acmicpc.net/problem/1069 문제 접근 오랜만에 재미있는 문제를 들고왔습니다. 고등학교 3학년 때, 기하와 벡터 과목이 생각나는 문제입니다. 간단하게 요약하자면, 2차원 평면상에, 하나의 점이 (x,y)로 주어졌습니다. 1. 원점까지 1초당 1의 거리를 ...

다익스트라 알고리즘 하나의 정점 기준으로 모든 정점까지의 최단 경로를 아는 알고리즘입니다. 음수 가중치가 존재하지 않아야 합니다. 개선된 다익스트라 알고리즘을 사용해서 O(n*logn)의 시간 복잡도로 해결할 수 있습니다. 이를 사용하기 위해 우선순위 큐 자료구조를 사용합니다. 왜? continue 후 갱신 안하나요? 이미 if문에서 갱신을 했습...

소스 코드 import sys from collections import deque n,m,v=map(int,sys.stdin.readline().split()) graph=[[] for _ in range(n+1)] for _ in range(m) : v1,v2=map(int,sys.stdin.readline().split()) g...

들어가기에 앞서 graph(1) - 그래프와 트리 이번 글에서는, 컴퓨터를 통해 그래프를 구현하는 방법과, 탐험하는 방법에 대해 알아보도록 하겠습니다. 그래프 구현 그래프와 트리에 대해 이해를 했습니다. 이젠 어떻게 구현하는지에 대해 python을 사용해서 이야기를 해보려고 합니다. 대부분의 언어가, 표준 라이브러리로 그래프를 지원하지 않습니...

들어가기에 앞서 제가 포스팅을 할 때, 이야기 형식으로 기술을 합니다. 혹자는 내용만 정리하면 되는데 너무 글머리가 길다고 질문할 수 있습니다. 하지만 이는, 혹시라도 존재할 지 모르는 누군가가 제가 쓴 글을 처음부터 읽는다면 최대한 흡입력이 있도록 하기 위해서입니다. 아무튼 반갑습니다. 첫 포스팅입니다. 첫 주제를 graph 이론으로 선정하였습니...