be programmer

https://www.acmicpc.net/problem/16947 전형적인 탐색 문제이다.문제를 읽어보면 사이클을 dfs, 재귀 등 방법으로 찾고, 사이클로부터 파생되는 지선의 깊이를 구해서 출력하면 된다.나는 사이클을 dfs로 찾고, 지선의 깊이를 bfs로 찾았다. 사이클을 찾을땐 재귀로 찾는게 편하다 생각했다. 왜냐하면 나한테 익숙했고, 처음 지점을 기억하고 계속 재귀하기에 사이클의 시작점?을 찾는덴 dfs가 가장 적합하다고 여겼기 때문이다. 사이클을 찾으면 true를 반환하여 탐색을 그만 둔다. 아닐 경우 탐색을 해야하기에 사이클 탐색 배열에 false를 준다. 이외 사이클에서 파생된 지선의 깊이는 bfs로 찾았다. 사이클 찾기public static boolean dfs(int prev, int..

https://www.acmicpc.net/problem/2469 구현 문제이다. 구현 문제를 좋아하지는 않는데 왜냐하면 실제 구현해서 굴러가는 프로그램들 마냥 예외처리를 해야하는 부분이 있고, 무턱대고 구현하기보다는 면밀히 생각해야 하는 부분이 존재하기 때문이다. 문제에 나름 친절히 설명된 사다리 타기의 성질을 이용하여 -가 뜰 경우 swap(차피 하나씩 하나, 여러개 하나 반댓쪽으로 이동되는건 똑같으니), *가 떴을경우 keep going 하면 됨이것을 시작지점, 도착지점에서 시행해서 ?가 뜨는지점에서 만난 후 문자열 비교를 해주면 됨.나는 막판 예외처리하고 swap 해줘야하는걸 생각 못해서 한번만에 맞추지는 못했는데, 그렇게 해야함. swap 안하면 ?지역에서는 -가 있어야 하는 지역임에도 사다리타..

https://www.acmicpc.net/problem/9921 영어 해석 이슈로 베낭 문제로 오인하여 풀었다. 전형적인 동전 DP 문제였고, BFS + DP로도 해결 할수도 있다고 한다. 최소의 가짓수를 사용하여 해당 가치를 만들수 있는지를 판별해주고, 된다면 최소의 가짓수를 출력해내면 된다.BFS로도 풀어보겠다. 필자는 베낭문제인줄 알고 헛짓 하느라 금방 푸는걸 1시간이나 넘게 걸려 풀었다. 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inp..

https://www.acmicpc.net/problem/11085 UnionFind(분리 집합) 문제이다. 사실 선지만 가지고는 이 문제가 정확히 뭘 말하고 싶은지 이해하기 어려워서 선지 보는데 문제 풀기로 정해둔 시간을 모두 다 날렸다.첫 줄에 Baekjoon World의 국왕이 정한 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 출력합니다. 부분이 이해가 안 가는 부분이었는데, 그냥 정렬 해 둔 후 그에 맞는것을 찾으면 되는 것이었고 실제로 그렇게 풀었다.간선을 w순으로 우선 순위 큐를 통해 정렬하고 w가 큰 간선부터, 시작과 끝점의 find가 같지 않다면 union 연산을 한다. 종료조건은 find(C) == find(V)이다. 가장 최근 연결했던 간선의 w를 출력해서 풀었다.큐를 정렬하는..

적어도 다른 이 보다 서류 점수 혹은 면접 점수가 떨어지지 않는 사람을 뽑는 문제이다.먼저 서류지원자 순위를 역정렬하고, 가장 떨어지는 서류 순위자의 면접 순위를 가지고 이것 보다 순위가 높으면 합산하고 그것으로 카운트하는 그리디 문제였다. 코드import java.util.*;import java.io.*;public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamW..

https://www.acmicpc.net/problem/11057 DP 문제이다. 쉬운 계단 수(https://www.acmicpc.net/problem/10844)를 이전에 풀어본적이 있었고, 이 문제 풀이 경험에서 답을 찾을 수 있었다.  풀이 방법은 간략하게 이미지와 같다.이미지는 다른 블로그에서 퍼왔다.숫자가 한자리일 경우 한자리만 있으므로 오롯이 하나만 설정해두면 된다.한자리 이상이 있을때는 다음과 같다. 두자리일 경우 첫째 자리가 0일 경우 00, 01, 02..., 09 10개, 1일 경우 11, 12, 13...., 19 9개, .. 9일경우 99로 1개 총 55개 나온다.세자리일 경우 첫째자리가 0이면 001, 002,... , 099 55개, 1이면 45개 .. 9면 1개이다.그러면 ..

https://www.acmicpc.net/problem/14442벽 부수고 이동하기 시리즈의 두번째 문제이다.1은 1학년때 말기에 풀었기에 4년이 넘게 지난 지금, 아무런 기억이 나지 않아서 고민을 여러번 한 문제이다.나는 기존 풀이를 참고하여 벽 뚫을 수 있는 횟수를 계산하는 배열을 추가했다. 벽을 부술수 없는 상태일 경우 더이상 벽을 부술수 없게 하는 장치가 필요했기 때문이다.  어떤 칸에 도달했을 때 나는 벽을 부술 수 있을 수도 있고, 그렇지 않을수도 있기 때문이다. 큐에 현재만의 최적 상태를 넣는다고 해서, 완전 최적상태를 찾을수 있음을 단언할 수 없다.  핵심 로직은 다음과 같다. 잘 알고있듯 큐에 좌표와 거리, 브레이크 카운터를 저장하고, 브레이크 카운터가 차기 전까지는 벽을 부수고 이동할..

https://www.acmicpc.net/problem/15993 dp 문제이다. 처음에 문제를 읽지 않고 코인 수 구하기와 비슷한 걸로 오해를 했으나, 완벽히 다른 문제임을 깨달았다.홀수개의 i-1을 사용한 수, i-2를 사용한 수, i-3을 사용한 수에서 숫자 하나를 더하면 짝수가 되고, 짝수개의 i-1,i-2,i-3을 사용한 수에서 숫자 하나를 더하면 홀수가 된다. 짝수개와 홀수개를 나눠서 풀었다. 소스코드import java.util.*;import java.io.*;public class Main6 { static int mod = 1000000009; public static void main(String[] args) throws IOException { Buffer..