본문 바로가기

백준756

백준 13306 자바 - 트리 (BOJ 13306 JAVA) [ 백준 13306 ] [ 코드 (깃헙) ] 트리의 부모를 알려주고, 주어진 쿼리를 해결하는 문제이다. 쿼리는 '0 b'와 같이 들어오면 b번째 edge 제거하는 쿼리와, '1 c d'와 같이 들어오면 c와 d 사이에 연결경로가 있는지 묻는 쿼리가 있다. 일단 거리 자체를 묻지 않고, 연결 경로가 있는지만 파악하면 된다. 그럼 이거엔 union-find 알고리즘을 쓰면 될 것임을 알 수 있다. 다만 해당 알고리즘의 경우 그룹간의 관계를 맺는것은 쉽지만, 연결을 끊는건 힘들다. 그럼 쿼리를 반대순서로 보면 어떻게 될까? 원래 순서대로라면 '간선들이 존재하는 그래프에서 edge를 제거하면서 중간중간 특정 노드간에 연결경로가 있는지 묻는 쿼리' 이지만, 반대로 미리 쿼리상에 존재하는 모든 간선을 제거한 후 역.. 2021. 11. 4.
백준 1138 자바 - 한 줄로 서기 (BOJ 1138 JAVA) [ 문제보기 ] [ 코드보기(깃헙) ] N이 최대 10이다. 따라서 모든 경우를 보려면 10! 번을 봐야한다. 이 경우 362880번으로, 사실 모든 경우를 봐도 가능하긴 하다! 다해봐야 O(N! * N) 정도이다. 사실 시간복잡도, 메모리복잡도 면에서 모두 이득인 방법이 더 있다. 어차피 입력이 키가 1인 사람부터 차례대로 들어오기 때문에, 키가 큰 사람부터 순서대로 입력을 만족하는 위치에 넣어버리면 된다. (따라서 그리디 알고리즘 분류다.) 4 2 1 1 0 의 입력을 확인해보자. 이 경우 키가 1인 사람은 좌측에 2명, 2인 사람은 좌측에 1명, 3인 사람은 좌측에 1명, 4인 사람은 좌측에 아무도 없다는 입력이다. 키가 작은 사람부터 보자면 어려운 문제가 확실하지만, 키가 큰 사람부터 보면 엄청 .. 2021. 11. 3.
백준 1485 자바 - 정사각형 (BOJ 1485 JAVA) [ 문제 보기 ] [ 코드 보기(깃헙) ] [ 틀린 경우 ] 처음엔 아래와 같이 축에 평핸한 정사각형을 찾는줄 알았다. 그래서 예를들어 입력이 1 1 1 1 2 2 1 2 2 와 같다면, 사실 좌측이 x축인지 우측이 x축인지는 안알려줬지만 상관없이 좌측이 2종류고, 우측이 2종류이며 각각 2번씩 나왔고, 좌측의 2종류의 차이와 우측의 2종류의 차이가 동일하다면 정사각형으로 판단하도록 했다. 이 코드는 틀렸다. [ 해설 ] 그렇다면 아래와 같이 정사각형이 기울어 있는 경우까지 찾을 수 있어야 한다. 1. 그래도 딱히 어려울건 없는데, 그냥 4개의 점을 입력받고 나올 수 있는 모든 경우의 길이를 구해본다. 4개에서 2개를 순서없이 골라야하니, 4C2 = 4P2 / 2! = 4*3/2 = 6가지만 구해보면 된.. 2021. 11. 3.
백준 1195 자바 - 킥다운 (BOJ 1195 JAVA) 문제 : https://www.acmicpc.net/problem/1195 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01100/BOJ_1195.java 순전히 구현력에 따라 풀 수 있고 없고가 갈리는 문제이다. 길이가 최대 100이므로 그냥 brute force로 모든 경우를 시뮬레이션 돌려도 전혀 문제가 없다. 1. 일단 최대로 나올 수 있는 경우는 예를들어 모든 부분이 '이'로 되어 있다면 서로 겹칠 수 없으니 두 문자열의 합이 일단 최대치이다. 그 후에, 이런 모양부터 시작해서 하나하나 직접 비교해보는 것이다. 이 때 '이'와 '이'가 만나는 경우는 맞물릴 수 없는 경우이므로 무시한다. ... --(A)-- ... 이런식.. 2021. 11. 2.
백준 1111 자바 - IQ Test (BOJ 1111 JAVA) 문제 : https://www.acmicpc.net/problem/1111 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01100/BOJ_1111.java 쉽게봤더니 생각보다 예외처리할게 많았다. 그래도 이정도면 무난한 편인듯. 'A'와 'B'가 언제 발생할지만 잘 생각해보면 된다. 1. 우선 n이 2 이상일 때 첫번째 수와 두번째 수가 동일한 경우를 생각해봐야 한다. 이게 찾기 제일 어려웠다. [1 1 1 1 ...] 이런 경우이다. 처음엔 2차방정식이 안풀리니 당연히 'A'일꺼라 생각했는데, 2x-1 과 같은 경우 가능하다. 그러니 동일한게 이어진다면 동일한 값을 출력만 해주면 된다. 다만 [1 1 2 ..] 이렇게 갑자기 숫.. 2021. 11. 2.
백준 23334 자바 - Olympic Ranking (BOJ 23334 JAVA) 문제 : https://www.acmicpc.net/problem/23334 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23300/BOJ_23334.java 브론즈 티어지만 자바 한정으로 시간초과 날 위험이 큰 문제라 남겨봅니다. 자바에 시간 어드밴티지 없이 모든 언어 동일하게 1초 제한인 문제입니다. 이 문제의 경우 일반적으로 생각할 수 있는, 입력받은걸 배열에 넣고 정렬하는 방식으로 하게 되면 시간초과가 날 확률이 있습니다. g,s,b가 최대 999이고, g,s,b 순서대로 비교가 되면 되므로 g*1000000 + s*1000 + b 로 처리를 하게되면 최대 10억-1 이므로 int형으로 한방에 표현 가능합니다. 예를들어 g.. 2021. 11. 2.
백준 22728 자바 - Amida, the City of Miracle (BOJ 22728 JAVA) 문제 : https://www.acmicpc.net/problem/22728 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/22700/BOJ_22728.java 일본어로 된 문제라 번역기 돌려야 한다는 점을 빼면 그냥 문제에 제시된 대로 구현만 하면 된다. 내 경우엔 arr[a][b] = c를 a높이에서 b번 수직선에서 c번 수직선으로 넘어갈 수 있다로 정의했다. 따라서 h, p, q를 입력받을 시 arr[h][p] = q, arr[h][q] = p가 된다. 그리고 높이 1001(가로선이 높이 1000부터 있을 수 있으므로)부터 높이를 1씩 감소시키면서 해당 높이에서 이동할 가로선이 있으면 무조건 이동하는 방식으로 짰다. 최종적으로.. 2021. 10. 30.
백준 1004 자바 - 어린 왕자 (BOJ 1004 JAVA) 문제 : https://www.acmicpc.net/problem/1004 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1004.java 사실 문제에 있는 복잡한 그림을 보고 쫄지만 않으면 된다. 그냥 시작지점과 끝지점이 각 원에 포함되는지만 확인하면 된다. 1. 둘다 포함하거나, 둘다 포함안되면 지나갈 필요가 없다. 2. 둘 중 하나만 포함되면 지나가야 한다. 원의 x,y 좌표와 시작점, 끝점의 좌표에 대해 각각 거리를 구해 반지름보다 작다면 포함되니 그걸로 판단하면 된다. 2021. 10. 29.
백준 1003 자바, 파이썬, C# - 피보나치 함수 (BOJ 1003 JAVA, Python, C#) 문제 : https://www.acmicpc.net/problem/1003 코드(자바) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.java 코드(파이썬) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.py 코드 (C#) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.cs Memoization 개념에 대해 익힐 수 있는 아주 좋은 문제이다. 피보나치의 경우 문제에 제시된 기본적인 방식으로 짜게 되면 재귀적으로 호출되는 함수.. 2021. 10. 29.
백준 2696 자바 - 중앙값 구하기 (BOJ 2696 JAVA) 문제 : https://www.acmicpc.net/problem/2696 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02600/BOJ_2696.java 1. 중앙값을 빨리 찾기 위한 방식을 찾아야 한다. 이렇게 중앙값을 취하는 경우 보통 절반씩 나눠서 어떠한 자료구조에 넣는 방식으로 풀면 괜찮은 경우가 많다. 2. 이 문제의 경우 힙 2개에 넣으면 괜찮게 풀 수 있다. PriorityQueue 2개를 둬보자. 하나는 맥스힙, 하나는 민힙으로 사용한다. 예를들어 1,2,3,4,5,6,7,8,9가 맥스힙에 1,2,3,4,5가 들어있고, 6,7,8,9가 민힙에 들어있다고 보자. 맥스힙에서 하나를 peek해보면 가장 큰 수인 '5'가.. 2021. 10. 29.

티스토리툴바