본문 바로가기

PS/BOJ752

백준 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.
자바 6137 자바 - 문자열 생성 (BOJ 6137 JAVA) 문제 : https://www.acmicpc.net/problem/6137 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/06100/BOJ_6137.java 문제에 제시된 '예제 입력 1'을 기준으로 그림을 그려보면 다음과 같다. 위와 같이 문자열이 있고, head가 앞쪽 tail이 뒤쪽을 가르키는 포인터라 생각하면 된다. 그리고 head는 우측으로, tail은 좌측으로 진행하면서 사전순으로 더 작은 character를 선택하면 된다. (A 2021. 10. 29.
백준 3409 자바 - 문자 방정식 (BOJ 3409 JAVA) 문제 : https://www.acmicpc.net/problem/3409 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/03400/BOJ_3409.java 첫 다이아 티어 성공한 문제이다. 사실 골드나 플래도 제대로 못풀다보니 다이아급은 쳐다도 안봤었는데 얼마나 어려운지 볼려고 도전해봤다(보통 티어랑 알고리즘 분류는 끄고푸는데, 문제 검색을 실버, 골드, 플래 전체 체크하고 순서 랜덤으로 두고 검색해서 푸는 편임). 결과는 의외로 쉬웠다. 안쫄고 이제 다야도 한번 덤벼봐야겠다. 풀고보니 다른 분들은 DP(다이나믹 프로그래밍)으로 다들 분류를 설정해뒀던데 내 경우엔 그냥 dfs로 풀었다. 이 문제의 경우 문제만 놓고 보면 복잡해보일.. 2021. 10. 28.
백준 1575 자바 - 졸업 (BOJ 1575 JAVA) 문제 : https://www.acmicpc.net/problem/1575 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01500/BOJ_1575.java 생각해야 할 부분이 많은 까다로운 문제였다. 그래도 1시간정도 걸렸으니 그저께 8시간 걸려 풀었던 문제 보다는 훨씬 나았다. 플래도 가끔씩 풀어지긴 하는데, 아직 내 실력으론 풀어도 보통 1시간 이상은 기본으로 걸리는 것 같다. 나중에 한 번 틀리고 나서 본건데, 6개월 전부터 '맞았습니다'가 하나도 없는 문제였다. 미리 채점 현황을 봤다면 아예 시도를 안해봤을수도 있을듯 ㄷㄷ 처음에 틀리고 나서는 나도 저 중에 하나가 되겠거니 했는데, 자기 전에 맞아서 꿀잠 잘 것 같다. 0.. 2021. 10. 26.
백준 16499 자바 - 동일한 단어 그룹화하기 (BOJ 16499 JAVA) 문제 : https://www.acmicpc.net/problem/16499 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/16400/BOJ_16499.java 만약 N개의 문자열에 대해 알파벳 순서까지 모두 같아야 한다고 하자. 그럼 단순히 HashSet에 입력받은 단어를 넣어보면 알아서 중복값이 제거되니, 해시셋의 크기가 답이 된다. 그럼 순서만 달라야 하는 경우는 어떻게 해야 할까? 여기서 서로의 동일성을 판별할 수 있는 기준은, N개의 단어에 대해 각각 '알파벳 소문자가 몇 번씩 나왔는지' 이다. 알파벳 소문자는 총 26개 이므로, 26칸짜리 배열을 만들어 두고, 입력 받은 각 문자열에 대해 각 character를 보면서 각.. 2021. 10. 26.
백준 14881 자바 - 물통 문제 (BOJ 14881 JAVA) 문제 : https://www.acmicpc.net/problem/14881 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/14800/BOJ_14881.java 처음엔 별 생각없이 brute force 정도로 생각했는데, 시간복잡도가 아닌 것 같아 다른 방법을 찾아봤다. 결론은 최대공약수 문제이다. 일단 되는 경우와 안되는 경우에 대해 생각해보자. 1. 일단 c가 a와 b 둘 모두보다 크다면 아예 불가능하다. (코드의 max>=c) 2. c가 a나 b와 동일하다면 당연히 가능하다. (코드의 a==c || b==c) 3. 다음으로 a,b의 최대공약수가 c의 공약수라면 가능하다. (코드의 c%gcd==0) 4. 마지막으로 a와 b가 서.. 2021. 10. 25.

티스토리툴바