문제 출처 https://www.acmicpc.net/problem/1464 1464번: 뒤집기 3 세준이는 어떤 문자열 S를 뒤집으려고 한다. 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자. i만큼을 뒤집는다는 소리는 그 문자열의 처음부터 정확하게 i개의 문자를 역순으로 뒤집는 www.acmicpc.net 문제 풀이 및 코드 해당 문제는 뒤집기 정렬에 관한 문제이다. 0~i번째까지만 뒤집기가 가능하다. 필자는 재귀를 이용하여 접근했다. 만약 가장 작은 알파벳이 뒤에 존재한다면, 앞에서 뒤집기를 하는 과정들이 무의미하다고 생각했고 가장 앞으로 오는 알파벳을 먼저 탐색했다. 따라서 가장 작은 알파벳을 찾되, 중복이라면 가장 뒤에 있는 값을 찾고자 했다. 해당 값을 m, index를 i라고 한다면 다..

문제 출처 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 풀이 및 코드 해당 문제는 dfs, bfs 문제로 경로마다 알파벳 종류를 파악해야 하는 문제였다. 필자는 bit연산을 이용해 알파벳을 저장했다. 알파벳이 26종류이니 a = 1, b= 2, c= 4이런식으로 사용했다. 따라서 dfs를 통해 경로가 진행될 때마다 해당 좌표의 알파벳을 지나왔는 지 체크하도록 visited라는 변수를 만들었다. 즉 visited에는 해당 경로를 ..

문제보기 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 및 코드 필자가 해석하기에 해당 문제에서는 함정이 있었다. 원하는 만큼 가지고 있는 주식을 판다. -> 최대이익을 얻기 위해서는 전부 팔거나 전부 사거나 두가지 경우만 존재했다. 아무것도 안한다. -> 일단 구매하고 동일한 가격에서 판매해도 동일하다 필자는 뒤에 더 비싼 가격이 나온다면 구매하고, 더 비싼 가격이 나오지 않는다면 해당 가격에서 판매 하는 두가지 원칙을 기..

문제보기 https://www.acmicpc.net/problem/3758 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net 풀이 및 코드 해당 문제는 특별한 알고리즘 활용 보다는 단순 구현 문제이다. 필자는 id 별로 값을 비교해야 하는 상황이 있을 시에 heap구조를 이용했다. heap 구조가 이럴때 편한게 list 형태로 value를 저장할 때에 첫번째 인자만 sort에 영향을 주기 때문에 시간 관리 차원이나 코드의 이해도 차원에서나 장점이 많다고 생각한다. 자세한 내용은 주석을 따라가며 실행하면 이해될 것이다!..

문제보기 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 풀이 및 코드 해당 문제는 dp를 이용해 푸는 문제로 solved.ac.기준 골드 3에 랭크되어 있다. 요즘따라 dp 문제를 유독 많이 푸는 것 같다ㅎ 핵심 점화식은 다음과 같다. for i in range(s, e): dp[s][e] = min(dp[s][e], dp[s][i] + dp[i+1][e]) dp[s][e] += sum(arr[s, e+1]) dp에는 s부터 e까지 ..

문제 출처 https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net 풀이 및 코드 해당 문제는 대표적인 dp문제로 solved.ac에서 골드 3으로 랭크되어 있다. 필자는 dp[i][j]에 0~i 까지 j개의 구간을 나누었을 때의 최대값을 저장해 주었다. 숫자를 추가해가며(i를 증가시켜가며) dp[n][m]을 구했다. 이때, 총 3가지 상황으로 분류할 수 있다. 1) i번째 요소를 구간에 포함시키지 않느다. 2) i번째 요소를 ..