본문 바로가기

Algorithm

백준 3111 검열 Java 2019. 7. 11. 스택을 활용해서 풀어야 하는 문제인 검열이다. 총 23번의 시도 끝에 성공할 만큼 고생을 많이 한 문제였다. 이 문제에서 고생하는 이유는 대부분 출력 초과, 시간 초과였는데 나는 메모리 초과 때문에 고생을 많이 했다. 텍스트의 최대길이가 300,000이기 때문에 스택을 활용하지 않고 일일이 검사하는 방법은 O(n^2)으로 당연히 시간 초과이다. 출력 초과는 내 생각에 그냥 틀렸다는 말과 똑같은 것 같다. 우선 문제를 푸는 방법을 설명하면 1. 왼쪽 스택, 오른쪽 스택 총 2개의 스택을 만든다. 2. 왼쪽에서부터 텍스트를 훑으면서 왼쪽 스택에 넣고 key값을 발견하면 왼쪽 스택에서 지운다. 3. 오른쪽에서부터 텍스트를 훑으면서 오른쪽 스택에 넣고 key값을 발견하면 오른쪽 스택에서 지운다. 4. 텍스트를 ..
백준 9935 문자열 폭발 Java 2019. 7. 10. 스택을 활용해서 풀어야 하는 문자열 폭발 문제이다. 정답률은 19%로 낮은 편이다. 문자열 A, B를 입력받고 A에서 B를 없애고 새로 만들어진 문자에서도 B를 없애고 계속해서 B를 없애면 되는 간단한 문제이다. 하지만 N제한은 백만으로 문자열이 새로 생길 때마다 검사하는 방법인 O(N^2)의 방식으로 푼다면 반드시 시간 초과가 나오게 된다. 시간 초과를 피하기 위해 스택을 사용하면 되는 문제이다. 스택을 사용하게 되면 O(N)만에 구현할 수 있다. 하지만 스택을 사용하면 된다라는 것을 눈치채도 구현하기 쉽지 않은 문제이다.. 문제를 푸는 법은 1. 임의의 클래스에 A문자열의 위치, B문자열의 위치를 표시할 int형 변수 두 개를 필드로 만들어서 스택을 생성한다. 2. B문자열의 길이만큼의 boolean..
백준 5582 공통 부분 문자열 & 9251 LCS & 9252 LCS 2 Java 2019. 6. 28. 세 문제 전부 유사한 문제이다. LCS(최장 공통부분 수열) 알고리즘을 사용한 문제이다. 다만 공통 부분 문자열 문제와 LCS문제의 차이점은 공통부분 문자열은 문자열이 연속적이여야하고 LCS 문제들은 연속적이지 않아도 된다. LCS2 문제는 최장 공통부분 수열을 출력까지 하는 문제이다. LCS 알고리즘은 LIS(최장 증가 부분 수열) 알고리즘과 유사하다. 먼저 공통부분 문자열 문제는 연속적이어야 하므로 문자열이 같을 때 LCS[i-1][j-1]에서 +1을 한 값을 저장하면 된다. 문자열이 같은 것이 여러 번 나올 수 있으므로 2중 for문으로 하나씩 찾아봐야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java.util.S..
백준 1700 멀티탭 스케줄링 Java 2019. 6. 27. 그리디 문제인 멀티탭 스케줄링이다. 정답률은 25퍼센트로 꽤 낮다. 나도 저 낮은 정답률에 상당 부분 기여를 했다.. 문제는 간단하다. N개의 멀티탭 구멍을 M개의 기계를 쓸 때 플러그를 빼는 최소의 횟수를 출력하면 된다. 그리디로 푸는 방법의 핵심은 가장 나중에 쓰는 용품을 빼는 것이다. 가장 나중에 쓰는 용품을 뺀다고 해서 가장 마지막에 쓰는 용품을 빼는 것이 아니다. 3 8 1 2 3 1 2 3 1 2이 주어졌다면 1 2 3으로 멀티탭이 가득 찼을 때 꽂혀 있는 것들 중 가장 마지막에 쓰는 2를 빼는 것이 아니라 가장 나중에 출현하는 3을 빼는 것이다. 풀이과정을 정리해보면 1. 멀티탭이 비어있으면 꽂는다. 2. 멀티탭에 이미 꽂혀있으면 그냥 넘긴다. 3. 멀티탭에 꽂힌 물건 중 다시는 사용하지 않..
백준 1202 보석 도둑 Java 2019. 6. 24. 정답률 23퍼센트의 그리디 문제인 보석 도둑 문제이다. 보석의 개수 N개와 가방의 개수 M개가 주어지고 보석의 무게와 가격이 주어지며 가방에 담을 수 있는 무게의 양도 주어진다. 단 가방에는 하나의 보석밖에 넣을 수 없다. N과 M의 최댓값은 300,000으로 O(NM)의 시간복잡도로는 문제를 풀 수 없다. 다시 말해서 보석을 가격이 비싼 순으로 정렬하고 가방을 무게가 가벼운 순으로 정렬해서 이중 for문으로 가벼운 가방에 비싼 보석의 무게를 비교해보며 푸는 방식은 시간 초과가 나온단 말이다. 물론 나는 시간 초과가 나올 줄 알면서도 한 번 해봤다 ㅎ 이 문제를 시간초과 없이 해결하려면 PriorityQueue를 사용해야 한다. PriorityQueue는 우선순위 큐로 들어간 값에 우선순위를 매겨서 정렬..
백준 1543 문서 검색 Java 2019. 6. 24. 그리디 문제인 문서 검색이다. 문제는 a와 b 두 개의 문자열이 주어졌을 때 a에서 중복되지 않게 b가 몇 번 나오는지 출력하는 문제이다. 정답률이 30퍼센트인데 비해 굉장히 간단하다고 생각했다. 앞에서부터 비교해서 문자열 b가 몇 번 나오는지 찾으면 되는 문제이니까.. 그런데 몇분 후에 맞왜틀을 연발하고 있었다. 분명 맞았는데 왜 틀린 것인가.... 질문 검색에 있는 글을 찾다가 그 이유를 알 수 있었다.. 문자열을 입력받을 때 Scanner 클래스의 .next()로 입력받았었는데 문제에 이런 문구가 있다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다. 공백.... 공백이 문제였다. .next()는 공백을 기준으로 문자열을 초기화하기 때문이다.. .nextLine()으로 바꾸어주니 바로 해결되..
백준 1182 부분수열의 합 Java 2019. 6. 24. 백트래킹 문제인 부분수열의 합 문제이다. N과 S가 주어질 때 N개의 정수로 이루어진 수열에서 S가 되는 부분 수열의 개수를 출력하면 되는 문제이다. 예제로 주어진 5 0 -7, -3, -2, 5, 8의 경우엔 1. -3 + -2 + 5 = 0 이 하나의 경우만 된다. N의 제한이 20이기 때문에 백트래킹으로 N개의 정수로 만들 수 있는 모든 부분수열을 만들어 보면 된다. 주의해야 할 점은 S가 0인 경우에 아예 빈 부분집합 즉 공집합인 경우에도 백트래킹에서 조건에 맞다고 처리하고 개수를 +1 하므로 S가 0인 경우엔 개수에서 -1을 해준다. 또한 i번째 수를 더하는경우와 더하지 않는 경우를 통해 모든 부분집합을 찾아볼 것이므로 백트래킹 중간에 S와 부분집합의 합이 같다고 해서 return을 하면 안된다..
백준 2210 숫자판 점프 Java 2019. 6. 24. 정답률 70퍼센트가 넘는 백트래킹 문제인 숫자판 점프이다. 5*5 배열에 각각의 숫자가 상하좌우로 이동할 수 있을 때 나올 수 있는 6자리 수의 개수를 출력하면 되는 문제이다. 여태까지 풀어왔던 백트래킹 문제처럼 풀려했으나 계속해서 실패했다. 처음 수부터 출발해서 사용하는 경우와 사용하지 않는 경우의 수를 재귀 호출해서 백트래킹 하려고 했던 방식이다. 이 문제는 각각의 수가 전부 상하좌우로 이동할 수 있고 다녀갔던 곳도 재방문이 가능하므로 2중 for문으로 배열의 시작부터 끝까지 한 번씩 훑으면서 백트래킹을 해주면 되는 문제였다. 2중 for문으로 안 하고 1부터 24까지 for문을 한 번만 써서도 가능하다. 내가 짠 코드는 백트래킹이라고 하기도 좀 그런 게 되추적 하는 부분이 안 들어간다.. 1 2 3..

티스토리툴바