문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,..
Union-Find의 개념 서로 중복되지 않는 부분 집합 (Disjoint Set)을 표현할 때 사용하는 자료구조 초기화 / 합치기 (Union) / 찾기 (Find) 세 가지 연산을 사용한다 최소 스패닝 트리를 구현하는 크루스칼 알고리즘에 사용되며, 사이클을 만들지 않고 모든 노드를 방문할 수 있다 Union-Find의 구현 초기화 : N 개의 원소가 각각의 집합에 포함되어 있도록 초기화한다 -> 각각을 유일한 원소로 가지는 집합 생성 Union (합치기) : 두 원소 a, b 가 각각 속한 두 집합을 하나로 합친다 -> 두 개의 집합을 하나로 연결하는 역할 Find (찾기) : 원소 a 가 주어질 때, 이 원소가 속한 집합을 루트노드를 반환한다 -> a가 어느 집합에 속해있는지 찾는 역할 //초기화 ..
[Algorithm] 프로그래머스 트리 트리오 중간값 - 트리의 지름
문제 코딩테스트 연습 - 트리 트리오 중간값 5 [[1,5],[2,5],[3,5],[4,5]] 2 programmers.co.kr 풀이 임의의 노드 1로부터 가장 먼 노드 A를 찾는다. A로부터 각 노드까지의 거리를 찾는다 이 때 가장 먼 거리의 노드가 여러개라면 A노드와 먼 노드 중 2개를 선택하면 되므로 가장 먼 거리 리턴 가장 먼 거리의 노드가 B 하나라면 다시 B 를 기준으로 탐색 B로부터 각 노드까지의 거리를 찾는다 이 때 역시 가장 먼 거리의 노드가 여러개라면 B노드와 먼 노드 중 2개를 선택하면 되므로 가장 먼 거리 리턴 가장 먼 거리의 노드가 A 하나라면 A와 B의 거리(트리의 지름)-1을 리턴 위와 같은 입력의 경우 2-1에서 리턴이 된다. 노드 1에서 가장 먼 노드는 3이고, 3은 1,..
문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다) 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다..
[Algorithm] 백준 5577 회전초밥 - 슬라이딩윈도우
문제 회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다. 새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다. 원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의..
문제 2019 카카오 인턴십 - 튜플 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 풀이 주어진 튜플에 많이 등장하는 순서대로 숫자 배열을 만들어 리턴해야한다 튜플에 중복이 허용되지 않기 때문에 map에 key값으로 튜플의 원소 값을 넣고 value로 빈도수를 계산해 정렬해서 사용했다 sortByValue()는 map의 value를 기준으로 내림차순으로 정렬하여 반환하는 함수이다 Map.Entry : key와 value로 하나의 쌍을 이루는 map entr..
문제 카카오 2018 공채 - n진수 게임 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0� programmers.co.kr 10진수를 2-16 사이의 모든 진법으로 변환하는 문제이다! 풀이 A라는 숫자를 n진법 수로 변환하려면❓ 1. 몫이 0이 될때까지 A를 n으로 나눈다 2. 나머지를 밑에서부터 읽는다 위의 방법을 함수로 만들면 되는데, 주의할 점은 10이 넘는 수는 대문자 알파벳으로 변환해야 한다 -> 아스키코드 사용하기 튜브의 순서인 수만 뽑아서 리턴하면 완성! public static String solution(i..
문제 프로그래머스 2019 카카오 공채 - 후보키 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 뭔가 간단해보이고 자료구조를 이용해 어떻게 해낼 수 있을 것 같았는데, '비트마스크'라는 새로운 풀이법을 적용해야 했다. 풀이 for문을 돌려 인덱스의 부분집합을 구해 해당 부분집합의 인덱스 조합이 후보키가 될 수 있는지를 검사한다. 1을 colSize만큼 왼쪽으로 쉬프트하게 되면 2^col..