SH

BOJ Link https://www.acmicpc.net/problem/1106  풀이 과정문제에서 호텔의 고객을 적어도 C명 늘려야 하기 때문에, C보다 고객이 많은 경우도 고려해야 한다.한개의 홍보로 얻을 수 있는 고객의 수는 100보다 작거나 같은 자연수이므로, C+100명까지 dp에 기록한다.이후, C~C+100번째 dp중 최소 값(홍보비용)을 출력한다. 또한, 배낭 문제를 1차원 dp로 다룰 수 있다.이때, Bounded(0-1) Knapsack인 경우 맨 뒤 인덱스부터 탐색해야 하며,해당 문제는 Unbounded Knapsack이므로 앞의 인덱스부터 탐색한다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java...

이슈VM에 ES 설치 도중, Window 환경 컴퓨터(호스트)의 텍스트가 Ubuntu 환경 VM(게스트)에 Copy&Paste 되지 않음 호스트 - 실제 하드웨어(컴퓨터) 게스트 -  호스트 컴퓨터 위에서 가상화 소프트웨어  해결 방법 가상 머신의 게스트 확장 패키지 설치 이후 클립보드 공유 양방향 설정   1. 게스트 확장팩 이미지 다운sudo apt updatesudo apt install virtualbox-guest-additions-iso 2. 이미지 삽입장치(Device) -> Guest Additions CD 이미지 삽입(Insert Guest Additions CD image) 클릭 3. 게스트 확장팩 마운트 & 런 /dev/cdrom -  CD 또는 DVD 드라이브를 나타내는 디바이스 ..

BOJ Link https://www.acmicpc.net/problem/1047  풀이 과정나무의 개수 N=40이다. 조합으로 접근할 수 없다.대신에, 울타리(직사각형의 영역)의 관점에서 생각한다. 나무의 좌표를 정렬한 배열을 통해, 탐색할 모든 영역을 구한다.이는 총 O(N^5)이며, 나무의 개수가 작으므로 가능하다. 1. 어떤 나무들을 모두 포함하는 울타리의 최소 둘레는, (가로변 길이+ 세로변 길이) *2이다. 이를 위해 꼭짓점 좌표 4개를 구해준다. 이 때, 가로/세로 길이가 0이 될수 있으므로 xleft==xright, yleft==yright인 경우도 고려한다. (O(N^4)) 2. 구성한 울타리를 기준으로, 안에 있는 나무와 밖에 있는 나무를 구해준다. 여기서 밖에 있는 나무란, 사실상 해..

BOJ Link https://www.acmicpc.net/problem/1234   풀이 과정dp[n][r][g][b]을 선언 후, bottom-up dp로 진행한다. n번째 레벨을 채우는 방법은 3가지이다. 1. 한 가지 장난감으로 꾸밀 때n-1의 dp에서 한 장난감을 n개 빼준다.경우의 수는 이전과 동일하므로, n-1번째 dp와 같다. 2. 두 가지 장난감으로 꾸밀 때해당 경우가 가능하려면, n이 2의 배수여야 한다.r=2, g=2 두가지 장난감으로 n=4의 레벨을 채운다면,2개의 자리에 r을 채운 후, 나머지를 g로 채운 것과 같다. (어떤 장난감을 먼저 배치해도 상관 없다.)r만 채운다면, g는 자동으로 올바르게 채워진다.따라서, 이는 곧 4C2이다. 3. 세 가지 공으로 꾸밀 때해당 경우가 가..

BOJ Link https://www.acmicpc.net/problem/1949   풀이 과정트리에서의 다이나믹 프로그래밍(+dfs) 문제다. 우선 임의의 정점을 루트로 잡고, top-down dfs로 리프 노드로 이동한다. 이후, 부모의 dp배열dp[parent][1]  - 우수 마을일 때dp[parent][0]  - 우수마을이 아닐 때 를 bottom-up으로 다음과 같이 채워나간다. 한 노드가 우수 마을 이라면, 인접한 노드는 모두 우수 마을이 아니여야 한다. 따라서,dp[parent][1] += dp[child][0]; 를 자식의 개수만큼 반복한다. 한 노드가 우수 마을이 아니라면, 인접한 노드는 우수 마을일 수도, 아닐 수도 있다. 따라서,dp[parent][0] += Math.max(dp[c..

