본문 바로가기

Java/알고리즘63

k진수에서 소수 개수 구하기 문제는 생각보다 쉬웠다. 완전탐색으로 풀수도있지만 조건을 잘 보면, 그냥 0으로 스플릿해서 스플릿된걸 소수인지아닌지만 판별하면 되는거였다. 그래서 1트에 어떻게 풀었는지 설명을 해보겠다. ㅇ 1트 몇진수로 바꿔라 하는 k는 10이면 Integer.toString(n) 을써서 그냥 int를 String으로 그대로 바꿔줬고, 10이 아닌경우에는 k진수로 바꿔주는 Integer.toString(n,k)를 썼다. cnt는 0을 기준으로 슬라이싱하고 각 원소들이 소수이면 갯수를 세도록 만들었고, cntN는 String a (n을 k진수화한거) 자체가 0이없는 소수일경우에, 0이 있는지 없는지를 세기 위해 만들었다. num은 a를 다시 Long형으로 바꾼거고, a를첨부터 끝까지 돌면서 0이 있으면 cntN++ 해준.. 2023. 10. 24.
알고리즘 공부(1) - 자료구조(스택,큐) 요즘 매일 아침마다 알고리즘을 하나씩 풀면서 느낀점은 자료구조를 잘 쓸수있어야 한다는점이다. 자바에서 자료구조를 어떻게 쓰는지 하나씩보자. 이건 내가 공부하면서 그냥 나혼자 볼생각으로 적어본다. 자바에서 사용하는 자료구조에는 어떤게 있을까? 자바에는 자료구조를 표현하는 인터페이스인 컬렉션(Collection)이 있다. 컬렉션을 구현한 자료구조는 List, Set, Queue, Stack, Map이 있다. https://kimchanjung.github.io/etc/2020/01/15/java-collection/ JAVA - 자료구조, Collection 별 특징 정리 JAVA Collection별 특징과 시간 메소드별 시간 복잡도를 일목요연하게 정리한 내용입니다. JAVA - 자료구조, Collecti.. 2023. 10. 23.
타겟넘버 이것도 완전탐색으로 풀어야겠다는 감이왔다. 어제 풀었던걸 응용해봐야겠다 싶다가 -인경우도 생각해봐야해서 다르게 생각했다. 재귀로도 물론 풀수 있지만 비트마스킹을 사용해 풀수도있다. 기본적인 풀이 과정을 요약하면 이렇다. 주어진 num 는 모두 양수니, 모든 원소를 음수로 바꾼 min를 만들어서 깊이우선탐색을 진행한것이다. ㅇ 비트마스크 (bit mask) 이진수를 이용해 연산을 하면 빠르게 연산이 가능하다. 이진수는 0 or 1만을 이용함. 비트마스크는 수행시간이 대부분O(1)로 다른 자료구조보다 더 빠르다. https://wogud6792.tistory.com/63 비트마스크 (BitMask) 알고리즘 [목차] 1. 비트마스크(BitMask)란? 2. 비트마스크의 장점 3. 비트 연산자 4. 비트마스크.. 2023. 10. 20.
피로도 ㅇ 문제 처음에 조건보고 너무쉽네ㅋㅋ 하고 자세히 보니, 모든 경우의수를 돌아봐야겠다 싶어서 절망했다.. 일단 조건은 dungeons를 쭉 순회할때, dungeons의 행이 k 이하일때, k - 열을 해주고 cnt++ 해준다. 그럼 끝인데, 문제는 모든 경우의수를 어떻게 만드냐가 관건이었다. 그래서 그냥 모든걸 메서드로 만들기로 생각하고 순열을 만드는 메서드를 만들어 재귀로 풀었다.(사실 구글링함) ㅇ 내풀이 //저장한 permutation 을 불러온다. //각 순열에서 maxTry를 해서 answer에 저장하고 전에 저장한 answer보다 크면 answer에 저장. public static int solution(int k, int[][] dungeons) { int answer = 0; List pe.. 2023. 10. 19.

티스토리툴바