본문 바로가기

백준749

백준 21187 자바 - Pulling Their Weight (BOJ 21187 JAVA) 문제 : https://www.acmicpc.net/problem/21187 뭔가 복잡해보이는데, 좀 정리해보면 그냥 brute force로 해결 가능한 문제이다. 1 최대 10^5개의 동물의 무게가 주어진다. 그리고 각 무게는 2만 이하이므로, 전부 더해도 20억 이하로 Integer로 표현 가능한 수치이다. 2 사실 동물이 몇마리가 주어지든 상관없고 중요한 데이터는 결국 '1~20,000 사이의 각 무게를 가진 동물이 각 몇마리씩 존재하는지' 이다. 3 정렬이 필요할것같이 생겼지만, 사실 무게가 2만 이하라서 배열에 카운팅한다면 정렬은 따로 필요 없다. 다음의 입력을 보자. 6 5 7 5 5 3 4 위 입력을 배열로 카운팅해보면 다음과 같다. 4 그럼 이제 index 기준으로 1부터 20000까지를 .. 2021. 11. 22.
백준 2912 자바 - 백설공주와 난쟁이 (BOJ 2912 JAVA) 문제 : https://www.acmicpc.net/problem/2912 1. 기본적인 아이디어는 각 쿼리의 [a, b] 구간에 대해 매번 [a, b] 전체를 확인하지 않고, 이전에 확인했던 구간과 겹치는 구간은 제외하고 확인하는 것이다. 예를들어 이전에 확인했던 구간이 [1, 100]이고 이번에 확인할 구간이 [4, 95]라고 해보자. 이 때, [1, 100] 구간을 전부 확인하면 100번 + [4, 95] 구간을 전부 확인하면 92번 봐야 한다. 그럼 192번 동작해야 한다. 하지만 [1, 100] 구간의 결과에서 [1, 3] 구간을 빼고, [96, 100] 구간을 빼면 [4, 95] 구간 전체를 본 것과 동일한 결과를 얻을 수 있다. 이 경우 108번만 동작하면 된다. 2. update가 없는 쿼.. 2021. 11. 20.
백준 14897 자바 - 서로 다른 수와 쿼리 1 (BOJ 14897 JAVA) 문제 : https://www.acmicpc.net/problem/14897 확실히 나한테 아직 플래수준은 어려운것같다. 아예 모르는 알고리즘 지식을 요구하는 문제가 아닌이상 꾸역꾸역 풀긴 하는 편인데 사실 이런게 CP에서 나왔다고 치면 시간내에 절대 못푼다. 못해도 1시간 이상은 걸리는 것 같다. 오답률도 높은편 ㅠ 뭐 꾸준히 하다보면 언젠가 플래수준도 쉽게 풀겠지! 생각 과정 풀이만 보려면 아래로 쭉 내려서 '풀이 정리'로 바로 가시면 됩니다. 1. 우선 문제에서 바로바로 생각나는걸 정리했다. - 업데이트가 없는 쿼리 이므로, 쿼리 순서를 마음대로 처리해도 된다. (오프라인 쿼리) - N이 최대 100만, 배열에 포함된 수는 최대 10억이다. 이 때, 문제에서 묻는건 서로 다른 수의 개수이므로 배열에.. 2021. 11. 19.
백준 10542 자바 - 마피아 게임 (BOJ 10542 JAVA) 문제 : https://www.acmicpc.net/problem/10542 오랜만에 엄청 재밌는 문제였다. 그다지 복잡한 알고리즘적 지식을 요구하지 않으면서도 이렇게 난이도도 어느정도 있으면서 재밌게 낸것도 모자라서, 심지어 예제 입력들도 풀이를 생각하기 편하게 잘 내줬다. 출제자 멋져 AD-HOC 문제로, 딱 이거다! 하는 해법 없이 논리적으로 맞다고 생각하는 방식들을 찾아 적용하며 풀어야 하는 문제이다. 일단 풀이과정은 한가지 확실한 조건(이하 '1'이 이에 해당함)에서 시작하면 판정을 위한 다른 방식들로 생각을 이어갈 수 있다. 1. 문제에서 제시된 '마피아끼리는 서로 누군지 아는 상황이기 때문에 서로 지목을 안 하려고 할 것이다.'에 따라, 일단 맨 처음에 들어온 입력에서 한 번이라도 지목을 당.. 2021. 11. 18.
백준 16509 자바 - 장군 (BOJ 16509 JAVA) 문제 : https://www.acmicpc.net/problem/16509 기본 BFS 문제다(구현이 상당히 귀찮은). 좀 덜 귀찮으려면 다음과 같이 하면 된다. 1. BFS 이동 위치를 문제에서 제시된 이동 위치 끝 지점만으로 한다. (코드의 dr, dc) 2. 이동하면서 장군에 걸리는 지점의 경우 이동이 불가하므로, 이 부분에 대한 체크 중 첫번째로 '상'의 상하좌우에 위치한 부분을 체크한다. (코드의 'switch (d)' 부분) 3. 다음으로 나머지 이동구간에 있는 지점들은, '1'에서 지정한 위치에서 대각선으로 한칸 이동한 위치이다. (코드의 'if (cr+dr[d]+(dr[d] 2021. 11. 18.
백준 17394 자바 - 핑거 스냅 (BOJ 17394 JAVA) 문제 : https://www.acmicpc.net/problem/17394 일단 A와 B 사이의 소수라는 조건이 없다고 생각해보자. 이 경우 1차원 좌표평면 상에서 시작점으로 부터 1. 현재위치/2 2. 현재위치/3 3. 현재위치-1 4. 현재위치+1 으로 이동하는 BFS 문제라 볼 수 있다. 그럼 이제 A, B 사이의 소수를 도착점으로 하는 방법만 찾으면 된다. B의 최대값은 100000이므로, 100000까지의 모든 소수만 찾으면 된다. 이 때, 당연하게도 매번 소수판정을 하면 시간초과가 날 것이다. 그러니 TC들 진행하기 이전에, 100000까지의 모든 소수를 찾아두면 된다. 이 경우 에라토스테네스의 체 방식으로 구해두면 편하게 소수를 구할 수 있다. 이 때 100000의 square root 까.. 2021. 11. 17.
백준 10282 자바 - 해킹 (BOJ 10282 JAVA) 문제 : https://www.acmicpc.net/problem/10282 가중치가 있는 방향 그래프에서 한점에서 시작해, 다른 모든 정점으로의 최단거리를 찾는 문제이다. 출력해야 하는 '총 감염되는 컴퓨터 수'는 최단거리가 무한대가 아닌 경우 즉 도달할 수 있다면 감염되는 컴퓨터이다. '마지막 컴퓨터가 감염되기까지 걸리는 시간'은 모든 정점으로의 최단거리 중 최대치를 출력하면 된다. 가중치가 있으므로 일단 BFS는 사용할 수 없고, DFS로는 시간초과를 피할 수 없다. Floyd-Warshall로는 O(100*10000^3) 이므로 역시 시간내에 통과할 수 없다. 쉽게 생각할 수 있는 이 문제에 딱 맞는 알고리즘은 다익스트라(dijkstra)이다. 시간복잡도는 대략 O(ElogV) 정도로 잡는다. -.. 2021. 11. 16.
백준 20310 자바 - 타노스 (BOJ 20310 JAVA) 문제 : https://www.acmicpc.net/problem/20310 사전순으로 가장 빠른 것이 되려면 결국 최대한 0이 앞쪽으로 와야하고, 최대한 1이 뒤쪽으로 가야한다. 그래서 생각보다 간단하게 풀 수 있는데, 단순히 1은 앞에서부터 지우고, 0은 뒤에서부터 지우면 된다. 다음과 같은 경우를 보자. 1은 4개이므로 2개를 지워야 한다. 0은 2개이므로 1개를 지워야 한다. 로직은 다음과 같다. 1. 편히 풀기위해 문자열을 character 배열 형태로 변경한다. 2. '1'이 들어있는 부분만 보면서, 지워야 하는 개수만큼 앞에서부터 순서대로 지운다. (따라서 이 풀이는 그리디!) 3. '0'이 들어있는 부분만 보면서, 지워야 하는 개수만큼 뒤에서부터 순서대로지운다. --- 코드 : https:.. 2021. 11. 14.
백준 3273 자바 - 두 수의 합 (BOJ 3273 JAVA) 문제 : https://www.acmicpc.net/problem/3273 보통 풀고보면 풀이 방법이 비슷비슷한 경우가 많은데, 아무래도 입력값 n이 10만개 밖에 안되다보니 재밌게도 풀이방법이 매우 다양한 문제이다. 일단, 단순히 2중 반복문으로 모든 쌍을 더해보면 O(N^2)이므로 시간초과다. 그럼 그 외에 시간 내에 가능한 풀이법에 대해 보자. 일반적으로 사람들이 많이 사용한 풀이 방법은 2가지 정도 있었다. 1. 정렬 후, 모든 값을 확인하며 x-a_i가 존재하는지 이분탐색으로 확인 : 정렬 O(NlogN) + N개에 대한 이분탐색 O(NlogN) 2. 정렬 후, 투 포인터 알고리즘으로 맨앞과 맨뒤에서 시작한 포인터를 움직이며 더해봄 : 정렬 O(NlogN) + 탐색 O(N) --- 내 경우엔 b.. 2021. 11. 13.
백준 9421 자바 - 소수상근수 (BOJ 9421 JAVA) 문제 : https://www.acmicpc.net/problem/9421 일단 이 문제를 풀기 위해 필요한 부분을 살펴보자. 1. 1000000이하의 모든 소수를 알 수 있어야 한다. -> 소수판정의 경우 간단히 에라토스테네스의 체를 사용해서 100만 이하의 모든 수에 대해 미리 소수를 구해두면 된다. 2. 상근수를 구할 수 있어야 한다. 이 때 '1'이 아예 안나오는 경우가 존재하므로 무한루프로 빠지지 않도록 하는 로직이 필요하다. -> 1이 나오거나, 이미 나왔던 수가 다시 나올 때 까지(순환) '각 자리수의 제곱의 합'을 구해준다. 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/09400/BOJ_9421.java import.. 2021. 11. 13.

티스토리툴바