본문 바로가기

알고리즘 풀이

 (84)
[프로그래머스] 파일명 정렬 / 2018 KAKAO BLIND RECRUITMENT(3차) - JAVA 🔗 문제 링크 [프로그래머스] 파일명 정렬 / 2018 KAKAO BLIND RECRUITMENT(3차) 코딩테스트 연습 - [3차] 파일명 정렬 파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램 programmers.co.kr 📝 풀이 과정 파일명의 문자열을 파싱하여 head, num을 추출한 뒤 정렬해야했기 때문에 문자열을 패턴으로 파싱할 수 있는 Pattern, Matcher 클래스를 사용하였다.(참고: [Java] Pattern, Matcher Class로 정규식 활용하기) Pattern pattern = Pattern.compile("(?\\D+)(?\\d+)(...
[프로그래머스] n진수 게임 / 2018 KAKAO BLIND RECRUITMENT(3차) - JAVA 🔗 문제 링크 [프로그래머스] n진수 게임 / 2018 KAKAO BLIND RECRUITMENT(3차) 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr 📝 풀이 과정 n진수로 이루어진 숫자를 차례대로 붙인 문자열을 구한 뒤 튜브가 말할 순서마다 뽑아서 붙이는 방식을 사용하였다. 구할 개수 t개에 인원은 총 m명이므로 구해야 할 숫자는 t * m보다 작다는 것을 알 수 있기 때문에 1부터 t*m까지의 숫자를 n진수로 변환한 뒤 문자열에 붙이기위해 String.toString(int n, int..
[프로그래머스] 압축 / 2018 KAKAO BLIND RECRUITMENT(3차) - JAVA 🔗 문제 링크 [프로그래머스] 압축 / 2018 KAKAO BLIND RECRUITMENT(3차) 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 📝 풀이 과정 문자열을 반복해서 사전에 넣고 찾는 작업을 해야하고, String(문자열)과 int(색인 번호)를 동시에 저장할 수 있는 Map을 사용하기로 했다. 길이가 1인 문자열을 모두 넣어주기 위해 반복문을 돌며 Map.put 해주었고, 입력 문자열을 하나씩 끊어 반복문을 돌며 탐색하였다. map.containsKey를 통해 만약 현재 key가 사전에 없을 때까지 뒤에 덧붙이는 방식..
[백준] 11779번: 최소비용 구하기 2 - JAVA 🔗 문제 링크 BOJ 11779번: 최소비용 구하기 2 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 📝 풀이 과정 다익스트라로 + 경로를 구하는 문제이다. 다익스트라는 dist 배열을 통해 현재 노드에서부터 다음 노드로 이동하는 비용이 최소 비용이 될 때 갱신하는 방법을 사용하는데, 이 때 거리를 갱신하면서 현재 노드의 위치를 함께 저장하면 경로를 구할 수 있다. 만약, 1번에서 3번으로 이동했다면 3번 전에 1번 노드를 방문했다는 의미가 되고, prev[3] = 1가 되는 ..
[백준] 10830번: 행렬 제곱 - JAVA 🔗 문제 링크 BOJ 10830번: 행렬 제곱 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 📝 풀이 과정 [백준] 1629번: 곱셈 - JAVA에서 확장된 문제다. 거듭제곱을 분할 정복으로 계산하는 같은 방식의 문제이지만, 행렬이라는 조건이 추가되었다. 행렬의 곱셈에서 A x B의 (i, j)의 값을 구하기 위해서는 A의 i열의 곱과 B의 j행의 곱을 순차적으로 더해 구해야 한다는 것을 이용해 곱셈하는 함수인 multipleMatrix(m1, m2)를 만들어 주었다. 기존 거듭제곱 문제에서는 거듭 제곱값으로 주어진 값이 ..
[백준] 1629번: 곱셈 - JAVA 🔗 문제 링크 BOJ 1629번: 곱셈 📝 풀이 과정 주어진 숫자를 제곱해야 하는데 단순하게 반복문으로 제곱수를 구하게 되면 시간복잡도는 B의 크기만큼 소요되게 되고 B의 최대 크기는 $2^{31}-1$로 시간 제한을 초과하게 된다. 따라서 정해진 제곱을 분할하는 방식을 사용해 시간을 줄여야 한다. $$ A^{10} = A^{5 + 5} = A^5 \times A^5 $$ 먼저 제곱은 위의 식처럼 분할이 가능하다. 따라서 제곱을 순차적으로 하나씩 곱하면서 구하지 않고, $A^5$를 구한 뒤 그 수를 제곱하면 $A^{10}$을 쉽게 구할 수 있는 것이다. 만약 제곱수가 11(홀수)이라면 $A^5$(절반)를 제곱한 뒤 그 수에 $A$를 곱하면 되기 때문에 빠르게 답을 구할 수 있게 된다! static lon..
[백준] 18119번: 단어 암기 - JAVA 🔗 문제 링크 BOJ 18119번: 단어 암기 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 📝 풀이 과정 단어가 알고있는 알파벳으로 구성되어 있을 때 아는 단어라고 한다. 따라서 단어를 알파벳을 기준으로 보고 단어에 포함되는 알파벳을 비트마스킹을 통해 처리하려고 하였고, 현재 알고 있는 알파벳도 비트연산을 통해 계속 누적하였다. 알파벳은 총 26자리로 이루어져있으며 처음에는 모든 알파벳을 알고있기 때문에 (1 = word) cnt++; 이후, for문으로 단어마다 기억하고 있는 알파벳과 &연산을 통해 비..
[백준] 15663번: N과 M (9) - JAVA 🔗 문제 링크 BOJ 15663번: N과 M (9) 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 📝 풀이 과정 permutation을 활용해 수열을 구하는 문제이다. 사전순으로 출력하기 위해 Arrays.sort를 활용해 입력이 들어온 숫자들을 오름차순 정렬해주었고, visit배열을 통해 같은 숫자가 수열에 포함되지 않도록 했다. input 3 1 4 4 2 -------- output 2 4 이전의 N과 M 문제들과 다른 점은 중복되는 수열이 출력되면 안된다는 점이다. 모든 수열을 구하게 되면 2,4,4..

티스토리툴바