전체 글

전체 글

    [코딩테스트 cheatsheet] 다익스트라

    개념 한 지점에서 다른 모든 지점까지의 최단거리를 구하는 알고리즘 현재 노드에서 가장 가까운 노드를 계속 탐색하며 최단거리를 그리디하게 업데이트해나감 힙을 사용하지 않으면 다음 노드를 선택하는 과정에서 연결된 노드를 모두 살펴야 함으로 비효율적 주의 : 가중치가 음일 경우 불가능함 => 벨만 포드 알고리즘을 사용해야함 시간복잡도 : O(ElogV) E : 간선의 개수, V : 노드의 개수 (힙 사용시) 코드 import heapq # 입력값은 인접리스트 형식으로 graph = [[] for _ in range(n + 1)] # 거리테이블을 무한으로 초기화 INF = int(1e9) distance = [INF] * (n + 1) # (거리, 노드)로 힙에 추가 -> 가장 가까운 거리를 바로 알 수 있음 ..

    [코딩테스트 cheatsheet] 플로이드 워셜

    개념 자주 나오는 유형은 아니지만 간간이 나오기 때문에 꼭 알고 있어야 된다고 생각한다. 시간복잡도 : O(n^3) 언제 써야하는가? 모든 정점에서 모든 정점까지의 거리를 알고 싶을 때 쓴다. 시간복잡도가 O(n^3)으로 굉장히 느려 정점의 개수가 500이하일 경우에 고려해볼만 하다. 500 * 500 * 500 = 125,000,000 인데 500은 진짜 삐끗하면 시간초과가 날 가능성이 높다. 아예 플로이드 워셜을 의도로 하는 문제는 n이 100~200정도이다. 코드 # 처음은 graph를 큰 수로 초기화 INF = int(1e9) graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기자신에게 가는 경로가 0일 경우에만 for x in range(1, n + 1)..

    [baekjoon] 2278 - 그래프 복원

    문제 링크 : https://www.acmicpc.net/problem/2278 2278번: 그래프 복원 첫째 줄에 그래프를 복원할 수 있으면 1을, 없으면 0을 출력한다. 복원할 수 있을 때, 다음 m개의 줄에 각 간선을 a, b, c의 형태로 출력한다. 이는 정점 a, b를 연결하는 가중치 c인 간선이 있다는 의 www.acmicpc.net 시도한 사람, 푼 사람이 거의 없다.. 평소에 해설을 쉽게 보는 편인데 해설이 없어서 강제로 열심히 풀었다. 백준 문제풀이는 너무 많은 사람이 올려서 쓰지 않을 생각이었지만 혹시 궁금한 사람이 있을 수 있으니.. 문제유형 - 그래프 복원 비슷한 문제는 1507번 - 궁금한 민호(https://www.acmicpc.net/problem/1507)가 있다. 두 문제의..

    [코딩테스트 cheatsheet] 시작하기

    개발자로 취업하기 위한 관문 중 하나는 코딩테스트이다. 코딩테스트 문제는 사람이 내는 것이고, 무한히 참신한 문제를 낼 수 없기 때문에 시중에 나와있는 문제들과 비슷하거나 조금씩 바꾼 문제가 출제되기 마련이다. 결국 문제은행 방식과 유사하다고 생각한다. 그럼 시중에 나와있는 문제들을 모두 푼다면 되겠지만 그건 비효율적이고 시간적으로도 모자르다. 이런 문제은행 시험을 통과하는 법 중 가장 효율적인 것은 최대한 많은 문제의 답지를 계속 보면서 외워버리는 것이라고 생각한다. 마치 문제와 답을 데이터로 하는 머신러닝을 우리 뇌로 돌리는 것 같다고 생각한다. 모든 문제의 답을 보는 것 역시 비효율적이므로 적절한 문제를 골라서 풀어보고, 답을 보고 주의할 점이 뭔지, 어떤 유형인지를 알아가면 될 것이다. 그럼 적절..

    flutter 버전 업그레이드 후기(2.10.4 -> 3.3.4)

    이 글은 2022년 10월 7일에 첫 작성되었습니다. (https://github.com/shs395/shs395.github.io/blob/master/content/flutter/version-upgrade/index.md) 버전 업그레이드 자세한 사항을 보려면 Upgrading Flutter(공식문서) 버전 업그레이드 자체는 되게 간단했다. flutter upgrade 한줄이면 스테이블 버전으로 업그레이드 된다. Upgrading Flutter to 3.3.4 from 2.10.4 ... 너무 쉽네 하고 앱을 빌드해보았더니 역시 에러가 났다. 간단한 앱인데도 쉽게쉽게 안되는구나,, 하나씩 해결해보자 에러 해결법 deployment target 에러 The iOS Simulator deployment..