본문 바로가기

PS/BOJ764

백준 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.
백준 2811 자바 - 상범이의 우울 (BOJ 2811 JAVA) 문제 : https://www.acmicpc.net/problem/2811 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02800/BOJ_2811.java 정리하자면 결국 다음과 같다. 1. 연속된 음수 날의 개수(우울 기간)를 센다. 2. 해당 우울 기간 * 2 배 이전부터 꽃을 준다. 3. 그 중 가장 우울 기간이 긴 날들을 살펴보면서, 3배 이전부터 선물을 줬을 때 가장 많은 꽃을 사줘야 하는 경우를 고르면 된다. 그럼 내가 푼 로직은 다음과 같다. 1. 배열로 값들을 입력받는다. 2. 연속된 음수값에 대해 해당 음수값이 시작한 위치에 '우울 기간(T)'을 기입한다. 다음의 경우를 보자. 15 -4 2 5 -1 -3 4 -5.. 2021. 11. 12.
백준 1501 자바 - 영어 읽기 (BOJ 1501 JAVA) 문제 : https://www.acmicpc.net/problem/1501 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01500/BOJ_1501.java 문제 자체는 해싱처리만 알면 풀 수 있는 문제인데, 설명이 너무 불명확하다 ㅡㅡ.. N개의 단어에 포함되지 않는 단어가 포함된 문장은 '0'을 출력해야한다.. 대체 문제 어디에 그 내용이 적혀있는데 ㅠ 뭐 굳이 억지로 찾아보자면 '각각의 단어들이 실제로 존재하는 단어(사전에 존재하는 단어)일 경우에만 의미가 있다.' 부분일 것 같긴하다만.. 1. 첫 문자와 끝 문자는 무조건 같아야 한다. 그 내부의 문자들은 소문자 a~z, 대문자 A~Z로 나눠서 카운팅하면 ababa, aabb.. 2021. 11. 12.
백준 2405 자바 - 세 수, 두 M (BOJ 2405 JAVA) 문제 : https://www.acmicpc.net/problem/2405 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02400/BOJ_2405.java 1. a 2021. 11. 12.
백준 2437 자바 - 저울 (BOJ 2437 JAVA) 문제 : https://www.acmicpc.net/problem/2437 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02400/BOJ_2437.java 일단 brute force(완전탐색)으로는 단순히 생각해봐도 2^1000 이므로 절대 무리다. 처음엔 DP류 일 것 같았는데, 결론적으로 완전 아이디어 하나로 풀리는 문제였다. 내 경우엔 공책에 막 여러 케이스 무지성으로 써보면서 확인해보다가 얻어걸렸다. 일단 '양의 정수 무게 중 최솟값' 이라는 부분에서, 최소값을 찾자마자 출력해야 할꺼라 판단하여 정렬부터 하고 생각했다. 그리고 잘 보면 애초에 '2 3 4 5 6' 이렇게 있어도 1이 없으면 1은 못만든다. 그다음으로 '1 .. 2021. 11. 12.
백준 1010 자바 - 다리 놓기 (BOJ 1010 JAVA) 문제 : https://www.acmicpc.net/problem/1010 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1010.java N=2, M=3인 경우를 보자. 이런식으로 가능하다. 그럼 좌측은 생각하지 말고, 우측 중 선택된 녀석들만 확인해보자. 위와 같다. 즉 선은 생각하지 말고, 어차피 M개 중 N개만 선택하면 되는 문제이다. 이 때 다리가 서로 겹칠 수 있다고 한다면 nPm 이겠지만, 서로 겹칠 수 없다고 했으므로 nCm이 된다. 왜냐하면 겹칠 수 있다면 다음과 같이도 놓을 수 있기 때문이다. nCm = nPm / n! 을 구하면 된다. 예를들어 N = 3, M = 5 라면 nCm = 5*4*3 .. 2021. 11. 11.
백준 5637 자바 - 가장 긴 단어 (BOJ 5637 JAVA) 문제 : https://www.acmicpc.net/problem/5637 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/05600/BOJ_5637.java 생각상으로는 그냥 공백이나 줄바꿈('\n')을 기준으로 나누면 될 것 같지만, '단어는 알파벳(a-z, A-Z)과 하이픈(-)으로만' 라는 기준에 따라 '마침표, 숫자, 심볼, 등등등...' 이라고 써져있는 것도 단어로 취급하면 안된다! 즉, '15-16 November 2012.' 라는 문장의 경우 여기서 단어는 '-', 'November'의 두가지 뿐이다. 따라서 단순히 자바의 StringTokenizer나 split으로 공백을 기준으로 나눠서는 처리할 수 없다. 방법이 두.. 2021. 11. 10.

티스토리툴바