알고리즘

[python3] 프로그래머스 추석트래픽 풀이 ( 그리디 )

이 문제는 접근은 바로 했는데 한 날짜를 계산하는 포인트에서 막혀서 상당히 버벅거리다 다른 풀이를 보고 빠르게 해소되었다. 그래서 다시는 잊지 않고자 이렇게 풀이를 쓴다. 문제를 요약하면 다음과 같다. 로그에 처리시간과 걸린시간이 주어진다. 그렇다면 1초간 얼마나 많은 트래픽을 처리할 수 있는지 확인하고자 한다. 로그는 날짜순으로 오름차순으로 제공된다. 위와 같은 그림을 보면 각 초마다 매번 확인을 하며 로그를 확인해야하는가 싶다. 그렇게 된다면 24시간을 초당 루프를 돌아야하고 더구나 각 로그가 속하는지도 확인을 해야한다. 다행인건 주어지는 로그가 오름차순으로 정렬되어 있다는 점이다. 이를 통해 문제 해결의 실마리를 찾을 수 있다. (각 구간에 속하기만 하면 된다. ) 따라서 로그1이 존재할때 로그 1..

[python3] 백준 1194 풀이 ( "달이 차오른다, 가자." , BFS )

이번 문제는 오랜만에 그래프이다. 우선 문제를 읽어보면 몇가지 포인트가 존재한다. 1. 이동 횟수의 최솟값을 구한다. => BFS로 푼다. 2. 키가 있어야 문을 열수 있다. => 키를 찾고 왔던길을 다시 갈 수 있다. => visited를 키에 따라 따로 관리해야 한다. => 그럼 키에 따른 visited를 관리해야한다. 따라서 3차원으로 visited를 관리해야 한다. * 이때 키는 bitmasking으로 관리해야 배열에 넣고 관리가 가능하다. 3차원으로 visited를 관리해야 하는 경우에는 [y][x][key]로 관리하여 key일때 y,x가 true 상태인지 false 상태인지 저장해준다. 사실 이러한 방식이 처음이라 이해가 어려웠다. 만약 key가 3이고(000000000011 => a,b키를 ..

[python3] 백준 1005 풀이 ( ACM Craft, 위상정렬, 다이나믹 프로그래밍, DP )

상당히 헤맸던 문제다. 갈피를 못 잡다가 문제의 알고리즘 분류를 힌트로 보고 방향성을 잡을 수 있었다. 그럼 문제를 보자 문제를 읽어보면 건물의 순서가 주어진다. 이때 목표하는 건물을 만들기까지 걸리는 최소 시간을 출력한다. 보면 건물의 순서가 그래프로 주어지기 때문에 사이클이 존재하지 않는다. 즉, DAG그래프처럼 보인다. 그럼 당연히 자연스럽게도 위상정렬이 떠오른다. 그럼 생각을 해본다. 위상정렬은 BFS처럼 동작한다. 큐에서 노드를 뽑고, 노드의 out degree접선을 제거하면서 진행한다. 그리고 만약 한 노드의 in degree접선이 0이라면 큐에 넣는다. 위상정렬의 원리는 아래의 글을 읽으면 된다. [python3] 백준 2252 풀이 ( 줄세우기, 위상정렬, DAG, 그래프 ) 위상정렬 어떤..

[python3] 백준 1238 풀이 ( 파티, 다익스트라 )

이번 문제는 참신했다. 물론 내가 생각도 못해서 참신하게 느껴진거 겠지만ㅋㅋ 우선 문제를 보자 문제를 읽어보면 여러 곳에서 학생들이 X마을로 모인다. 이후에 각자 집으로 돌아갈 때 가장 오래 걸리는 학생의 소요 시간을 출력한다. 간단히 생각해보면 파티에 참석하는 경우 마을이 N개 이기 때문에 N -> X로 가는 경우의 수가 나올것이다. 파티가 끝나고 집에 가는 경우는 X -> N으로 가는 경우의 수가 나온다. 그럼 단순하게 보면 단일 시작점 알고리즘이 적용되면 안 되는거 같다. 왜냐하면 출발할 때 N개의 마을에서 각자 출발하기 때문이다. 그래서 나도 플로이드-워샬을 적용하고 풀고자 했다. N=1000 이므로 N^3 = 1,000,000,000 = 10억, 21억 넘지 않아서 괜찮을 줄 알았다. (찾아보니..

[pypy3] 백준 12015 풀이 ( 가장 긴 증가하는 부분 수열 2 , LIS , 이분 탐색 )

이번에는 진짜 너무 어려웠다. 정답비율이 40%문제인데 다들 대단한거 같다. 물론 문제 자체가 기본적인 LIS유형중 한개로 쉽게 풀리지만 알지 못하는 상태에서 생각해 내기 굉장히 어려운거 같다. 따라서 나도 LIS를 공부하고 기본 코드로 풀이를 할 수 있었다. 우선 문제를 보자 문제는 간단하다. 수열이 주어지고 여기서 "최장 증가 부분 수열"을 구하면 된다. 내가 풀이를 쓰는 것보다 더 좋은 풀이가 있어서 고수님의 글을 참고하면 좋을것 같다. https://chanhuiseok.github.io/posts/algo-49/ 알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘 컴퓨터/IT/알고리즘 정리 블로그 chanhuiseok.github.io 결론적으로 LIS의 풀이 방법은 2가지가 있다. 1. DP를..

#5 알고리즘 공부 8/24 리뷰

올해부터 알고리즘 공부의 필요성을 느끼고 나름 열심히 공부하고 있습니다. AC RATING을 보니 살짝 정체기도 있었지만 꾸준히 상승하고는 있네요. 2월~3월까지 알고리즘 공부를 시작하고 학기 중에는 거의 하지 못했네요. 다행히 방학에는 알고리즘 스터디와 sds알고리즘 특강 덕분에 꾸준히 조금씩 성장하고 있는 듯이 보입니다. 현재까지는 213문제를 풀었는데 어서 빨리 공채 코테는 다 뚫어버리는 실력을 가지고 싶네요. 다시 화이팅 입니다!

[python3] 백준 2110 풀이 ( 공유기 설치, 이분탐색 )

저번에 푼 프로그래머스와 비슷한 문제였다. 그런데 상당히 헤매고 풀었기 때문에 다시 한번 풀이를 정리해 본다. [python3] 프로그래머스 징검다리 풀이 ( 이분탐색 ) 왜 이분 탐색문제인지 이해를 할수가 없어서 상당히 헤맸다. 결국 풀이를 봤다. 우선 문제를 읽어보면, 징검다리를 만들 때 n만큼 돌을 제거하고 최솟값을 찾는다. 이때 최솟값을 최대로 만드는 guccin.tistory.com 우선 문제를 읽어보자 문제를 읽어보면 입력으로 x가 0~1,000,000,000의 범위를 가진다. 딱 보자마자 완전 탐색으로는 절대 돌수가 없다. 따라서 이분탐색의 냄새가 난다. x의 좌표에서 이분탐색의 느낌이 나는데, 우리는 출력으로 두 공유기 사이의 최대 거리를 출력해야한다. 공유기 사이의 최대거리를 만족하기 위..

[python3] 프로그래머스 징검다리 풀이 ( 이분탐색 )

왜 이분 탐색문제인지 이해를 할수가 없어서 상당히 헤맸다. 결국 풀이를 봤다. 우선 문제를 읽어보면, 징검다리를 만들 때 n만큼 돌을 제거하고 최솟값을 찾는다. 이때 최솟값을 최대로 만드는 경우를 구하면 된다. 제한사항을 보면 distance가 1~1,000,000,000이다. 아무래도 선형탐색은 못할 만큼 값이 크다. 따라서 여기서 이분탐색의 냄새를 살짝 맡아본다. 처음에 나는 각 돌마다 거리를 구하고 작은 값부터 제거하면 되지 않나?하고 생각했다. 그러나 문제는 돌이 제거되면 각 돌의 거리를 다시 최신화 해주어야 한다. 그럼 돌을 제거 할 때마다 sort를 하게 되고 n만큼 sort를 해야되는 상황이 발생한다. 그럼 생각을 바꿔보자 만약 최솟값을 기준으로 현재 바위가 만족하는지 확인한다고 가정한다. ..