본문 바로가기

Developer/Algorithm

(9)
[코딩테스트] 자바스크립트에서 파이썬으로 바꾸기 이번 하반기를 준비하면서 코테의 중요성을 크게 느낀다. 그 동안의 주언어를 자바스크립트를 사용하다가 3주 전부터 급하게 파이썬으로 바꿨다. 자바스크립트를 사용하지않는 기업도 있었고 자바스크립트만 사용하는 기업도 있었지만 가장 큰 이유는 제공하는 라이브러리가 파이썬이 많기 때문에 코테 문제를 풀 때 수월하다는 것이다. 예를 들어 순열, 조합을 계산할 때 자바스크립트는 재귀함수로 함수를 만들어야하지만 파이썬은 라이브러리를 통해 한 줄로 작성가능하다. 코테처럼 시간을 중요시하고 경우의 수를 많이 생각하는 부분에서 당연히 파이썬이 유리할 수 밖에 없다는 나의 판단이다(뇌피셜) 아무튼 학부 때 주언어가 파이썬이었어서 그래도 바꾸는데에 큰 무리는 없었지만 헷갈리기는 했다. 그래서 기본 파이썬 문법들 중 꼭 필요한 ..
[프로그래머스] 배상 비용 최소화 문제풀이 / Javascript https://programmers.co.kr/learn/courses/13213/lessons/91086 OO 조선소에서는 태풍으로 인한 작업지연으로 수주한 선박들을 기한 내에 완성하지 못할 것이 예상됩니다. 기한 내에 완성하지 못하면 손해 배상을 해야 하므로 남은 일의 작업량을 숫자로 매기고 배상비용을 최소화하는 방법을 찾으려고 합니다. 배상 비용은 각 선박의 완성까지 남은 일의 작업량을 제곱하여 모두 더한 값이 됩니다. 조선소에서는 1시간 동안 남은 일 중 하나를 골라 작업량 1만큼 처리할 수 있습니다. 조선소에서 작업할 수 있는 N 시간과 각 일에 대한 작업량이 담긴 배열(works)이 있을 때 배상 비용을 최소화한 결과를 반환하는 함수를 만들어 주세요. 예를 들어, N=4일 때, 선박별로 남은 ..
[프로그래머스] DFS/BFS - 네트워크 (Javascript) [ 문제 설명 ] 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. [ 제한 사항 ] 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 c..
[프로그래머스] 구현 - 풍선터트리기 (Javascript) [ 문제 설명 ] 일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다. 여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다. 당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에..
자바스크립트 - 순열과 조합 순열과 조합은 기능을 만들거나, 코딩테스트에서 자주 사용한다. 하지만 자바스크립트는 파이선과 같은 언어와 달리 자체적으로 제공해주는 함수가 없기 때문에 직접 구현해야한다. 순열과 조합은 재귀함수로 만들 수 있는데, n이 무수히 크지 않는다면( 성능을 많이 요구하지 않고, 빠르게 구현한다면 ) 재귀를 사용하여 구현하는 것이 편하다. 순열 순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미한다. (순서 상관 있음) function permutations(arr, n) { // 1개만 뽑는다면 그대로 순열을 반환한다. 탈출 조건으로도 사용된다. if (n === 1) return arr.map((v) => [v]); let result = []; // 요소를 순환한다 arr.forEach((fixe..
[프로그래머스] 그래프/BFS - 가장 먼 노드 문제풀이 (Javascript) 위 문제 설명에 노드와 간선으로 보고 그래프 문제인 것을 알 수 있다. 핵심 키워드는 "노드", "간선", "최단 경로" 최단 경로가 제일 큰 경우의 집합의 수를 구하는 문제이다 [자료구조] 그래프 노드와 간선으로 이루어진 자료구조 문제 풀이는 노드의 너비를 탐색하여 푸는 문제이기 때문에 BFS 풀이 방식 Queue를 이용해서 풀 수 있다. Queue 를 풀 때 간단하게 Array 형식으로 만들어 Shift를 사용하여 만들 수 있지만 많은 데이터를 테스트 케이스로 이용할 때 시간이 오래 걸린다는 단점이 있다. 따라서 Queue 클래스를 만들어 dequeue방식을 사용하자. Queue 클래스는 구현하기 간단하기 때문에 생각해서 자주 사용하는 것이 좋다. const graph = Array.from(Arra..
[프로그래머스] 자바스크립트 - 정렬 문제 풀이 (K번째수,가장 큰 수,H-Index) 문제 1. K번째 수 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 3. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한 사항 - arra..
[프로그래머스] 이분탐색 > 입국심사 (Javascript) 풀이 | 문제 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요. | 제한사항 입국심..