코딩하는 개굴이

광고가 게시된 블로그에서 Programmers 의 풀이는 저작권 문제로 게시할 수 없음에 따라, 일괄 비공개 처리합니다. 차후, 코딩 테스트 관련 Git 공유 등의 별도 포스팅이 있을 예정입니다. 저작권 관련 내용은 아래 공지를 참고 부탁드립니다. ( _ _ ) https://programmers.zendesk.com/hc/ko/articles/360034546572-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%EC%9D%98-%EB%AC%B8%EC%A0%9C%EB%A5%BC-%EC%99%B8%EB%B6%80%EC%97%90-%EA%B2%8C%EC%8B%9C%ED%95%A0-%EC%88%98-%EC%9E%88%EB%82%98%EC%9A%94-

큰 숫자의 팩토리얼도 계산할 수 있는지를 묻는 문제이자, BigInteger 를 사용하는 법에 대해 알려주는 문제이다. int 형의 메모리 크기는 4byte 로 표현이 가능한 범위는 -2,147,483,648 ~ 2,147,483,647이고 long은 메모리 크기는 8byte로 표현할 수 있는 범위는 -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807이다. 해당 범위가 넘어가는 경우가 존재한다면 오작동의 가능성이 존재한다. 따라서, 알고리즘을 풀 때, 무한의 정수가 들어가거나 큰 숫자가 들어갈 가능성이 있는 경우는 BigInteger를 사용하는 것을 권장한다. 본래 JAVA 에서는 BigInteger 가 문자열의 형태로 이루어져있어 어떠한 숫자든 담을 수 있..

Compare Triplets : https://www.hackerrank.com/challenges/compare-the-triplets/problem Compare the Triplets | HackerRank Compare the elements in two triplets. www.hackerrank.com 간단한 문제이다. fun compareTriplets(a: Array, b: Array): Array { // Write your code here var aScore = 0 var bScore = 0 for(i in a.indices) { if(a[i] b[i]) aScore++ } val arr = Array(2) { 0 } arr[..

Super Reduced String : https://www.hackerrank.com/challenges/reduced-string/problem Super Reduced String | HackerRank Given a string, repeatedly remove adjacent pairs of matching characters and then print the reduced result. www.hackerrank.com 2개 이상 중복되는 캐릭터가 있으면 삭제하는 문제이다. 재귀로 반복적인 확인을 수행하면 해결할 수 있다. fun superReducedString(s: String): String { // Write your code here for (i in s.indices) { if (..

import java.io.BufferedReader import java.io.InputStreamReader import java.lang.Integer.min fun main() = with(BufferedReader(InputStreamReader(System.`in`))) { val (n, m, k) = readLine().split(" ").map { it.toInt() } var team: Int = min(n/2, m) var intern = (n+m) - team * 3 while (intern < k) { intern += 3 team-=1 } println(team) }

알고리즘 뽀개기 Step 6 : 트리 알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :) 해당 내용은 백준 알고리즘 강의를 기반으로 작성되었습니다. 추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다. 트리 자료 구조의 일종으로, 사이클이 존재하지 않는 그래프 정점의 개수가 V라면, 간선의 개수가 V-1 루트(root) : 특정 정점으로부터 아래로 방향을 정할 수 있다 위의 트리에서는 1을 루트로 볼 수 있다. 부모(parent) : 1은 2,3의 부모이며, 2는 4,5의 부모이다. 자식(child) : 2는 1의 자식이며, 4는 2의 자식이다. 3의 자식은 6,7이다. 단말 정점(leaf node) : 트리의 마지막 노드를 말함 위 트리의 단..

알고리즘 뽀개기 Step 5 : 그래프 알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :) 추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다. 해당 내용은 백준 알고리즘 강의를 참고하여 작성되었습니다. 그래프 자료구조의 일종으로, 정점(Node/Vertex)과 간선(Edge)으로 구성되어있으며, G = (V,E) 로 표현한다. 아래와 같은 개념을 추가로 알아두자. 경로 : 정점 2에서 1로 가는 경로 2 -> 3 -> 1 2 -> 1 사이클 : 정점 A에서 다시 A로 돌아오는 경로 단순 경로/사이클 : 같은 정점을 두 번 이상 방문하지 않는 경로/사이클로, 문제 등에서 특별한 언급이 없을 경우 일반적인 경로/사이클은 이를 의미한다. (보통 다..

알고리즘 뽀개기 Step 4 : 정렬 알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :) 추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다. 정렬 sort 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 힙 정렬, 병합 정렬 등이 존재 주로 O(N^2), O(NlogN) 의 복잡도로 나뉘는데, 정렬 알고리즘은 빠를 수록 좋기 때문에, O(NlogN)이하로 걸리는 정렬을 사용하도록 한다. 정렬을 직접 구현하는 것보다, C++ 기준 STL 에 있는 sort (각 언어에서 구현되어있는 소팅 수단)을 사용하는 것이 좋다. sort(begin, end) 로, begin 부터 end 바로 전까지를 정렬하는 함수 리스트의 0~n 까지를 정렬할 경우, so..

알고리즘 뽀개기 Step 3 : 수학 알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :) 추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다. 수학 나머지 연산 컴퓨터의 정수는 저장할 수 있는 범위가 저장되어있기에, 답을 M으로 나눈 나머지를 출력하라는 문제가 종종 등장한다. (A + B) mod M = ((A mod M) + (B mod M)) mod M (A X B) mod M = ((A mod M) X (B mod M)) mod M (A - B) mod M = ((A mod M) - (B mod M) + M) mod M 뺄셈의 경우는 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 위와 같이 M을 더한후 mod 를 수행한다. 최..

알고리즘 뽀개기 Step 2 : 다이나믹프로그래밍 알고리즘을 최대한 간단하면서 빼먹는 부분이 없게 복습 및 요약하기 위해 포스팅을 하려고 합니다 :) 추천한 문제는 일부만 해설되어있으며, 언어는 Kotlin 입니다. 다이나믹 프로그래밍 큰 문제를 작은 문제로 나누어 푸는 알고리즘을 의미 다이나믹 프로그래밍의 조건 Overlapping Subproblem (문제를 작은 문제들로 쪼개어 풀 수 있다) Optimal Substructure (문제의 정답을 작은 문제들의 정답으로 구할 수 있다) 각 작은 문제는 한번만 푼다. Optimal Substructure를 만족하기 때문에, 같은 작은 문제일 경우 순서에 상관없이 구할 때 마다 정답이 같다. 구한 특정 작은 문제의 정답을 저장하여 활용한다. (Memoiz..