새로운 알고리즘이네요.그리디(Greedy) 알고리즘의 일종인 크루스칼(Kruskal) 알고리즘 입니다. 크루스칼 알고리즘 목적: 최소 신장 트리 구하기 주요 기능: Union - Find를 통한 최소 비용외의 간선 삭제 이런 노드들이 있다고 가정하면, 간선 [3 - 4]를 제외한 경로가 비용이 최소가 되는 경로입니다. 이런 경로를 구하는 방법은 다음과 같습니다. 1. 비용의 순서대로 정렬. 2. 해당 노드의 부모를 갱신. 3. 비용 계산으로 진행됩니다. union - find 연산은 node의 부모가 다를때 각 노드의 부모를 갱신해주는 알고리즘입니다. 부모가 같다면 해당 간선으로 사이클이 발생할 수 있기 때문에 부모가 같은 경우는 제외하게 됩니다. 종종 union 연산 시 갱신하는 parent가 최상단의..

옛날 문제를 자꾸 풀게 되는데,뭔가 창의력을 요구한달까.. 요즘은 유형이 어느정도 나뉘잖아요. 오히려 접근이 편한데 옛날 문제는 약간 창의력을 보네요.이 문제는 엣지 케이스 처리만 잘해주면 크게 어려운 건 없습니다. (17, 18번이 문제이신 분들은 비겼을 때만 처리해주면 되거든요...!) 문제 요약 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다. 각 사원은 딱 한 번씩 경기를 합니다. 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀..

프로그래머스 UI가 개편되면서 꼭 leetcode 처럼 바뀌었네요.저번 정렬 기준으로 1페이지를 다 풀었었는디.. 이제 다시 채워야죠! 자 그럼 레벨 3 - 1번 문제인 최고의 집합을 같이 보시죠! 문제 요약 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합 예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다. { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } 그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다. 집합의 원소의 개수..

보통 프로그래머스에서 문제 제목이 있으면 "JS PROBLEM_TITLE" 이런식으로 검색하면 쉽게 다른 블로그의 풀이를 볼 수 있는데, 이 문제는 제목이 너무.. 알고리즘에 잡히기 힘들겠더라구요ㅋㅋㅋㅋ 아무튼 가봅시다! 어제에 이은 또 dp문제네요. 문제 요약 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다. 알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다. 문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다. 예를 들어, 당신의 현재..

레벨 3도 앞장을 다 했네요.앞장에서는 우선순위 큐(힙)나 덱과 같은 자료구조나 최소거리 문제, 완전 탐색 같은 주제였는데요.다시 dp를 다뤄볼 때가 온 것 같습니다. 이게 가장 어려운 것 같아요. 같이 한 번 볼까요? 문제 요약 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다. 제한사항 문자열 s의 길이 : 2,500 이하의 자연수 문자열 s는 알파벳 소문자로만 구성 테스트케이스 s answer "abcdcba" 7 "ab..

말이 되나요.. 9000ms 미리 보여드립니다~ 아마 제가 이상하게 푼 거 같긴한데.. 더 이상 걸러낼 자신 없습니다. 일단 푼 거나 공유해드리겠습니다. 네.. 걸러냈네요. 큐가 아니라 우선순위 큐를 이용한 다익스트라 알고리즘으로 접근 시 훨씬,, 훠어어얼씬 빠릅니다. 문제 요약 건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다. 제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다. 설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다. 경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1)..