자료구조

자바(Java) 알고리즘 문제풀이 최소 스패닝 트리[백준 / 크루스칼(그리디)]

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 코드 이 문제는 최소 신장트리를 구하는 문제인데, 크루스칼 알고리즘을 사용하면 해결되는 문제이다. 크루스칼 알고리즘이란, 그래프 내 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용된다. 쉽게 말해 그래프를 회로가 없는 트리로 만들면 되는 것. 그래프 내의 모든 정점들 중, 가장 적은 비용을 가진 간선부터 연결을 시작하고 연결하기 전에 해당 ..

자바(Java) 알고리즘 문제풀이 같은 숫자는 싫어 [프로그래머스 / Stack]

문제 설명 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면, arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다. arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다. 배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요. 제한사항 배열 arr의 크기 : 1,000,000 이하의 자연수 배열 arr의 원소의 크기 : 0보다 크거나 ..

자바(Java) 알고리즘 문제풀이 공주 구하기 [인프런 / Queue]

강의의 문제를 가져왔기 때문에 밝힙니다 ! 임의로 추가, 수정, 삭제한 내용들이 있으니 정확한 이해를 위해서는 강의를 구매하시는 것을 추천드립니다 😅 출처 : 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 (인프런 강의) 1) 공주 구하기 수건 돌리기와 비슷한? 문제였다. N 명의 사람 중 K 라는 특정 수를 외치면 그 사람은 빠지고 한 사람이 남을 때 까지 이어서 진행, 그 사람을 구해내면 되는 간단한 문제였다. 예를 들어 N = 4 / K = 2 라면, [1, 2, 3, 4] -> [1, 3, 4] -> [1, 3] -> [1] 로 진행되어 1번 사람이 마지막에 남게된다. 헷갈렸던 부분은 특정 수를 외친 사람이 빠지고 다시 1부터 세야하는 부분 ? 이 조금 헷갈렸지만, Queue 를 사용해 특..

자바(Java) 알고리즘 문제풀이 쇠막대기 [인프런 / Stack]

강의의 문제를 가져왔기 때문에 밝힙니다 ! 임의로 추가, 수정, 삭제한 내용들이 있으니 정확한 이해를 위해서는 강의를 구매하시는 것을 추천드립니다 😅 출처 : 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 (인프런 강의) 1) 쇠막대기 문제를 처음 봤을 땐 길기도 하고 복잡하게 보여서 꽤나 긴장했었는데, 차근차근 그림을 그려가며 보니 Stack 을 사용한다면 꽤나 간단히 풀 수 있는 문제였다. 열린 괄호를 계속해서 넣어주다가 닫힌 괄호가 등장했을 때 레이저가 만들어지는지 막대기가 나오는지 구별하면 된다. 처음 시도에서는 stack.peek() 을 활용해 풀이했는데 틀려서 디버깅 후 겨우 원인을 찾을 수 있었는데 ,, 1-1) peek() 을 활용한 첫번째 풀이 (오답) 닫힌 괄호가 등장했을 때, ..

자바(Java) 알고리즘 문제풀이 올바른 괄호,괄호문자제거 [인프런 / Stack]

강의의 문제를 가져왔기 때문에 밝힙니다 ! 임의로 추가, 수정, 삭제한 내용들이 있으니 정확한 이해를 위해서는 강의를 구매하시는 것을 추천드립니다 😅 출처 : 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 (인프런 강의) 이번에도 따로 강의를 보지 않고 문제만 풀었음 ㅎ_ㅎ 정답이긴 하지만 강의 코드와 다를 수 있습니다 ! 1) 올바른 괄호 Stack 자료구조를 활용하면 빠르게 풀어낼 수 있다. 예전에는 Input 받은 문자열을 split() 메서드를 통해 배열로 만들었는데, toCharArray() 메서드를 활용하면 효율성 테스트 또한 통과할 수 있다고는 하는데 .. 그런 제약 없으면 아무 방법이나 사용해도 무방할 듯 하다. answer 를 YES 값으로 셋팅하고, 분기문을 따라 내려가면서 NO..