본문 바로가기

전체 글1049

[자바] 프로그래머스 - 3 x n 타일링 [코딩테스트 연습 Lv4] - 문제 출처 : 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges - 지형이동 문제 : https://programmers.co.kr/learn/courses/30/lessons/12902 - 코드 : 깃헙 일반적으로 DP 기본 문제로 풀어봤을 2 x n 타일링과 크게 다르지 않다. 2 x n 타일링에서 규칙성이 좀 더 찾기 어려워졌을 뿐 마찬가지로 꼼꼼하게 규칙성만 잘 찾으면 된다. 1. 우선, 2칸짜리 타일을 사용해야 하므로 무슨짓을 하던 n이 홀수라면 전체 칸 수(3 x n)가 홀수이므로 2칸짜리 타일로 타일링이 불가능하다. 즉, n이 짝수일 때만 타일링이 가능하다. 이 부분은 예외로 처리해준다. (코드 10line) 2. 가장 기본적인 .. 2021. 10. 21.
백준 16497 자바 - 대출 요청 (BOJ 16497 JAVA) 문제 : https://www.acmicpc.net/problem/16497 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16400/BOJ_16497.java 이 문제의 경우, 31일까지 모든 날짜에 대해 현재 대출되어 있는 책의 수를 세보면 간단히 풀 수 있다. 이 때 주의점은 (3, 6)이라면 3일에 빌려서 6일 0시에 딱 반납된다고 생각하면 된다. 즉, (3, 6)과 (6, 8)이 있다면 k=1 일때도 처리할 수 있다는 의미이다. 따라서 (3, 6)이라면 3일에 빌려서 5일까지만 가지고 있다고 생각하면 된다. 그럼 문제에 나온 기본 예시 (1, 2), (3, 6), (5, 8)은 다음과 같이 나타낼 수 있다. 이와 같이 모든.. 2021. 10. 19.
백준 16666 자바 - Guest Student (BOJ 16666 JAVA) 문제 : https://www.acmicpc.net/problem/16666 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16600/BOJ_16666.java 어렵진 않고 그냥 수학적으로 생각해서 구현하면 되는거긴한데.. 코드보면 알겠지만 이래놓고 실버라니 숭악하다. 0. 일단 매 TC 마다 입력을 받아두고(14line), 1로 시작하는 위치에서 모두 시작해본다. (15~16line) 1. 거기서 부터 일단 k가 0이될 때 까지 돌려본다.(19~22line) -> 이 때 k가 0이 된다면 그걸로 해당 회차는 끝 (23line) -> 그렇지 않다면 다음 로직으로 2. 다음으로 중간 부분은 수학적으로 나눗셈을 활용해서 날려버릴 수 있.. 2021. 10. 18.
백준 11376 자바 - 열혈강호 2 (BOJ 11376 JAVA) 문제 : https://www.acmicpc.net/problem/11376 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/11300/BOJ_11376.java 기본적인 형태의 이분 매칭 문제이다. 다만 한 사람당 2개의 일을 할 수 있으므로, n을 2배로 늘렸다. 이 때 간선 정보는 n개만 유지할 수 있도록 하는것이 좋다. 내 경우엔 그래서 간선정보를 n개 받아두고, e[n/2] (12line) 형태로 받아온다. 사실 이분 매칭에서 매칭시킬 때, 기본형태에서 그 안에 들어있는 n의 번호 자체는 중요한게 아니므로(같던 다르던 상관 없음) 코드의 45line처럼 for문 돌릴 필요 없이, 그냥 그 내에서 다시한번 2번을 돌리도록 해도.. 2021. 10. 17.
백준 11375 자바 - 열혈강호 (BOJ 11375 JAVA) 문제 : https://www.acmicpc.net/problem/11375 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/11300/BOJ_11375.java 이분매칭에 응용같은걸 끼얹지 않은 기본형 문제이다. 따라서 단순히 '이분 매칭'을 공부해서 풀어도 바로 풀 수 있으며, 아이디어에 대한 힌트만 보려면 이 글(https://nahwasa.com/36)의 하위호환이므로, 이 글의 그림 있는 부분부터 보면 이 문제의 풀이 방식과 동일하다. 빨리 각 알고리즘이나 자료구조들에 대한 글을 써서 그런걸로 링크를 달면 깔끔할텐데.. 그런거 쓰려면 한편한편이 너무 오래걸린다 ㅠ 열심히 해야지.. 2021. 10. 16.
백준 18138 자바 - 리유나는 세일러복을 좋아해 (BOJ 18138 JAVA) 문제 : https://www.acmicpc.net/problem/18138 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/18100/BOJ_18138.java 일단하나씩 매칭시키는 문제이니 이분 매칭 문제인건 알겠는데, 그래프에 간선이 없다. 그러니 로직은 간단히, 1. 입력을 받는다 (init()) 2. 간선을 만든다 (makeEdge()) -> 이 때, w가 동일한게 안들어온다는 보장이 없으므로 w 대신 인덱스 번호로 새로 매칭시킨다. n개와 m개에 대해 0~n과 0~m을 노드로 하는 그래프로 바꾸면 된다. 간선을 만든 이후 w값은 필요없어진다. (62line) 3. 이분 매칭 돌린다 (matching()) 이분 매칭의 경우,.. 2021. 10. 16.
백준 14217 자바 - 그래프 탐색 (BOJ 14217 JAVA) 문제 : https://www.acmicpc.net/problem/14217 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/14200/BOJ_14217.java 문제 길이에 비해 사실 생각보다 쉬운 문제이다. 결국 시간복잡도가 문제인데, 가장 쉽게 생각할 수 있는 방법은 그냥 무작정 q줄에 대해 매번 해당 edge를 추가하거나 제거한 후 최단거리를 찾아보는 방식이다. 그럼 최단거리 찾기에 가장 간단한 bfs부터 보자. O(V+E) 정도이므로, O(N^2)정도고, q가 최대 500번이므로 최종적으로 최악의 경우 O(500^3) 정도로 별 문제가 없다는걸 알 수 있다. 그러니 그냥 입력 쫙~ 받고 q줄에 대해 매번 간선을 제거하거나 추.. 2021. 10. 14.
아두이노로 화장실에 사람 있는지 체크하는 무언가 만들기 [1편] 아두이노로 화장실에 사람 있는지 체크하는 무언가 만들기 1편. 아두이노를 사용했으므로 정말 'Toy' 프로젝트! 반 장난으로 시작했지만 약간 진심으로 재밌게 하고 있습니다.ㅋㅋ [ 시작 이유 ] 회사 화장실이 남,여 공용이다보니 한명씩 밖에 못들어간다. 보통 들어갈 때 푯말을 '사용중'으로 하고, 나올 때 '공실'로 돌려둬야 하는데 가끔씩 까먹는 사람들이 있다. 그럼 다른 사람들이 사용중인지 아닌지 알 수가 없어 일단 기다려보다가 너무 오래 지났다 싶으면 '똑똑' 노크 해봐서 확인하는 식이다. 또한, 안쪽 자리에 앉은 사람들은 현재 사용중인지 확인하기 위해 먼 거리를 이동해야 하므로 근손실이 날 수 있고, 우연히 확인할 때 마다 계속해서 사용중일 수 있으므로 정신건강에 안좋을 수 있다. -> 술먹다가 얘.. 2021. 10. 14.
자료구조 큐, 스택, 덱 (Queue, Stack, Deque) Queue, Stack, Deque(=Double-ended Queue) 큐, 스택, 덱은 배열, 리스트와 함께 선형 자료구조에 속하는 자료구조들이다. 사실 큐, 스택, 덱의 모든 기능은 리스트(이하 '리스트'라는 단어는 모두 Linked List를 뜻함)만 사용해서도 시간복잡도 마저 동일하게 동작할 수 있다. 즉, 어찌보면 스택, 큐, 덱은 리스트에 포함되는 자료구조라고 볼 수 있다. 그럼에도 큐, 스택, 덱은 분명 리스트와는 별개의 자료구조로 정의되어 사용되고 있다. 이건 일종의 컨셉, 규칙에 해당한다고 생각한다. 술먹고 있는데 상대방이 갑자기 병따개를 준다. 병따달라는 의도를 바로 파악할 수 있다. 술먹다가 이번엔 상대방이 멀티툴을 갑자기 준다. 물론 멀티툴엔 병따개가 있다. 하지만 난 멀티툴을 받.. 2021. 10. 11.
백준 1412 자바 - 일방통행 (BOJ 1412 JAVA) 문제 : https://www.acmicpc.net/problem/1412 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01400/BOJ_1412.java 플래 중위권 문제치곤 그리 어렵지 않았다. 구현이 어렵다기보다는 아이디어를 떠올리기 좀 어려울 수 있는 문제라 티어가 높게 책정된 듯 하다. 일단 '도시 x에서 출발해서 다시 그 도시 x로 돌아올 수 없게 만드는 것이다.' 부분을 만족하려면, 결국 자기 자신으로 되돌아오는 Cycle이 없으면 된다. 여기까진 쉽게 생각할 수 있는데 그럼 양방통행와 일방통행 도로의 두 종류가 있는 상황에서 어떻게 해야 Cycle을 없앨 수 있는지가 관건이다. 그래서 일단 그려보며 열심히 생각해봤는.. 2021. 10. 11.

티스토리툴바