밤이 블로그

BOJ#1182 부분집합의 합 * 문제https://www.acmicpc.net/problem/1182 * 풀이처음에는 조합을 이용해서 풀었습니다. (160ms)집합에서 1개를 고르는 경우, 2개를 고르는 경우, ...., N개를 고르는 경우 두번째 풀때는 집합의 각 원소의 2가지 경우에 대해(고르는 경우, 고르지 않는 경우)재귀 함수 호출로 답을 구하였습니다. (76ms) 주의할 점 : S가 0인 경우에는 공집합도 카운트 될 수 있음 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%231182_SumOfSubsets/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BO..

BOJ#9376 탈옥 * 문제https://www.acmicpc.net/problem/9376ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2013 J번 * 풀이어려운 문제라고 생각합니다. 일단 맵을 상하좌우로 1칸씩 늘려줍니다. -> 이유 : 시도1 처럼 여러 시작점들을 어딘가에 저장해놓고 조사하는 것과, 외곽의 어느 한점을 시작점으로 잡고 조사하는 것은 차이가 없다.(문이 아니라면 cost가 없기 때문) 죄수 2명을 탈옥시키는 방법은 3가지가 있습니다. 1) 죄수 1이 죄수2를 데리고 바깥으로 나가는 경우 2) 죄수2가 죄수1을 데리고 바..

BOJ#2468 안전 영역 * 문제https://www.acmicpc.net/problem/2468 * 풀이 비가 내리는 양을 증가시키면서 BFS 또는 DFS를 수행하면 됩니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%232468_SafetyZone/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; /** * BOJ#2468 안전영역 * https:..

BOJ#12851 숨바꼭질 2 * 문제https://www.acmicpc.net/problem/12851 * 풀이 쉬운 문제인데 푸는데 고생을 좀 했습니다. 일단은 1697 숨바꼭질 문제와 동일한데..동생을 찾는 가장 빠른 시간을 출력하는 것과가장 빠른 시간으로 찾는 방법의 개수까지 출력해야 합니다. 헷갈리지 말아야 할 것은 가장 빠른 시간으로 찾는 '경로'가 아니라 '방법'의 개수 입니다. 즉, 입력 데이터가 1 10일 때가장 빠른 경로는 1 -> 2 -> 4 -> 5 -> 10 이지만방법으로 따지면 아래와 같이 2가지가 있습니다.1 -> 2(+1) -> 4(*2) -> 5(+1) -> 10(*2)1 -> 2(*2) -> 4(*2) -> 5(+1) -> 10(*2) 따라서 방법의 개수를 구하려면 큐에 ..

BOJ#1707 이분 그래프 * 문제https://www.acmicpc.net/problem/1707 * 풀이 그래프 관련 기본 문제입니다. 저는 BFS/DFS로 풀었는데, 주의할 점으로 연결 그래프와 비연결 그래프를 둘 다 고려해주어야 합니다, * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231707_BipartiteGraph/src/Main.java (BFS)import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /** * BOJ#1707 이분 그래프 * https://www.acmicpc.net/p..

BOJ#1865 웜홀 * 문제https://www.acmicpc.net/problem/1865 * 풀이 벨만-포드 알고리즘을 활용하는 기본 문제입니다. 일단 기본적인 풀이 방법은 "BOJ#11657 타임머신" 문제와 같고,음수 간선 사이클이 존재하는지 확인만 하면 되는 문제입니다. 주의할 점 #1)도로에 방향이 없으므로,도로 정보를 입력 받을 때 양방향으로 생각해야 한다는 점입니다. -> 결국 Edge의 개수는 2 * M + W -> 코드 상 여러번 쓰이게 되므로, 실수하지 않게 따로 변수로 저장해둡시다. 주의할 점 #2)시작점이 주어지지 않았으므로, 시작점을 어느 곳으로 해야 할 지 결정해야 합니다. 음수 사이클은 웜홀이 연결된 지점에서만 존재 할 수 있으므로웜홀의 목적지들을 배열에 따로 저장하여, 이..

BOJ#11657 타임머신 * 문제https://www.acmicpc.net/problem/11657 * 풀이벨만-포드 알고리즘 문제입니다. → http://stack07142.tistory.com/79 알고리즘 설명은 위 링크를 참고하시면 됩니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#11657 타임머신 * https://www.acmicpc.net/problem/11657 */ public class Main { static final int NONE = -1; static final int IN..

BOJ#13422 도둑 * 문제https://www.acmicpc.net/problem/13422 * 풀이 푸는건 어렵지 않지만 시간 제한에 신경을 써서 구현해야 합니다. → O(nm)으로 구현 시 시간초과, 따라서 O(n)으로 해결을 해야 합니다. 시간 초과, 코드 길이, 푸는 속도 등에 초점을 맞춰 풀어보시면 좋을 것 같습니다. 풀이의 요점은 이전 Iteration에서 사용했던 sum에서 필요없는 값은 빼고, 더할 값만 더해서불필요한 연산을 하지 않는 것입니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%2313422_Theif