https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 처음 이 문제를 봤을 때는 그냥 주어진 문자열과 주어진 시작,끝 인덱스를 이용해서 비교값과 같으면 count값을 증가시키는 방식을 생각해냈다. 하지만 그렇게 했더니 50점만 받을 수 있었다. 이 문제에서 바라는 것은 누적합계산이었다. 즉, 값 저장 배열을 만들어서 누적된 계산의 합을 구하라는 것이다. 그래서 표를 만들었다. joon이라는 문자열이 ..

https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 중복되는 수열을 제거하고 또한 이전에 앞자리에 쓰인 숫자는 사용이 안되게 만드는 것이다. 하지만 자기자신을 사용한 경우는 출력한다. 잘 알아듣지 못할 수도 있어서 I/O 예제를 가져왔다. 여기서 사용해야할 것은 중복을 제거하기 위한 메서드 수행시마다 확인할 tmp와 시작지점을 바꿀 at을 사용한다. 물론 변수는 다른걸 사용해도 상관없다. 그렇게 해서 dfs메서드를 재귀로 돌리는 동안..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 중복되는 수열의 출력을 제거하고, 나올 수 있는 모든 수열을 출력하는 문제이다. 즉, 자기자신이 두 번 출력되는 것을 없애고, 나머지를 출력하는 것이다. 이 문제를 해결하기 위해서는 매번 메서드를 호출할 때마다 중복을 검사해줘야한다. 중복을 검사하는 방법은 방문했던 값인가, 이전의 값과 같은 값인가를 비교하는 방법인 두 가지로 이루어진다. 아래의 코드를 보면 이해가 빠를 것이다. pu..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 유튜브에서 DP관련 영상을 본김에 DP문제를 풀어보기로 했다. 위의 문제는 주어진 코드로 피보나치 함수를 구형하면 시간초과가 난다. 그래서 이것은 중복적으로 계산하는 횟수를 생략하여 DP배열에 저장하고, 그 값을 이용하는 것이다. 즉, 피보나치 수열은 fibonacci(3)=fibonacci(2)+fibonacci(1)이고, fibonacci(4)=fibonacci(3)+fibonacci(2)이니까 이전의 값을 저장해두면 다시 반복해서 계산하는 과정을 생략하고, 값을 구할 수 있다. 즉, fi..

https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이 문제는 15654번과 15650번을 합친 문제라고 생각할 수 있다. 풀이는 간단하다. 입력 받은 배열을 이용하여 dfs를 구현하는 것이다. 중요한 것은 중복이 없고 앞자리 수보다 작은 수는 오지 않게 만든다는 것이다. 그럼으로 15650번과 마찬가지로 at 변수를 사용하여 시작지점을 설정하여 출력하면 된다. 15650번과 같은 방식과 15654의 배열 이용 방법을 이용한 것이기 때문에..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이번 문제는 저번 스타트링크 문제를 풀고 백트래킹을 더 공부해야겠다고 생각해서 N과 M을 전부 풀어볼 목적으로 한다. 이 문제는 저번 15649번의 코드를 아주 조금 바꾸면 되기에 간단하게 설명하겠다. 먼저 각 수열 내부의 중복을 제거해야하지만, 각 수열로 봤을 때 역순은 있어야한다. 그렇기에 방문체크를 사용하여 이 문제를 해결 할 것이다. 출력은 다른 N과 M문제들과 마찬가지로 깊이가 ..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이번 문제는 많은 감자짓을 통해 해결한 문제이다. 알고리즘 장인 선배의 도움이 없었다면 못풀고 몇일을 고민하다 답지 봤겠지.. 처음 이 문제를 봤을 때 문제의 이해를 조금 잘못해서 삽질의 시간이 좀 더 오래걸렸다. 나는 팀을 주어진 수에서 2명씩 골라서 2팀을 만드는 문제인줄 알고 삽질하다가 선배가 문제 설명해줘서 이해하고 접근을 시작했다. 그런데도 접근 방법이 떠오르지 않아서 도움을 통해 접근했다...ㅎㅎ 그래서 이..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 요즘 DFS 알고리즘 공부를 하면서 백트래킹 문제를 풀어보았다. 그 과정에서 나는 오늘도 한 감자 했다. 주변에 알고리즘 고수들이 없었다면 내 알고리즘 지식이 어땠을지ㄷㄷ... 오늘의 감자 짓은 DFS를 구현하고 값의 차이를 절댓 값으로 구해야 하는데 구하지 않아서 정답이 나오지 않아 계속 삽질 한 내용이다... 아침부터 계속 이 문제 붙잡고 생각하면서 브루트 포스로도 해보고, 별짓 다 해봤는데 결국 알고리즘 고수님의..