본문 바로가기

전체 글428

플로이드 워셜 알고리즘 플로이드 워셜 알고리즘은 '모든 정점간에 최단거리를 구하는 알고리즘' 입니다. 시간 복잡도는 O(n^3)이다. 두개의 정점과 정점을 거치는 중간점 총 3개를 모두 탐색해야 합니다. 핵심은 거쳐가는 정점을 기준으로 최단거리를 알아내는 것입니다 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단거리를 구하는 문제 입니다. 다익스트라 알고리즘 플로이드 워셜 알고리즘 한 정점에서 다른 모든 정점으로의 최단 거리 구하는 알고리즘 모든 정점에서 모든 정점으로의 최단거리 구하는 문제 코드 먼저 살펴보겠습니다 v, e = map(int, input().split()) INF = 10000000 dist = [INF * (v+1) for _ in range(v+1)] # 입력받은 간선들에 대한 정보로 거리정보 .. 2021. 11. 28.
가다듬기(일상을 깨지 않고 인생을 바꾸는 법) - 지금, 이곳에 집중할 것 눈앞의 일에 집중하자. '나'라는 사람은 눈앞에 펼쳐지는 풍경과 이어진다. 일할 때는 일에, 요리할 땐 요리에, 청소를 한다면 청소에, 누군가를 만난다면 만남의 시간에, 온전히 의식을 집중하자 눈앞에 펼쳐진 풍경은 지금 이곳밖에 없다. 무엇이 보이는가, 어떻게 느끼는가. 그것이 지금 나와 이어지는 세계다. - 마음껏 흔들리자, 그 다음이 관건이다 마음이 흔들리면 문득 나의 역량이 부족한 탓이라는 생각이 들 때가 있다. 내가 단단하고 빈틈없는 사람이라면 갈피를 잡지 못하고 이리저리 흔들리지 않을 거라고 여기는 것이다. 그러나 흔들리지 않는다고 마냥 좋을까? 그렇지는 않을 것이다. 흔들리는 것은 섬세하다는 방증이기도 하다. 섬세하면 사소한 일에도 깨달음을 얻지만, 동시에 마음이 .. 2021. 11. 28.
전구와 스위치[백준 2138] - python https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 1년 전에 풀때 못풀었던 문제다. 이번에 풀게되었는데 이번에도 실패다. (고마워요 다른 블로거 포스팅들) 다음엔 꼭 성공하리... 다음에 실패하지 않기 위해 이번에는 생각을 정리해서 글을 남겨둘 거다. 다음에 풀 나에게 힌트가 되기를 바라며... 정답 코드 먼저!!! n = input() first = list(input()) target = list(input()) .. 2021. 11. 21.
list Filter python에서 Filter javascript에서 filter를 즐겨 쓰다보니 python에서도 filter를 계속 찾게된다. 아직 익숙치 않아 매번 블로그 뒤지고 있어서 이 참에 한번 깔끔하게 정리해보자 실제 활용 예시 먼저!!! import re s = "one2three4five6" print(list(re.split('(\d)', s))) # ['one', '2', 'three', '4', 'five', '6', ''] print(list(filter(lambda x: x != '', list(re.split('(\d)', s))))) # ['one', '2', 'three', '4', 'five', '6'] 최근 정규 표현식 라이브러리를 사용하려 하고 있다. re.split을 하면 split .. 2021. 11. 20.
가장 긴 증가하는 부분 수열[백준 11053] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 스터디중 25분내에 풀지 못하고 곤혹에 빠졌던 문제이다. dp를 이용하여야 하는 문제이다. 정답 코드 먼저!!!! n = int(input()) l = list(map(int, input().split())) dp = [1] * (n + 1) for i in range(1, n) : for j in range(i) : .. 2021. 11. 20.
랜선 자르기[백준 1654] https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 우선 문제를 보고 바로 이분 탐색의 접근 방법이 떠올랐다는 것은 스스로에게 칭찬해주고 싶다. 최근에 이분 탐색 풀이에 크게 감명받고 한번쯤 이분 탐색을 꼭 곁들여 보는것 같다(혹시 이 접근은 아닐까 하는식??) 각설하고 애를 먹었던 부분은 길이가 최대로 긴 부분까지 접근해야 하는데 이부분을 어떻게 할것이냐?? 정답 코드 먼저!! k, n = map(int, input(.. 2021. 11. 20.

티스토리툴바