본문 바로가기

분류 전체보기

백준 9095 1, 2, 3 더하기 Java 2019. 6. 11. 2019년 4월에 동적 프로그래밍으로 풀었었던 1, 2, 3 더하기 문제이다. 이 문제를 재귀 호출을 통한 완전 탐색으로 푸는 방법을 정리한 글이다. 동적 프로그래밍으로 푸는 방법을 모른다면 아래의 글을 보도록 하자. https://dundung.tistory.com/9?category=744408 백준 9095 1, 2, 3 더하기 Java dp문제는 문제를 잘 읽어보고 푸는 방식을 빨리 캐치하는 것이 중요한 것 같다.. 나에게는 아직 너무나도 미숙한 능력이다. 이 문제는 마지막에 어떤 수가 올 수 있는지가 중요한 문제 였다. 합을 나타낼 때는 수.. dundung.tistory.com 나는 아직 재귀 함수를 잘 다루지 못한다. 연습을 통해 재귀 함수를 잘 다루려고 노력해야겠다.. 이 문제는 n이 주어..
백준 2251 물통 Java 2019. 6. 10. BFS를 사용한 완전 탐색으로 풀어볼 문제인 물통이다. 문제 설명이 굉장히 간단하다. 왠지 설명이 간단할수록 이해하기 더 힘든 것 같다ㅠ 이 문제를 처음 본 날엔 머리가 안돌아가는 상태였던 건지 글을 쓰는 지금은 이해가 잘되는데 당시에는 문제가 이해가 안 됐었다. 간단하게 설명하자면 입력으로 주어지는 3개의 정수는 각각 A B C 물통의 용량이 주어진 것이고 시작은 A와 B가 비어있고 C에만 가득 찬 상태로 시작한다. 그리고 다른 물통에 물을 부을 때는 한 물통이 비거나, 가득 찰 때까지 부을 수 있다. 몇 리터씩만 부어주고 이런 게 안된다. 그렇게 물을 이리 부었다 저리 부었다 하다가 A가 비어있을 때 C에 있는 물의 양의 경우의 수를 모두 출력해주면 되는 문제이다. 물의 최대 리터는 200이기 때문에..
백준 1946 신입 사원 Java 2019. 6. 10. 문제를 이해하는 것부터 나에겐 시간이 걸렸고 구현하는 데에도 여러 번의 시행착오를 겪었던 그리디 문제인 신입 사원이다. 흔히들 말하는 맞았는데 왜 틀리지.가 자동으로 연발됐던 문제였다. 문제를 간단하게 요약하면 지원자가 전부 한자리에 모여있을 때 누군가가 나보다 면접 순위, 서류 둘 다 높으면 절대 붙을 수 없다. 둘 중 하나의 순위라도 다른 지원자들 보다 높아야 한다는 것이다. 입력받는 게 순위, 등수가 아니라 점수인 줄 알아서 헷갈렸고 순위인 것을 알아채고도 헷갈렸었다. 예제 5 3 2 1 4 4 1 2 3 5 5 에서 3 2의 경우를 보면 1 4 보다 면접 순위가 2 < 4로 낮고 4 1 보다 서류 순위가 3 < 4로 낮고 2 3 보다 면접 순위가 2 < 3으로 낮고 5 5 보다는 둘 다 높다. 그..
백준 1120 문자열 Java 2019. 6. 10. 그리디 문제를 순차적으로 풀다 만난 문자열 문제이다. 알고리즘 분류를 보면 여러 가지 푸는 방법이 있다는 걸 알 수 있는데. 그리디에서 만났기 때문에 그리디스럽게? 풀어보려고 노력했다. 처음엔 앞에서부터 비교해보고, 뒤에서부터 비교해보고 더 적게 차이 나는 것에 A문자열의 앞부분이나 뒷부분을 붙이는 방법으로 풀어보려고 했는데 아무리해봐도 실패했다. 결론적으로 이 문제는 B문자열을 하나씩 A문자열만큼 돌면서 A문자열과의 차이가 가장 적을 때 그 차이를 출력하면 되는 문제이다. A = aaa B = bbaaabb 일 때 i = 0 -> aaa, bba -> 2 i = 1 -> aaa, baa -> 1 i = 2 -> aaa, aaa -> 0 . . . 이런 식으로 A문자열과 B의 부분 문자열 가장 차이가 적..
백준 1525 퍼즐 Java 2019. 6. 9. BFS를 이용한 완전 탐색을 통해 풀 수 있는 퍼즐 문제이다. 이 문제는 다른 BFS문제와는 다르게 0의 위치만 예제와 맞게 구현하면 안 되고 1부터 8까지의 수의 위치도 맞아야 하기 때문에 까다롭다. 먼저 편하게 풀기 위해 입력받은 값에서 초기 값인 1 2 3 4 5 6 7 8 0 으로 이동하는 문제로 바꿔서 풀고 2차원 배열은 까다롭기 때문에 1차원 배열로 바꾸어서 풀고 Map인터페이스를 이용해서 이동한 횟수를 저장하면서 풀어야 한다. 첫 번째 예제의 값 1 0 3 4 2 5 7 8 6 을 예로 보면 1 0 3 4 2 5 7 8 6으로 바꾼다. 그리고 0 대신에 9를 넣어준다. 1 9 3 4 2 5 7 8 6 이 1차원 배열을 1 2 3 4 5 6 7 8 9로 바꾸는 데 걸린 최소 횟수를 출력하면 되..
백준 9019 DSLR Java 2019. 6. 8. 완전 탐색으로 가능한 문제인 DSLR 문제이다. 정답률은 난이도에 비해 많이 낮은 것 같은 21%이다. 쉽다는 말은 아니다.. 이 문제는 n과 m이 주어졌을 때 n에서 m으로 가는 최소한의 명령어를 출력하면 된다. 최소한의 명령어이고 가중치가 따로 없고 크기도 그렇게 크지 않으므로 BFS탐색으로 정말 탐색하면 풀 수 있는 문제이다. 처음엔 시간 초과가 나왔었는데 L과 R 명령어를 처리할 때 문자열로 처리해서 시간 초과가 나왔던 것 같다. 뭔가 저런 자릿수를 바꾸는 구현은 문자열로 하는 습관이 있는데 고쳐야겠다. 이 문제를 내가 헤맨이유는 명령어를 똑바로 구현하지 못했기 때문이다. 꼭 명령어를 천천히 읽어보고 구현해야 할 것 같다. 내가 잘못 이해했던 부분은 S: S는 n에서 1을 뺀 결과 n-1을 레지스..
백준 1963 소수 경로 Java 2019. 6. 8. 완전 탐색 문제인 소수 경로이다. 간선의 가중치가 없고 최소 회수를 구하는 문제이고 4자리의 소수들만 탐색해보면 되므로 2초는 넉넉하다. 그러므로 BFS를 사용한 완전 탐색으로 풀면 되는 문제이다. 자주 까먹는 에라토스테네스의 체를 다시 한 번 복습해 볼 수 있어서 좋은 문제였다. 소수를 한 단계씩 바꾸는 모든 경우를 어떻게 구해야하는지 헤맸는데 그냥 4자리 중에 한자리씩 0~9까지 다 바꿔보면서 그 수가 소수이면 큐에 넣어서 BFS탐색을 하면 됐었다. 수를 바꿔넣을 땐 Stringbuilder의 메소드인 setCharAt(인덱스, 바꿀 문자)를 사용했다. StringBuilder에 유용한 메소드가 생각보다 참 많은 것 같다. 어려워보이면서도 간단한 문제이다. 다른 BFS탐색 문제랑 똑같이 구현하면 된다..
완전 탐색(exhaustive - search)의 종류 2019. 6. 7. 완전 탐색은 말 그대로 가능한 모든 경우를 다해보는 탐색 방법이다. 이러한 완전 탐색을 하는 방법은 대략 5가지가 있다. 1. brute force -N중 for문으로 푸는 방법 2. 순열 3. BFS -BFS는 O(정점 개수) 이기 때문에 N제한이 1초안에 가능할 경우 -최소를 구하는 문제 -간선의 가중치가 1일 때 4. 비트마스크 5. 백트래킹 완전탐색은 코딩테스트에서 자주 나오는 유형인 만큼 5가지 방법 모두 잘 다룰 수 있도록 공부해야 겠다.

티스토리툴바