본문 바로가기

전체 글

 (12)
[Algorithm] 백준 14501 퇴사 - node.js 이 글은 백준 14501번 퇴사를 풀이한다. 알고리즘은 javascript를 이용해 구현하였다. 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다. 상담을 하..
[Algorithm] 백준 2839 설탕 배달 - node.js 이 글은 백준 2839번 설탕 배달을 풀이한다. 알고리즘은 javascript를 이용해 구현하였다. 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 ..
[Algorithm] 최장 증가 부분 수열(LIS: Least Increasing Subsequence) 문제를 푸는 두 가지 알고리즘 이 글은 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제인 최장 증가 부분 수열 문제와 이를 푸는 알고리즘 두 가지에 대해 설명한다. 최장 증가 부분 수열 문제 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수를 제거해서 부분 수열을 만들 수 있다. 주어진 수열에서 얻을 수 있는 증가 부분 수열 중 가장 긴 것을 찾는 문제를 최대 증가 부분 수열 찾기 문제(LIS: Least Increasing Subsequence)라고 부르며, 이는 매우 유명한 동적 계획법 알고리즘 문제 중 하나이다. 이 문제를 푸는 대표적인 알고리즘이 두 가지 존재한다. 알고리즘 답을 구하는 데에 필요한 배열 A, D를 정의하자. A[i], D[i]는 다음과 같다. A[i]: 수열의 i번째 수 D[i]: A[i]를 마지막 ..
[Algorithm] 백준 5904 Moo 게임 - node.js 이 글은 백준 5904 Moo 게임 문제를 풀이한다. 코드는 javascript로 작성되었다. 문제 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 "m o o"이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다. S(0) = "m o o" S(1) = "m o ..
[Algorithm] 백준 6549 히스토그램에서 가장 큰 직사각형 - node.js 이 글은 백준 6549 히스토그램에서 가장 큰 직사각형 문제를 풀이한다. 코드는 javascript로 작성되었다. 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,00..
[Algorithm] 조합(nCr)의 모든 경우를 구하는 방법(c++, javascript) 이 글은 n개의 수 중 r개를 고르는 모든 경우(조합)를 구하는 방법에 대해 설명한다. 조합 서로 다른 N개의 원소를 순서 없이 골라낸 것을 조합(combination)이라고 부른다. 모든 조합 만들기 중첩 반복문 0번부터 차례로 번호 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드를 작성해보자. 예를 들어, n이 7이라면 (0, 1, 2, 3) (0, 1, 2, 4) (0, 1, 2, 5) ... (3, 4, 5, 6)의 모든 경우를 출력하면 된다. 이를 간단하게 푸는 방법에는 다음과 같은 4중 for문이 있다. //c++ for(int i=0; i
[Javascript] 백준 1012번 유기농 배추 - node.js 이 글은 백준 1260번 DFS와 BFS를 풀이한다. Javascript를 이용해 알고리즘을 구현했다. 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. (한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다) 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 ..
[Javascript] 백준 2606번 바이러스 - node.js 이 글은 백준 2606번 바이러스를 풀이한다. Javascript를 이용해 알고리즘을 구현했다. 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 ..
[Javascript] 백준 1260번 DFS와 BFS - node.js 이 글은 백준 1260번 DFS와 BFS를 풀이한다. Javascript를 이용해 알고리즘을 구현했다. 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 예제 입력 1 4 5 1 1 2 ..
[Algorithm] 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) - 그래프 탐색 알고리즘 이 글은 그래프 탐색 알고리즘의 대표적인 알고리즘, 깊이 우선 탐색(DFS) 알고리즘과 너비 우선 탐색(BFS) 알고리즘을 소개한다. 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색 알고리즘이라고 한다. 탐색 알고리즘 중 가장 널리 사용되는 두 가지는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이다. 깊이 우선 탐색(DFS: Depth First Search) 깊이 우선 탐색은 현재 정점과 인접한 정점들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 따라간다. 이 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. 이는 재귀 호출을 이용하면 간단하게 구현할 수 있다. 너비 우선 탐색(B..
[Javascript] 배열 선언, 초기화의 모든 것 (Hacks for Creating Javascript Arrays) 이 글은 자바스크립트로 배열을 선언하는 방법들에 대해 설명한다. 배열 리터럴([]) 일반적으로 배열 리터럴을 이용해 배열을 생성한다. 그러나 동적으로 배열을 생성하기에 최적의 방법은 아니다. const array1 = [1, 2, 3]; 배열 생성자(Array()) 배열 생성자(Array())를 이용한 선언이 배열 리터럴의 대안이 된다. 아래 코드는 배열 생성자의 쓰임새를 보여준다. // 매개변수(parameter)가 하나 이상일 때 // 인자(argument)를 요소로 가지는 새 배열을 생성한다. // 배열의 길이는 인자의 개수로 설정된다. const array1 = new Array(1, 2, 3); console.log(array1); // [1, 2, 3] console.log(array1.len..
[React, React Native] 논리 연산자 AND(&&)로 조건부 렌더링할 때의 주의사항 이 글은 React, React Native에서 논리 연산자로 조건부 렌더링할 때의 주의사항에 대해 설명한다. JSX 안에는 중괄호를 이용해 표현식을 포함할 수 있다. 그 안에 javascript 논리 연산자 &&를 사용하면 쉽고 간결하게 엘리먼트를 조건부로 렌더링할 수 있다. && 연산자는 왼쪽 피연산자가 true로 간주되면 오른쪽 피연산자를, false로 간주되면 해당 리터럴을 반환한다. 다시 말해서 a&&b의 결과는 a가 true로 간주된다면 a, false로 간주된다면 b이다. 컴포넌트나 엘리먼트를 논리 연산자 &&를 이용해 조건부 렌더링하면, 왼쪽의 피연산자가 true로 간주되는 값일 때 오른쪽의 컴포넌트나 엘리먼트가 렌더링된다. 그러나 컴포넌트 조건부 렌더링 시 왼쪽의 피연산자가 false일 ..

티스토리툴바