Algorithm/BaekJoon

[JAVA] 백준 1261 : 알고스팟

문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 해결 방법 다익스트라 알고리즘을 사용해서 풀어야 합니다. 다익스트라 알고리즘은 A에서 B로 가는 것의 최단 거리를 구할 때 주로 사용합니다. 이 문제에서는 시작 지점과 끝 지점이 지정되어있고, 구해야 하는 벽을 부순 횟수가 음수로 존재하지 않기 때문에 사용이 가능합니다. 코드는 다익스트라 알고리즘을 그대로 구현한 것이라 따로 설명하진 않겠습니다. 아래 링크의 분이 잘 설명해두셔서 참조 남깁니다. [알고리즘/자바] 다익스트라 알고리즘 (..

[JAVA] 백준 2933 : 미네랄, 18500 : 미네랄2

문제 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 미네랄 2도 같은 코드로 해결 가능. 해결 방법 범위는 크지 않아서 문제에서 주어진대로 구현만 하면 된다. 처음에 문제가 이해가 잘 되지 않아서 내가 이해한 것을 바탕으로 최대한 풀어서 설명하려고 한다. 일단 문제에서 얘기하는 클러스터는..

[JAVA] 백준 2776 : 암기왕

문제 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 해결 방법 해시쪽을 복습하면서 관련된 문제들을 보고 있는데 이 문제와 같은 경우는 굳이 HashMap을 사용하지 않고, HashSet을 이용해서 값을 넣어둔 뒤에 그 값이 있는지 없는지만 체크하면 될 것 같아 아래와 같이 코드를 짜보았다. 처음에 주어진 값을 diary라는 HashSet에 넣어둔 뒤에 contains를 이용해서 비교한 뒤 있으면 1, 없으면 0을 StringBuilder에 저장해 놓은 뒤에 출력하는 방식이다. 코드 import java.io.Bu..

[JAVA] 백준 1620 : 나는야 포켓몬 마스터 이다솜

문제 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 해결 방법 기본적인 HashMap 사용 문제이다. HashMap에 대해 공부할겸 관련된 문제를 풀면서 정리를 해두려고 한다. HashMap은 Key, Value 로 이루어져 있는데 문제에서는 포켓몬 이름을 순서대로 입력 받은 다음 숫자를 주면 해당되는 순서에 있는 포켓몬 이름을 출력하고, 포켓몬 이름을 주면 몇 번째 순서에 있는지 출력해야한다. 그래서 두 가지 경우를 다 대응할 수 있게끔 포켓몬 이름이 Key인 HashMap과 ..

[JAVA] 백준 14267 : 회사 문화 1

문제 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 해결 방법 생각보다 까다로웠던 문제였다. 이 문제에서 주의 깊게 봐야 하는 것은 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이라는 것. 처음엔 인접리스트를 구현한 후에 칭찬을 받은 번호부터 칭찬의 수치를 dfs로 탐색하며 업데이트하는 방법을 사용했다. 다음 탐색할 곳을 찾는 것은 단순히 현재 탐색하는 곳보다 숫자가 크면 탐색하는 조건문을 사용했다. 하지만 최초 칭찬의 횟수만큼 계속 탐색을 진행하게 되어 시간 초과가 발생해서 다른 방법..