알고리즘

플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 '모든 정점간에 최단거리를 구하는 알고리즘' 입니다. 시간 복잡도는 O(n^3)이다. 두개의 정점과 정점을 거치는 중간점 총 3개를 모두 탐색해야 합니다. 핵심은 거쳐가는 정점을 기준으로 최단거리를 알아내는 것입니다 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단거리를 구하는 문제 입니다. 다익스트라 알고리즘 플로이드 워셜 알고리즘 한 정점에서 다른 모든 정점으로의 최단 거리 구하는 알고리즘 모든 정점에서 모든 정점으로의 최단거리 구하는 문제 코드 먼저 살펴보겠습니다 v, e = map(int, input().split()) INF = 10000000 dist = [INF * (v+1) for _ in range(v+1)] # 입력받은 간선들에 대한 정보로 거리정보 ..

전구와 스위치[백준 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()) ..

가장 긴 증가하는 부분 수열[백준 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) : ..

랜선 자르기[백준 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(..

스택 수열[백준 1874]

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net stack을 탈출하는 조건에서 고민했던 문제이다. 굳이 그럴필요는 없었지만..... 구현하기 나름인데 아직 문제를 꿰뚫는 황금 라인은 보이지 않는것 같다. 예전에 골프 만화를 읽었을때 어느정도 경지에 오르면 골프공이 홀에 빨려들어갈 황금 라인이 보인다더라. 알고리즘도 하다보면 그런 라인이 보이겠지???? 언제나 그렇..

프린터 큐[백준 1966]

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 우선순위가 껴있어서 우선순위 큐를 사용해야지 했다가 우여곡절을 겪은 문제다. 당연히 우선순위큐를 이용해서 풀수도 있겠지만 작성하고 있던 코드는 계속 산으로 가서 방법을 수정했다. 처음보면 테스트 케이스에서 3번 예제가 이해 안될법 한데 문제 잘 읽으면 이해 될거에요 아래는 정답 코드다. tc = int(input()) for _ in range(tc) : n, m = list(map(int, inpu..

숫자 문자열과 영단어[2021 KAKAO BLIND]

https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr 레벨 1짜리 문제다. 너무 어렵게 접근을 했었다. 다른 사람들의 답변을 보고 파이썬에 아직 익숙하지 않구나 하는걸 느꼈다. 내가 제출한 코드를 먼저 보자 def solution(s): answer = 0 hash_list = {"zero": 0, "one": 1, "two": 2, "three": 3, "four": 4, "five": 5, "six"..

치킨 튀기기[제로베이스]

철수는 개발자에서 은퇴하여 치킨집을 하게 되었다. 철수는 뛰어난 개발 실력으로 N대의 자동 튀김기를 만들어냈다. i번째 자동 튀김기는 치킨을 한번 튀기는 데에 fry[i] 만큼의 시간이 걸리며, 튀김이 한 번 끝나면 clean[i] 만큼의 시간동안 자동 세척을 한다. 철수가 C번 치킨을 튀겨내려고 할 때, 최소한 몇 시간 동안 자동 튀김기를 가동해야 하는지 계산하시오. 제약사항 * 0 < N

기둥과 보 설치[2020 KAKAO BlIND RECRUITMENT]

https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr 접근 방법 : * 나머지 연산을 생각했었다. 원형의 특성상 나머지 연산을 통해 방향에 상관없이 인덱스에 접근할 수 있을것 같았다. * 배열을 두개를 붙여야 겠다고 생각했다. 나머지 연산은 계산이 너무 복잡해 질것 같았다. 전체 크기만큼 붙인 인덱스를 뒤에 연이어 붙여주기만 하면 될것 같았다. 두번째 방법으로 코드를 짜보았다. 살펴보도록 하자! from itert..

나 잡아 봐라[2019 LINE 인턴채용]

연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다. 이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나는데 걸리는 최소 시간을 구하시오. 조건 코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다. 즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다. 브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다. 코니와 브라운의 위치 p는 조건 0