빠르고 꾸준하게

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 1916(파이썬) - 최소비용구하기

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 이 문제는 다익스트라의 기본 중 기본문제이다. 먼저 각 인덱스 노드와 연결되어 있는 노드와 경로 값을 노드 번호를 인덱스로 가지고 있는 data리스트에 넣어준다. dijkstra 함수에서는 heap구조를 이용해서 start 노드를 시작으로 놓고 구현했다. q라는 리스트가 빌 때까지 while문을 돌려주면서 현재 비교하려는 노드와 그 노드가 가진 경로 값을 꺼내서 ..

자료구조 & 알고리즘/프로그래머스(programmers)

[programmers] 크레인인형뽑기게임 (2019 카카오 개발자 겨울 인턴십)

https://programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 내가 처음에 알고리즘 풀이를 시작했을 때, 프로그래머스에 있는 카카오기출문제를 풀어봐야지라고 마음을 먹고, '레벨 1은 어떤 문제일까?' 하고 봤었다. 근데, 문제부터 너무 어렵게 생겼었다. 문제를 읽고 어떻게 풀어야하는지도 모르겠고,,, 멘붕이 왔었는데 꾸준히 풀다보니 성장한 건지... 보자마자 풀어재꼈다. 정말 간단하다. 먼저 for문으로 주어진 moves를 하나씩 확인하면서 그 세로..

자료구조 & 알고리즘/프로그래머스(programmers)

[programmers] 튜플 (2019 카카오 개발자 겨울 인턴십)

https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 이 문제는 튜플 관련된 문제인 줄 알았지만 문자열을 잘 다루는지를 묻는 문제였다. 파이썬에서 문자열에 관련된 문제는 split을 먼저 떠올리는 게 좋다. split을 사용하면 분리해서 리스트에 담아준다. 처음 주어지는 s 라는 문자열을 앞뒤 {{ , }} 부분은 신경 쓰지 않아도 되기 때문에 s [2:-2]로 ..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 1753(파이썬) - 최단경로

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 이 문제는 제목 그대로 최단경로, 즉 알고리즘 분류 중 다익스트라로 풀어내는 문제이다. 최단경로 문제는 다익스트라와 플로이드 워셜 정도가 있지만 둘이 차이는 아래와 같다. 다익스트라 : 시작점으로 부터 나머지 정점까지 최단거리를 구할 때 플로이드 워셜 : 각 정점간 최단경로를 구할 때 위를 고려해서 문제를 풀어주면 된다. 가장 기본적인 다익스트라 함수를 구현해서 문제를 ..