목차 추가 메서드의 전체 코드는 다음과 같다.import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;class Main { static class Node { Map childNode; boolean endOfWord; public Node() { this.childNode = new HashMap(); this.endOfWord = false; } } static class Trie { Node root; Trie(Node node) { th..

BOJ Link https://www.acmicpc.net/problem/1041   풀이 과정그리디 + 구현 문제이며, 간만의 하드 코딩이였다. 1. 한 개의 주사위 구성하기 한 개의 주사위에 대해, 문제에서 요구하는 경우는 3가지이다.그리디 하게 정답을 구성할 수 있으므로, 아래의 값만 사용하여 최종 주사위를 구성한다. 주사위의 한 면만 보일 때 (min1)한 면의  최소값이다. 주사위의 두 면만 보일 때 (min2)인접한 두 면의 최소값이다.A면과 F면처럼 두 면이 수평한 경우를 제외하고 모든 경우를 구해준다. 주사위의 세 면만 보일 때 (min3)인접한 세 면의 최소값이다. 조합의 응용으로 구할 수 있나 생각했지만, 이는 꽤나 고려해야할 조건이 생긴다.대신, 하드 코딩으로 i번째 면과 두개의 면이..

BOJ Link https://www.acmicpc.net/problem/19580   개요정렬 + 우선순위 큐 + 그리디 문제이다. 추가 시간이 없는 문제라 Java로 풀시 까다롭다.O(M+N+(M+N)log??) 코드로도 시간 초과를 받았다.이후 sort 2번 + pq 1개 코드에서, pq 3개로 바꿔서 통과했다. 풀이 과정탐색 이전에, 시민을 마스크를 사려는 최소 가격(s)기준 오름차순으로 정렬한다. 이후 마스크를 가격(price)기준 오름차순 정렬한다.(s가 같다면 최대 가격(e)기준 오름차순 정렬할 필요는 없다.) 이후 탐색한다. 이 때, 정렬 후 판매할 수 있는 시민 후보를 담은 우선순위 큐를 별도로 사용해야 하는 이유는 다음과 같다. 우선 순위 큐를 사용하지 않을시, 첫번째 시민의 s가 2이..

https://softeer.ai/practice/7727 HAST 모의고사를 경험했기에, 외부 IDEA를 쓰지 않는 것에 익숙해졌다. 때문에 자바 Docs를 보지 않고 진행할 수 있었다. 그래프 탐색 문제이며, 나는 DFS로 구현하였다. 시간 복잡도최대 3명의 친구가 각각 3번씩 움직인다. 이를 delta 배열(4)로 구현하면,O(4^(3*3)) = O(262144)가 나온다. 충분히 브루트포스 할 수 있다. 친구들은 같은 칸에 방문할 수 있으며, 해당 경우엔 값을 한 번만 누적한다.나는 방문체크 배열만 기록하고 마지막에 계산하는 방식을 선택했다.(방문 횟수는 딱히 상관 없으므로 boolean 배열로 구현해도 된다.) 또한, BFS를 사용한다면, 형상 복귀가 까다롭다. 때문에 DFS를 사용했다. 각 친..

목차 트라이 (Trie/Prefix Tree)데이터(주로 문자열)을 효율적으로 저장하고 탐색하기 위한 자료구조이다.검색을 뜻하는 단어 Retrieval 에서 유래되었으며, 트리 형태로 이루어져있다.접두사를 기반으로 동작하기에, Prefix Tree라고도 불린다.   적용 사례  "아이"라는 키워드를 검색했을 때, 해당 단어를 접두사로 하는 모든 단어를 표시해준다.이렇듯 접두사를 활용할 수 있는 자동완성 기능, 자연어 처리(NLP), 맞춤법 검사기(Spell Checker)등에 사용된다. 트라이의 특징1. 접두사(prefix)를 기반으로 문자열을 저장한다.node라는 문자열을 저장하면, 해당 문자열과 함께 접두사인 n, no, nod또한 저장된다. (node 또한 node의 접두사이다.)밑에 등장하지만, ..