루피도 코딩한다

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42890 풀이 흐름 후보 키 목록 뽑기 -> 비트 연산을 활용한 조합구하기 최소성 검사 -> 비트 연산 활용 유일성 검사 -> 자료구조 Set 활용 후보키 에 속하는 속성을 String으로 이어붙인 뒤 set에 넣어주기 ex) 후보키가 이름, 전공 이렇게 두가지가 있다면 아래와 같이 처리함 val hashSet = {"ryanmusic, "apeachmath" .. } 조합에 관해 느낀점 c++에서는 조합을 구할 때 algorithm STL에서 지원해주는 permutation 함수를 활용해 편리하게 구현했었다. 그런데 kotlin에서는 조합 합수의 경우 재귀함수로 구성하는 등 그 과정이 좀 복잡..

문제 : k진수에서 소수 구하기 배운 점 및 필요한 개념 정리 10진수 n을 k진수로 변환 : n.toString(k) 원래는 이거 직접 구현했었음! 마무리 reversed 잊지말기 private fun convert10ToK(n: Int, k: Int): String { var temp = n var str = "" while (temp >= 0) { str += temp % k temp /= k if (temp == 0) break } return str.reversed() } n이 소수(prime)인지 판별 :n을 2이상 sqrt(n) ‘이하’의 수로 나눠본다 이에 대한 인사이트를 주는 글 자매품으로 에라토스테네스의 체가 있다. 아래 로직을 보면 너무 당연하다 [예제] 26이하의 자연수 중 소수가 ..

Thanks to Kotlin's functional programming features, we can efficiently solve algorithmic problems compared to using traditional languages. In this post, we'll explore how to transform a list into a map under specific conditions in just one line using withIndex() and associate(). 1. Basic Notion withIndex() withIndex() is an extension function for collections in Kotlin. It enables iterati..

접근법 1) 경우의 수, 팩토리얼 활용하기 n의 값을 알때 n을 (1*2)블럭 몇개와 (2 * 1)블럭 몇개로 채울것인가? n/2를 해서 (2*1)블럭을 k개, k-1, ... 1, 0개로 채우는 경우를 생각해볼 수 있다 세로블럭 a개, 가로블럭 b개를 가지게되는 경우의 경우의 수는 이항계수를 활용할 수 있다. val vertical = a val horizontal = b(a + b) ! / a!*b! == aCb 그런데 이럴 경우 n!의 결과값 까지 모두 구해야한다는 단점이 있다. 나머지 정리이야기를 해보자. A+B를 m으로 나눈 나머지를 구하고자 할때, A를 m으로 나눴을때의 나머지와, B를 m으로 나눈 나머지를 더하면 A+B를 미리 더한값을 m으로 나눴을때의 나머지와 동일한 값을 도출할 수 있다...

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LnipaDvwDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [문제 요약] 1. BFS방법을 통해 Node를 방문한다 ex) 1 ->2->3->4 2. (1->2거리) + (2->3거리) + (3->4거리) + (4->1거리) [ISSUE] 문제를 처음 읽고 BFS + LCA를 활용하면 되는 문제라 생각하고 신나게 문제를 풀었다. 그러나 시간초과가 발생해버렸다.. 무엇이 문제일까 다시 생각을 해봤다. BFS는 정형적인 패턴이니까 시간을 더 단축하긴 어려울것이..

https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 알고리즘 분류 : Monotone Stack 문제를 읽고, 어떤 방식으로 구현해봐야 하는지에 대해 생각해보았다. 처음 생각해낸 방법은 브루트 포스 방식이었다. Array로 빌딩의 높이 값을 모두 입력 받은 다음, N만큼 반복문을 돌면서 현재 빌딩 높이와 비교하는 로직을 구하는 것이었다. 그러나 이 방법에 대해 마음에 들지 않는 두 가지 포인트가 있었다. 1. 시간복잡도가 O(n^2)이라는 ..

알고리즘 분류 : Stack (Stack으로도 풀 수 있으나, 해당 게시물에서는 Stack의 속성만을 이용) Stack으로도 풀 수 있는 문제이지만, 올바른 괄호 표현식의 원리를 이용해서 정수 Int type 변수 하나만을 사용했다. [풀이 로직] 1. N을 읽는다 2. N번 String을 받아온다. // "(()))())(" 3. 각 케이스마다 새롭게 사용할 index와 input을 초기화 해준다. * index의 경우, stack의 top을 가리키는 변수와 동일하게 -1로 설정 해 주었다. 3. 2번에서 받아온 길이만큼 반복문을 돌리며 괄호 하나 하나를 검사한다 4. 정상적인 괄호식의 경우 '('부터 시작하므로, '(' 가 들어오면 index 변수에 +1을 해준다 // stack 에서의 push에 해..

[알고리즘] 브루트 포스 어제 블랙잭 문제에 이어서 비슷한 일곱 난쟁이 문제를 풀어봤다. 9개의 정수를 받아, 그중 7개의 정수의 합이 100이 되면, 7개의 정수를 오름차순으로 출력하는 문제다. 7개의 정수를 다 더해서 100인지 확인하는 로직보다, 2개의 정수를 더한 값을 전체 합에서 뺀 케이스를 살펴보는 게 Time Complexity가 간단하겠다는 생각이 들었다. 2개의 정수의 합을 구하기 위해, 미리 구현해둔 permutation 메소드를 사용했다. 재귀로 이루어진 permutation 함수의 break point는 permutation의 수가 2개이며, 전체 정수에서 두 수의 합을 뺀 값이 100일 때로 설정했다. 위 조건을 만족하게 되면, 문제의 출력 요구조건을 맞추기 위해 sortAndPr..

[알고리즘] 브루트포스(순열) 블랙잭 문제는 순열을 활용한 문제입니다. Python에서는 itertools, C++에는 next_permutation와 같은 내장함수가 순열을 지원해 주시만, Java에서는 내장함수가 없으므로 Recursion, 혹은 다중 for문을 활용하여 이를 직접 구현해야합니다. 아래 코드는 Recursion을 활용한 방법입니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static final int CARD = 3; static int N, M; static in..