Social Developer

어제보다 한 걸음 더

Algorithms

바로 직전에 풀었던 수들의 합2(2003번) 문제와 매우 유사하다. sdesigner.tistory.com/58 투 포인터로 S보다 큰 경우를 찾고, 경우의 수 대신 범위의 길이를 출력해주면 되겠다. 이번 문제에서도 N이 100,000인 경우 모든 원소가 10000이라고 해도 합이 약 10억이다. int형 변수를 사용하는데 문제가 없고 0.5초 시간 제한에도 딱히 문제가 없다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, S; static int arr[]; static int ans; static int star..

2021. 2. 5.

Algorithms

전형적인 투 포인터 문제다. 수열 하나에 포인터 두 개를 두고 탐색해주면 된다. 수열의 길이인 N의 최댓값이 10,000인데, 각 원소가 30,000을 넘지 않으므로 수열의 모든 원소를 합쳤을 경우에도 int의 범위에 해당해 처리하는데 문제가 없다. 마침 합으로 만들어야 하는 M의 경우에도 최댓값이 3억으로 알맞게 주어졌다. 시간 제한은 0.5초로 다른 문제와 비교해 길지 않은 편인데, 투 포인터로 배열 하나를 모두 돌아다녀야 2N으로 O(N)이고 최악의 경우 길이 10,000이라고 해도 20,000 번 안에 탐색이 끝나니까 0.5초면 충분하겠다. 주 풀이는 합에 포함할 범위의 처음과 끝을 나타내는 포인터 2개(start, end), 합을 저장할 변수 1개(sum), 합이 M과 같을 경우의 수를 세는 변..

2021. 2. 5.

Algorithms

문제를 잘 이해해야겠다. 지문에서 크기가 양수인 부분수열 중에서~ 부분이 있는데 크기가 양수라는 말 그대로 이해하지 못하고, 값을 양수라고 생각했다. 지금 보면 헷갈릴 이유가 없는데, 처음 접했을 때는 이상하게 헷갈렸다. 크기가 양수인 부분수열이라 하면 아무 것도 선택하지 않는 상황만을 제외하면 되겠다. 그런 경우도 부분수열이라고 할 수 있는지는 몰랐지만 아마 집합에서의 부분집합에서 공집합 개념과 유사하지 않은가 싶다. 풀이는 먼저 DFS, 백트래킹 개념을 이용하면 된다. 수열의 각 원소로 구할 수 있는 값을 모두 구하면서, 값이 S와 동일한지 아닌지를 체크하면 되겠다. 시간 제한이 2초로 주어졌는데, 수열의 길이인 N의 최댓값이 20이다. 각 원소를 합에 포함할 지, 하지 않을지 두 가지 선택지를 모든..

2021. 2. 5.

Algorithms

지문은 간단하다. 입력으로 k개의 수를 주기 때문에, 그 k개의 수에서 6개를 골라 사전 순으로 출력하면 된다. 진짜 문제는 k개의 수에서 6개를 고르는 과정과 이를 사전 순으로 출력하는 과정이다. 간단한 것 같은데 은근히 머리가 아프다. 알고리즘 분류에 백트래킹이 있기 때문에 풀이 방법을 떠올리면 다행인데, 이를 모르고 풀이를 떠올리기는 쉽지 않을 것 같다. 어쨌거나 백트래킹을 활용한 DFS라는 것을 떠올릴 수 있다면 구현은 복잡하지 않게 할 수 있다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class P6603 { static int[] S; stati..

2021. 2. 2.

Algorithms

문제를 보고 처음 한 것은 예제 입력을 직접 그려보는 것이었다. 직사각형이 여러개 그려지는 모습이 머릿속에서 잘 안그려졌기 때문.. 그리다가 x, y를 바꿔 그려 다시 그리면서 너무 더러워졌다.... 붉은색으로 입력받은 직사각형을 하나하나 그려주고 번호를 매겨줬다. ???... 겹쳐서 그려지는 직사각형이 있다. 문제에서 펜을 떼는 PU 명령의 최솟값을 구하라고 했고, 거북이가 같은 선을 여러번 그릴 수 있다고 했다. 펜을 떼지 않고 그릴 수 있는 직사각형들은 떼지 않고 그리고, 떼는 횟수를 구하면 될 것 같다. 근데 떼지 않고 그릴 수 있는 직사각형의 정보를 어떻게 담지.. 고민하다 먼저 생각이 든 것은 그려야 하는 좌표들을 Set에 모두 담아두는 것이었다. Set을 생각한 이유는 겹치는 부분들은 중복해..

2021. 1. 29.

Algorithms

완전탐색 - 1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143 출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm] 알고리즘 문제풀이(PS) 시작하기 이런건 고수들이나 써야 하지 않나 싶지만, 그래도 1년정도 공부하면서 이 분야를 어떻게 시작해야 할지 써보려 한다. 라고 운을 뗀다음 열심히 내 얘기만 했던 후속편이다. 내 인생사가 궁금하 plzrun.tistory.com 사실 이 문제는 ..

2021. 1. 8.

Algorithms

완전탐색 - 1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143 출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm] 알고리즘 문제풀이(PS) 시작하기 이런건 고수들이나 써야 하지 않나 싶지만, 그래도 1년정도 공부하면서 이 분야를 어떻게 시작해야 할지 써보려 한다. 라고 운을 뗀다음 열심히 내 얘기만 했던 후속편이다. 내 인생사가 궁금하 plzrun.tistory.com 지문도 짧고 간결..

2021. 1. 8.

Algorithms

완전탐색 - 1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143 출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm] 알고리즘 문제풀이(PS) 시작하기 이런건 고수들이나 써야 하지 않나 싶지만, 그래도 1년정도 공부하면서 이 분야를 어떻게 시작해야 할지 써보려 한다. 라고 운을 뗀다음 열심히 내 얘기만 했던 후속편이다. 내 인생사가 궁금하 plzrun.tistory.com 처음 문제를 접근..

2021. 1. 8.

Algorithms

완전탐색 - 1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143 출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm] 알고리즘 문제풀이(PS) 시작하기 이런건 고수들이나 써야 하지 않나 싶지만, 그래도 1년정도 공부하면서 이 분야를 어떻게 시작해야 할지 써보려 한다. 라고 운을 뗀다음 열심히 내 얘기만 했던 후속편이다. 내 인생사가 궁금하 plzrun.tistory.com 문제를 풀면서 많..

2021. 1. 8.