본문 바로가기

전체 글1063

백준 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.
백준 3015 자바 - 오아시스 재결합 (BOJ 3015 JAVA) 문제 : https://www.acmicpc.net/problem/3015 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/03000/BOJ_3015.java 우선 체크를 어느 방향으로 할 지 정해보자. 전 왠지 입력 다 받고 풀기보단 입력 받으면서 바로바로 풀고 싶었기에 N번째 사람을 입력받을 때 그 이전사람들을 체크해보기로 했다(입력 받으면서 바로바로 하려면 그 이후 사람에 대한 정보는 없으므로 그 이전 사람들만 가지고 생각해야한다!). 방향을 저와 같이 정했다면, 이번에 입력된 사람보다 키가 작은 이전사람은 의미가 없다는 것을 알 수 있다. (위와 같이 4명까지 확인했다. 그리고 5명째를 확인하려고 하는데, 사실 이 때 N=2와.. 2021. 10. 10.
AtCoder Beginner Contest 222 참여후기 (ABC 222) Contest : https://atcoder.jp/contests/abc222 Editorial : https://atcoder.jp/contests/abc222/editorial AtCoder는 구글 번역기 돌려도 제대로 번역이 안되서 영어로 읽어야한다... 수식 포함된 영어는 특히 읽기가 어려워서 머리에 잘 안들어온다 ㅠ 영어공부좀 해야지 특히 C번에서 문제 대충 읽다가 이해 잘못해서 시간을 쓸데없이 많이 들이다보니 문제를 D번까지밖에 못봤다. Beginner 라고 써있으면서 많이 어려웡.. 아직 늅늅이가 맞으니 어려운게 맞을듯함. 아직 레이팅 엄청 낮은 늅늅이지만 그래도 꾸준히 올라가긴 하니 다행임. Editorial이 이미 공개되었으니 별도로 해설은 하지 않고 대회진행중에 푼 문제에 대해 후기만.. 2021. 10. 9.
백준 15779 자바 - ZigZag (BOJ 15779 JAVA) https://www.acmicpc.net/problem/15779 i번째 데이터에 대해, i-2, i-1, i 번째 데이터를 살펴보며 단조증가 수열이거나 단조감소 수열일 경우 arr[i] = 0을 기입했고, 지그재그 수열일 경우 1을 기입함.(13line) 그럼 예를들어서 문제에 제시된 2번째 예시 (1,3,4,2,5)의 경우 제가 짠 로직으로는 arr = [0, 0, 0, 1, 1] 와 같이 기입됨. 근데 이 때 1이 연속된 갯수가 결국 지그재그 수열의 길이이므로, 13line처럼 이전값+1을 해주면 연속된 길이도 한꺼번에 구할 수 있음. 최종적으로 arr 배열에 있는 가장 큰 수가 가장 긴 지그재그 수열의 길이이므로 max값을 찾아주고 (19line) 거기에 2를 더해준게 답임. (+2를 해준 것은.. 2021. 10. 8.
백준 2759 자바 - 팬케이크 뒤집기 (BOJ 2759 JAVA) https://www.acmicpc.net/problem/2759 알고리즘 분류를 굳이 따지자면 constructive, ad-hoc, greedy 쪽일 것 같음. 애초에 답으로 가능한 경우 어떤 것이든 출력하면 되기도 하고, 이런 류의 문제를 풀기위한 well-known 스러운 풀이도 없다고 판단되므로 논리적 추론을 통해 이 문제만의 풀이과정을 만들어야 하는 종류의 문제이다. Brute force로 모든 경우를 보면 최대 O(30^30) 이라는 괴랄한 수가 나오므로 절대 무리.. 전 일단 가장 큰 수 부터 차례대로 맨 아래로 가야한다는 부분에 포인트를 맞추고, 그럼 위에서 k개를 뒤집는 방식으로 어떻게 가장 큰 수부터 차례대로 맨 아래로 내릴지 생각해봤다. 결론적으로 제 풀이는 다음과 같음. 가장 큰 .. 2021. 10. 7.
백준 15993 자바 - 1, 2, 3 더하기 8 (BOJ 15993 JAVA) https://www.acmicpc.net/problem/15993 f(n)을 정수 n을 1,2,3의 덧셈으로 표현 가능한 가지수라 정의하면, f(n) = f(n-1) + f(n-2) + f(n-3) 이다. 왜냐하면 예를들어 n=5라면, f(5)는 f(4)의 모든 표현의 뒤에 +1을 붙인 것 + f(3)의 모든 표현의 뒤에 +2를 붙인 것 + f(2)의 모든 표현의 뒤에 +3을 붙인 것 이기 때문이다. 위 식을 배열로 나타내자면 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]; 이 된다. 그런데 이상태로는 짝수가지수와 홀수가지수를 알 수 없다. 따라서 dp를 2차원 배열로 확장해서 dp[a][b]로 보자. a가 1,2,3의 합으로 나타내려는 정수, b는 0일 때 짝수인 경우, 1일 때 홀.. 2021. 10. 7.
백준 22866 자바 - 탑 보기 (BOJ 22866 JAVA) https://www.acmicpc.net/problem/22866 풀이방법을 생각하기보다는 구현이 복잡한(==귀찮은) 문제였다. 일단 3가지로 나눠서 생각해봐야 하는데, 1. 각 건물에서 좌측으로 보이는 건물의 개수 2. 각 건물에서 우측으로 보이는 건물의 개수 3. 각 건물에서 가장 가까운 건물 번호 중 작은 번호 위와 같다. 일단 '각 건물에서 좌측으로 보이는 건물의 개수' 어떻게 구할지 생각해보자. 문제에서 제시된 예시를 예시로 들겠다. 3 7 1 6 3 5 1 7 에서 좌측부터 차례로 봐보자. 1번째 건물 : 3 이다. 현재 좌측으로 보이는건 없다. 뭐 일단 어딘가에 넣어둬보자. 2번째 건물 : 7 이다. 현재 좌측으로 보이는건 없다. (7보다 높아야 보임). 그 이후로는 모두 7에 막힐것이므로.. 2021. 10. 5.