알고리즘

[dp] 모듈러 분배법칙

코딩테스트를 풀다보면 결과 값이 매우 큰 경우 값의 나머지를 구하라는 문제가 자주 출제된다. 단순히 결과 값에 모듈러 연산을 수행하면 이미 결과값이 너무 커져서 오버플로우가 발생하거나 연산에 시간이 오래 걸리는 경우바 발생한다. 따라서 이럴때 연산 과정 중간에 모듈러 연산을 적용해야 한다. 연산 과정중에 모듈러 연산을 적용하기 위해서는 모듈러 연산의 분배법칙에 대해 알아야한다. 각 피연산자에 모듈러 연산을 취하고 계산 결과에 다시한번 모듈러 연산을 취하면 된다. ( dp[i] + dp[j] ) % C = ( dp[i]%C + dp[j]%C ) %C와 같다. 모듈러 연산의 분배법칙은 덧셈+, 뺄셈-, 곱셈* 에만 적용이 가능하고 나머지 연산에 대해서는 분배법칙을 적용할 수 없다.

[python3] 백준 1939 풀이 ( 중량제한, MST, 유니온 파인드 )

문제를 읽어보면 생각보다 간단하다. 여러개의 섬으로 이루어진 나라가 존재한다. 그리고 2개의 공장이 각 섬에 하나씩 존재한다. 섬들은 서로 중량제한이 있는 다리로 이루어져있다. 따라서 중량제한을 넘지 않고 다리를 건너서 한공장에서 다른 공장으로 물품을 이송해야한다. 이때 공장A에서 공장B로 갈때 얼마나 많은 물품을 한번의 이동시 옮길 수 있는지 출력해야한다. 여기까지 읽고나면 그래프 문제라는 감이 온다. 그런데 A공장에서 B공장까지 가야하기 때문에 여러개의 경로가 존재한다.문제는 다리개수가 100,000개이기 때문에 완탐으로 푸는 미친짓을 해서는 안된다. 천천히 고민해보자 우선 다리를 건너는 비용은 문제가 되지 않는다. A->B로 가기만 하면되고 이때 건너는 다리의 중량한계의 최솟값이 가장 큰 경로를 찾..

[python3] 백준 1339 풀이 ( 단어 수학, 그리디 )

이 문제는 상당히 헤맸다. 결국 1시간내에 풀지 못해서 질문을 찾다보니 좋은 접근 방법이 있어서 그걸 토대로 푸니 금방 풀렸다. 길이가 최대 8인 문자열이 최대 10개가 주어진다. 각 알파벳은 숫자를 의미하는데 숫자를 대입하여 모든 문자열의 총합을 구하면 된다. 예를 들어 AB + A의 최대값은 98+9 = 117로 나타낼 수 있다. 그럼 간단한 규칙을 찾아낼 수 있다. 1. 가장 앞에 있는 문자열일수록 큰수를 대입해야한다. 2. 많이 나올수록 큰수를 대입해야한다. 그런데 이렇게 정리하면 삽질을 하게 된다. 한마디로 짧게 생각하면 스스로 함정에 빠지는 거다. 그냥 간단하게 AB -> A*10+B*1, B-> B*1 AB+B -> A*10 + B*2 가 된다. 따라서 이걸 그대로 해주면 어떤 값이 가장 크..

[python] 코테 대비 알고리즘 모듈 정리

정렬 arr = [(1,2),(2,3), (1,1)] arr.sort() # 일반적으로 처음인자부터 차례로 정렬 nlogn arr.sort(key=lambda x:x[1],x[0]) # 두번째 인자 우선순위로 정렬 arr.sort(key=lambda x:x[0], reverse=True) # 첫번째 인자 기준으로 반대로 정렬 곱집합, 조합, 순열 from itertools import product product([1,2,3],['a','b','c','d']) # 하나씩 선택하는 모든 케이스(곱집합)가 만들어진다. from itertools import combinations combinations(iterable, r=None) # 조합 구하기 from itertools import permutatio..

[python3] 프로그래머스 외벽 점검 ( 2020 KAKAO BLIND RECRUITMENT, level3, 완전탐색, 순열 )

일단 문제 설명에 앞서 너무 어려웠다. 어려워서 짜증이 치밀어 오르다가 여러 사람의 풀이를 참고해보고 스스로 풀기를 반복하여 겨우겨우 풀었다. 문제를 읽어보면 크게 별게 없다. 취약한 지점이 존재하고 최대한 적은 친구들을 사용하여 취약한 지점을 점검하고 오는 것이다. 이때 사용된 친구들 수의 최솟값을 구하면 된다. 그런데 문제는 어디에서 시작해야할지, 어떤 친구를 투입할지 여러가지 고민이 필요하다. 처음에는 그리디 냄새가 났다. 어떤 취약한 지점을 고르고 가장 이득이 큰 부분을 선택하는 방식으로 진행하려고 했지만 기준을 만드는게 어려웠고 어떻게 구현을 해야하나 고민되었다. 그런데 n은 200이하이고, weak배열은 15이하, dist배열도 8이하였다. 그렇다면 완전 탐색으로 모든 경우를 해볼수도 있겠다는..

[python3] 백준 4195 (친구 네트워크, 유니온 파인드)

문제는 아주 심플하다. 소셜네트워크를 구성할때 서로 친구가 될때마다 해당 네트워크에 몇명이 속하는지 알아내면 된다. 테스트 케이스의 범위는 주어지지 않았지만 F의 값이 100,000으로 주어졌다. 그럼 테스트 케이스 * 100,000으로 상당히 연산량이 클것으로 예상된다. 또한 DFS를 통해 구성된 네트워크의 노드 갯수를 센다고 가정한다면 100,000 * O(N) 정도의 시간 복잡도가 걸리는데 만약 N이 100,000이 된다면 너무 시간복잡도가 크다. 즉, 매번 탐색하는 방식으로는 구할 수가 없다. 그럼 A라는 친구가 어디 네트워크에 속하고, 네트워크의 크기는 어느정도인지 한번에 안다면 우리는 testcase*100,000의 연산만으로 정답을 구할 수 있다. 딱 냄새가 난다 네트워크에 속하고 머시기 어..

[python3] 백준 2470 풀이 ( 투포인터 )

문제의 목표는 두 용액을 선택하여 차이 값이 가장 적은 경우를 가지는 두 용액의 특성값을 출력해야한다. 입력으로 주어지는 N값은 100,000이다. 만약 모든 용액을 서로 비교한다고 가정한다면 100,000 * 100,000 경우의 수를 연산해야한다. 이러한 경우 연산 횟수가 너무 많아지기 때문에 완전 탐색으로 풀수가 없다. 따라서 다른 방법을 써야하는데 투포인터를 쓰는 방식을 생각해 볼 수 있다. 투 포인터는 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다. 따라서 보통은 i,j로 인덱스를 만들고 인덱스를 서로 1씩 증가 시켜가며 특정 합을 구할때도 많이 쓰인다. 이것과 비슷하게 이 문제를 처리할 수 있다. 다만 i,j를 서로 반대편에 놓고 값을 비교해가며 포인..

[python3] 프로그래머스 섬 연결하기 ( 그리디, MST, 크루스칼, 유니온 파인드)

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 처음에는 그래프 알고리즘을 고민했다. 다익스트라,플로이드를 떠올렸지만 이건 목적지가 존재하는 경우에 사용하는 알고리즘이라 사용불가능 했다. 그러다가 가중치를 기준으로 정렬하여 하나씩 포함하면 되지 않을까 했고 visited 배열을 만들어 노드를 체크해주었다. def solution(n, costs): answer = ..