전체 글 (201) 썸네일형 리스트형 [2020 KAKAO BLIND RECRUITMENT] 가사검색(Trie, Java, 효율성, 간단한 코드) ## 접근 - Trie의 add 연산은 간단하나, find 연산은 종료 조건을 분류 * "?" 만나서 종료하는 경우, 존재하지 않은 단어를 만날 경우 ## 효율성 - Reverse라는 메소드를 정의해서 사용했는데, 매번 += 연산을 통해서 concat 시켰는데 이게 효율성을 어긋나게 했다. - ReplaceAll으로 '?'를 대체하는 것대신 '?' 발견 시 종료하도록 코드 구성 ## 해설코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 .. [BOJ 14226] 이모티콘(Java, 간단한 코드, 런타임에러, 증명) https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만�� www.acmicpc.net 이 문제를 Bottom-up으로 접근할 수 없다. 화면에 있는 이모티콘 중 하나를 삭제하기 때문에, 순차적인 접근이 이루어지기 어렵다. 1. Top-Down 방식으로 DP를 작성한다. DP의 매개변수는, 화면에 이모티콘 수와 클립보드 이모티콘 수로 2개를 사용한다. 2. BFS를 이용해서, 3가지 기능에 대해서 구현해주면 된다. 또한, 메모이제이션 기법을 통해서 중복을 제거해 시간복잡도를 줄이도.. [BOJ 12865] 평범한 배낭(Java, DP) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 전체 물품을 이용해서, 제시된 K 무게까지의 최대 가치를 구해야 한다. 소문제로 나누어서 문제를 풀기 위해서, 두 가지 변수를 사용한다. 물품과 무게를 사용해서 DP를 구성한다. 2. DP의 점화식을 세워야 하는데, DP[i][j] = max(DP[i - 1][j] + DP[i - 1][j - i번째 물품 무게] + i번째 가.. [BOJ 1024] 수열의 합(Java, 단순한 풀이) https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 2가지 방법으로 풀이를 작성하겠다. # 풀이1(직관적이나 시간복잡도가 큼). 1. 길이가 L부터 100까지 탐색을 한다. While문 내에서 합을 L만큼 더해가면서, 합이 N을 만들 수 있는 모든 수를 탐색한다. 2. 합이 N이라면, 정답을 출력한다. 해설코드(Java). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 .. [BOJ 1068] 트리(Java, 간단한 풀이, Set) https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 입력을 처리할 때, 각 노드의 부모 노드를 기억, 노드의 자식 노드들을 기억할 수 있도록 데이터를 저장하는 자료구조를 사용한다. 2. 제거해야하는 노드가 있으면, 부모 노드의 자식 노드에서 해당 노드를 지우고, 제거해야하는 노드와 연결된 노드들을 큐를 사용해 모두 체크한다. 3. 전체 노드들을 탐색하면서, 자식 노드가 0이며 제거햐아하는 노드와 연결되지 않은 것을 정답의 값에 추가한다... [BOJ 1405] 미친 로봇(Java, DFS, 간단한 풀이) https://www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자�� www.acmicpc.net 1. 로봇은 방문했던 곳을 방문하지 않고 정해진 횟수의 이동을 끝내는 경우를, 단순한 경로라고 한다. 단순한 경로들을 찾아가면서, 발생할 확률들의 합을 구하면 정답이 된다. 2. 로봇의 방문을 DFS를 통해서 전체 탐색을 하도록 한다. 해설코드(Java). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 .. [BOJ 2616] 소형기관차(Java, Dynamic Programming, 동적계획법, Bottom-up, Top-down 풀이) https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있� www.acmicpc.net 1. 다이나믹 프로그래밍 정의에 맞게 작은 문제를 이용해 큰 문제를 해결하기 위해 두 가지 매개변수 이용(소형기관차의 수, 탐색한 객실 번호) * 다이나믹 프로그래밍 감이 오지 않는다면, https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182 참고 2. 2차원 형태의 배열을 생각하고 점화식을 고려(행 : 소형기관차의.. [JAVA] 소수점 자릿수 출력하기(백준 3053, 택시 기하학) 실수를 출력해야 하는 상황에서, 소수점을 원하는 자릿수만큼 출력해야 하는 상황이 존재한다. String.format("%.nf", 실수) 실수는 double형이나 float형을 사용할 수 있고, n은 몇 번째 자릿수까지 표기할 것에 관한 변수이다. 실제 적용해볼 수 있는 문제로 아래 문제를 추천한다. https://www.acmicpc.net/problem/3053 3053번: 택시 기하학 문제 19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다. 택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다. D(T1,T2) = |x1-x2| + | www.acmicpc.net 해설코드(Java). 1 2 3 4 5 6 7 8 9.. 이전 1 ··· 6 7 8 9 10 11 12 ··· 26 다음