본문 바로가기

자료구조 & 알고리즘 & cs

 (88)
[TIL] 최소 신장 트리(MST) 1 - 크루스칼(kruskal) 알고리즘 최소 신장 트리(MST : Minimum Spanning Tree) 가능한 신장 트리 중에서 간선의 가중치 합이 최소인 신장 트리 최소 신장 트리를 찾을 수 있는 알고리즘은 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 있음. 두 알고리즘 모두 탐욕 알고리즘을 기반으로 한다. 신장 트리란? - 그래프의 모든 노드를 포함하면서 모든 노드가 서로 연결 되어 있고 트리의 속성을 만족시키는 트리 (사이클 x) 크루스칼 알고리즘(Kruskal's algorithm) 모든 정점을 독립적인 집합으로 만든다. 모든 간선을 가중치를 기준으로 정렬하고, 가중치가 가장 작은 간선부터 양 끝의 두 정점을 비교한다. 두 정점의 최상위 정점(루트 노드)을 확인하고 서로 다르다면 연결한다. (같을 경우 사이클이 생기므로 x) Un..
[python] 13549 - 숨바꼭질 3 13549번: 숨바꼭질 3 (acmicpc.net) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이번 문제는 bfs와 다익스트라 두 가지 방법으로 풀이할 수 있다. 전에 bfs 문제를 풀 때 다루었던 문제랑 똑같은게 아닌가? 했는데 이 문제에서는 가중치를 고려해야한다. 그래서 전에 풀었던 bfs 방식에서 가중치를 고려하여 살짝 변형하여 풀고 최근에 학습한 다익스트라로도 코드를 짜 보았다. [BFS] import sys from collections import deque #..
[python/java] 프로그래머스 Lv2. - 최솟값 만들기 코딩테스트 연습 - 최솟값 만들기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 파이썬으로는 배열의 정렬을 사용하여 매우 간단하게 풀었다. [python] def solution(A,B): answer = 0 A.sort() B.sort(reverse=True) for i in range(len(A)): answer += A[i]*B[i] return answer 그런데 자바를 사용할 경우 이슈가 발생했다. 기존에 알고있던 Arrays.sort()와 Arrays.sort(arr, Collection..
[python] 프로그래머스 Lv2. - 줄 서는 방법 코딩테스트 연습 - 줄 서는 방법 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 이해하는 것이 꽤나 어려웠다. 팩토리얼까지는 접근을 했는데 그 다음 식으로 구현하는 것에 애를 먹었다. 문제와 같이 n=3, k=5일 경우 모든 경우의 수를 나열해보면 다음과 같다. [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] 따라서 결과는 5번째 방법인 [3,1,2]가 리턴되어야 한다. 줄을 서는 모든 경우의 수는 n을 일렬로 나열하는 경우의 수 n!가지이다. 예를 들어..
[java/python] 프로그래머스 Lv2. - 숫자의 표현 코딩테스트 연습 - 숫자의 표현 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도가 높지 않은 문제였다. [python] def solution(n): answer=1 for i in range(1, n+1): sum=i for j in range(i, n-1): sum+= j+1 if sum > n: break if sum == n: answer+=1 break return answer 처음에 sum의 크기를 고려하지 않았다가 효율성 테스트에서 시간초과가 발생했다. 계산 횟수를 줄이기 위해 s..
[java/python] 프로그래머스 Lv.2 - 땅따먹기 코딩테스트 연습 - 땅따먹기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dp를 사용하여 해결하였다. [python] def solution(land): if len(land) == 1: return max(land) else: for i in range(1,len(land)): for j in range(4): if j == 0: land[i][j] += max(land[i-1][1], land[i-1][2], land[i-1][3]) elif j ==1: land[i][j] += max(lan..
[python] 10986 - 나머지 합 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 부분합 문제이다. 이전까지의 부분합 개념을 이용하여 풀려고 했는데 계속 런타임 에러가 났다. 도저히 방법을 찾을 수가 없어 다른 풀이를 참고하여 해결하였다. 참고 사이트 : [파이썬] 백준 10986번 나머지 합 (tistory.com) 수학적 지식이 필요했는데, 간단하게 말하면 부분합을 구한 후 m으로 나누었을 때의 나머지가 동일한 구간을 찾으면 된다. 쉽게 이해하..
[TIL] knapsack 알고리즘 (배낭 문제) knapsack problem - 배낭 문제 : 배낭에 담을 수 있는 무게의 최댓값은 정해져 있고 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 넣을 짐을 고르는 방법을 찾는 문제 냅색 알고리즘은 물건 분할 유무에 따라 분할 가능한 문제와 0-1 문제로 나뉜다. 여기서 다룰 문제는 0-1 냅색 알고리즘으로 백준 12865 문제를 풀다가 접하게 되었다. 12865번: 평범한 배낭 (acmicpc.net) 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,0..
728x90

티스토리툴바