프로그래밍 공부하기

Union-Find Sturucture이란 서로소 집합(Disjoint Set)을 저장하기 위한 자료구조이다. 서로소 집합이란 그림과 같이 공통원소가 존재하지 않는 두 집합을 의미한다. Union-Find는 두 노드가 서로 같은 그래프에 속하는지 판별하거나 그래프의 사이클(순환 경로)을 판별하기 위해 사용한다. 1. Operation Find: 특정 원소가 속한 부분 집합을 구한다. Union: 2개의 부분 집합을 하나의 부분 집합으로 합친다. Union-Find 구조는 Find와 Union 2가지 연산으로 구성된다. Find는 자료구조 내에서 해당 원소가 속해있는 집합을 찾는 연산이다. Union은 두 개의 집합을 합칠 수 있는 경우 합치는 연산이다. 2. Example 위와 같은 노드와 경로가 있다고..

Candies | HackerRank Help Alice to save money by minimizing the total number of candies. www.hackerrank.com 학생들에게 사탕을 1개 이상씩 나눠줄 때 필요한 사탕의 최소 갯수를 구하는 문제이다. 단, 서로 이웃해있는 두 학생들 중 점수가 높은 아이는 더 많은 사탕을 주어야한다. 또한 점수가 같은 경우 반드시 사탕을 같은 갯수로 줄 필요가 없다. 즉, 학생들의 점수가 [1, 2, 2] 라면, 사탕은 [1, 2, 1] 개를 주어야 사탕의 최소 갯수가 된다. 1. 문제 분석 주어진 예시를 한 번 풀어보자. 단순하게 생각하면 i번째 학생은 i - 1 번째 학생보다 점수가 높으면 i -1 번째 학생보다 +1개를 갖고, 점수가 낮으..

Array Manipulation | HackerRank Perform m operations on an array and print the maximum of the values. www.hackerrank.com a-b 구간에 k를 더해나가면서 가장 큰 k 누적 값을 찾는 문제이다. 예제를 살펴보자. 1. 예제 문제에서는 query라는 이름으로 (a, b, k)의 순서쌍이 여러개 주어진다. 이 쿼리들을 0으로만 구성된 배열에 적용해나가면서 최종 배열의 최대 값을 찾는 문제이다. 단, 인덱스는 1부터 시작한다. 처음에는 모든 값이 0이다. (1, 5, 3) 은 배열의 1번부터 5번까지 3을 더하라는 의미이다. 실행 결과는 step1 이다. (4, 8, 7) 은 배열의 4번부터 8번까지 7을 더하라는 의..

NumberOfDiscIntersections coding task - Learn to Code - Codility Compute the number of intersections in a sequence of discs. app.codility.com index를 중심으로, value를 반지름으로 하는 원을 그렸을 때 교차하는 원들의 쌍의 갯수를 구하는 문제이다. 예를 들어 A = [1, 2]라는 배열이 있다면 첫 번째 원은 0을 중심으로 1을 반지름으로 하는 주황색 원이다. 두 번째 원은 1을 중심으로 2를 반지름으로 하는 붉은색 원이된다. 이 둘은 겹쳐져있으므로 답은 1이 된다. 1. 풀이1 O(N^2) 원이 겹치는 것은 2가지 경우가 있다. 첫 번째는 한 원이 다른 원을 포함하는 경우, 두 번째는..

코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 밟을 수 있는 횟수가 정해진 돌들로 이루어진 징검다리를 건널 때 최대 몇 명이 징검다리를 건널 수 있는지를 찾는 문제이다. 이 때 각 징검다리의 돌은 주어진 k 만큼 뛰어 넘을 수도 있다. 1. 문제 분석 문제를 봤을 때 가장 먼저 든 생각은 제한 사항의 숫자들이 상당히 크다는 점이다. stones 배열의 크기는 1~20만 범위이며, stones의 원소 값은 1~2억까지 범위를 갖는다. 따라서 해결 방법이 입출력 예시처럼 한 사람씩 건너지는지 확인하는 것은 O(N*M) 즉, stones.length * stones의 원소 범위 만큼의 시간이 걸리므로 시간초과에 걸릴 것이다. ..

코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 팰린드롬은 앞뒤를 뒤집어도 똑같은, 예를 들어 '토마토' 같은 문자열이다. 문자열을 주면 가장 긴 팰린드롬을 찾는 문제이다. 1. 문제 분석 문제의 핵심은 어떤 문자열이 회문임을 알면 해당 문자열의 앞뒤 글자만 확인하면 더 긴 회문이 있는지 확인할 수 있다는 점이다. 예를 들어 위처럼 'abcba' 문자열에서 길이 1인 회문 'c'를 찾았다고 해보자. 이 때 c 앞뒤의 문자열을 보면 더 긴 회문이 존재하는지 ..

[자료구조 포스팅] 1. Stack, Queue 2. Linked List 3. Hash Table 4. Graph 5. Tree 1. Priority Queue 일반적인 Queue와 달리 데이터를 출력할 때 입력 순서와 상관없이 우선순위가 높은 데이터를 먼저 출력하는 Queue가 Priority Queue이다. 우선순위 큐는 보통 Heap 자료구조로 구현하며, 우선순위가 있는 작업, 예를 들면 운영체제의 작업스케줄러(SJF/최단작업우선스케줄링 등)에 사용된다. 우선순위 큐를 Heap으로 구현하는 이유는 무엇일까? Priority Queue를 선형자료구조(큐, 스택, 연결리스트)에 저장할 경우 데이터 입출력 시 데이터의 우선순위에 따라 Queue에 존재하는 데이터들이 한 칸씩 밀리거나 당겨지는 일이 발생..

코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만 programmers.co.kr 각 원소의 합이 s가 되는 n개의 수의 집합 중 모든 원소의 곱이 최대가 되는 집합을 구하는 문제이다. 예를들어 n = 3, s = 8 이라면 답은 [3, 3, 4]이다. 1. 문제 해결 방법 문제는 크게 2가지 방법으로 해결할 수 있다. 첫 번째는 모든 경우의 수를 찾는 것이고 두 번째는 조건에 맞는 답을 바로 찾는 것이다. 후자가 당연히 효율적이므로 조건에 맞는 답을 바로 찾을 수 있는 방법을 찾아보자 n = 2, s = 9 -> [..

https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 위 문제를 간단히 요약하자면 배열의 각 요소들을 총 n번 빼고 뺀 결과들의 제곱의 합이 최소가 되기 한다. 이때 숫자가 클 수록 제곱을 했을 때 변화량이 크기 때문에 배열의 각 값들이 고르게 분포되도록 값을 빼주어야 한다. 즉, 매번 배열에서 가장 큰 숫자를 골라 -1해주는 것이 좋다. function solution(works, n) { cons..

코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대 programmers.co.kr 하노이의 탑은 재귀를 연습할 수 있는 유명한 문제이다. 하노이의 탑을 통해 재귀를 찾고 JS 코드로 구현해보자. 1. 재귀 1. 큰 문제를 더 작은 문제로 계속 나눈다. 2. 가장 작은 문제를 해결한다. 3. 가장 작은 문제의 해결을 이용하여 큰 문제를 해결해나간다. 일반적으로 재귀함수는 위와 같은 형식으로 문제를 해결한다. 이를 코드로 나타내면 다음과 같다. function recursive(input1, input2, ...) { //..