Hello Ocean! 🌼

문제 설명 카카오에 신입 개발자로 입사한콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다. 용어의 정의 '('와')'로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를균형잡힌 괄호 문자열이라고 부릅니다. 그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우..

문제 설명 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 ..

문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상ICN공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. 입출력 예 tickets return [[ICN,JFK],..

최단 경로 알고리즘 (Dijkstra) 최단 경로(shortest path)문제 란? 임의의 두 노드를 연결하는 경로 중, 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다. 여기서 가중치는 비용, 거리, 시간 등이다. 예를들어 위와 같은 그래프에서 A -> B로 가는 경로를 생각해보자. A->B로 갈 수 있는 경로는 매우 많다. 하지만 그 중에서 최단 경로는 노드 E를 거쳐서 가는 경로이다. 최단 경로를 구하는 문제는 여러가지가 있다. 하나의 노드 -> 다른 하나의 노드 최단 경로 찾기 하나의 노드 -> 다른 모든 노드 최단 경로 찾기 하나의 목적지로 가는 모든 최단 경로 찾기 모든 최단 경로 찾기 Dijkstra의 최단 경로 알고리즘 개념 Dijkstra의 최단 경로 알고리즘은, 위의 최단 경로..

Spanning Tree(신장 트리) ? 개념 그래프 내의 모든 노드을 포함하는 트리 모든 노드를 사이클 없이 연결하는 간선들을 모아놓은 트리 그래프의 최소 연결 부분 그래프 최소 연결 = 최소의 간선 n개의 노드를 n-1개의 간선으로 연결 특징 DFS, BFS를 이용해서 찾을 수 있다. 탐색 도중에 이용된 간선 모으기 하나의 그래프 -> 여러개의 spanning tree 사이클 X MST(Minimum Spanning Tree) ? 개념 Spanning Tree중에 간선의 가중치 합이 최소인 트리 단순히 가장 가중치가 작은 간선을 이용한다고 해서 최소 비용이 얻어지는 것은 아님 특징 간선의 가중치의 합이 최소 n개의 노드을 가지는 그래프, n-1개의 간선만 이용 사이클 X 구현 방법 1. Kruskal..

문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연수입니다. ..