본문 바로가기

알고리즘

 (179)
[BOJ 10942] 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 다이나믹 프로그래밍의 단골 소재인 팰린드롬이다. 다이나믹 프로그래밍의 핵심은, 큰 문제들을 해결하기 위해서 작은 문제들의 값을 이용하는 것이 핵심이다. 그렇다면, 팰린드롬을 분석해보자. 인덱스 i ~ j의 숫자들이 팰린드롬인지 확인해야 한다. 다이나믹 프로그래밍의 본질, 큰 문제를 해결하기 위해서 작은 문제들의 값을 이용해보자. DP[i][j]를 인덱스 i부터 j까지 펠린드롬 여부라고 정한다. DP[i][j]를 큰 문제라고 했을 때, ..
코딩테스트 실전 감각 키우기, 온라인 컴파일러 추천, BOJ 이번 글은 코딩테스트 실전 감각을 키우기 좋은 방법을 알려주겠습니다! 라인, 카카오, 네이버 등 IT기업들은 온라인 컴파일러를 통해서 코딩 테스트를 진행합니다. 이 말이 무슨 말이냐면, 삼성은 이클립스, 비쥬얼 스튜디오 등으로 실제 컴파일러를 통해서 코드를 작성한 후에 복사 붙여넣기가 가능하지만, 라인, 카카오, 네이버와 같은 회사들은 온라인 컴파일러에서 코드를 구현하도록 유도하고 있습니다. 왜냐하면, 부정행위 방지를 위해서 코드 복사 붙여넣기가 안되고 있기 때문에... 그래서 평소 공부를 하면서 실전 감각을 키울 수 있는, 온라인 컴파일러 사이트를 추천하려고 합니다. https://ideone.com/ Ideone.com Ideone is something more than a pastebin; it'..
[BOJ 9251] LCS(왜 동적계획법인가?) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 정말 다이나믹 프로그래밍의 정석같은 문제라고 볼 수 있다. 이 문제를 재귀 함수나, 동적 계획법으로 풀지 않았을 경우를 생각해보자. 두 문자열중에, 짧은 문자열을 사용해서 나올 수 있는 조합들을 모두 체크해본다고 가정하자. 짧은 문자열의 길이가 5라고 가정하면, 5C0 + 5C1 + 5C2 + 5C3 + 5C4 + 5C5의 연산이 필요하다. ..
재귀호출(recursive), 동적 계획법(Dynamic Programming) 알고리즘의 기본이라고 할 수 있는 재귀호출과 동적 계획법에 대해서 알아보자! 재귀호출 - 문제를 해결 하기 위해, 기존 문제를 작은 문제로 나눠서 문제를 푸는 것 - Big -> Small 동적 계획법 - 문제를 해결 하기 위해서, 작은 문제의 해결법을 이용해 기존 문제를 해결하는 것 - Small -> Big 그렇다면, 여기서 모든 재귀호출을 동적 계획법으로 표현할 수 있을까? 정답은 아니다. 동적 계획법이라면, 특정 단계의 문제를 해결하기 위해서, 특정 이전 단계의 문제들을 모두 해결해야 한다는 것이다. 하지만, 특정 이전 단계들의 문제들을 차례로 해결하지 않으면, 특정 단계의 문제를 해결할 수 없게 된다. 따라서, 모든 재귀호출이 동적계획법으로 표현될 수 있는 것이 아니다. 동적 계획법으로 특정 단..
두 수의 부호가 같은지 다른지 확인하는 방법[XOR], C++, 코딩스킬 일반적으로 두 수의 부호가 다르기 위해서, if문을 쓸 수도 있다. 물론 이 방법은 너무 쉽기 때문에... 누구든지 생각할 수 있다. 만약에 a, b라는 숫자가 있다고 하면, 여기서 곱하기로 부호를 체크한다면, overflow가 발생하기 때문에 틀린 방식이다. 따라서, a와 b의 부호를 각각 확인해주는 방식을 사용한다. if((a > 0 && b >0) || (a = 0 처음보면 낯설 수도 있다. 하지만..
Manacher's Algorithm, 펠린드롬 길이가 N인 문자열이 있을 때, 펠린드롬을 가장 빠르게 판단할 수 있는 방법은 마나체스 알고리즘이다. 시간 복잡도는 O(N)이다. Manacher's algorithm은 문자열 내에서 팔린드롬(palindrome,회문)을 찾는것과 관련된 알고리즘이며, 시간 복잡도는 O(n) 이다.(n은 문자열의 길이) 이 알고리즘은 문자열 S를 입력으로 받아 다음을 반환한다: 문자열 S와 길이가 같은 정수 배열 A, 각 A의 원소 A[i]는 i번째 문자열을 중심으로 하는 가장 긴 팔린드롬의 반지름의 길이.(즉, S[(i−A[i])⋯(i+A[i])]는 팔린드롬이며, S[(i−A[i]−1)⋯(i+A[i]+1)]은 팔린드롬이 아니다) 예를 들면, S='banana'라는 입력에 대해 A의 결과는: 알고리즘은 다음과 같다: i는..
9252번 : LCS 2 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍 문제이다. DP 정의를 잘하면 쉽게 풀 수 있는 문제이다. 두 문자열의 가장 긴 공통된 부분 수열을 찾아야 하는 문제이다. str1 : ACAYKP str2 : CAPCAK 이 두 수열에서 가장 긴 공통된 부분 수열을 어떻게 찾을 수 있을까? 만약 가장 긴 공통된 부분 수열이 있다고 가정하면, CAPCAK에서 각 문자는..
2096번 : 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 이 문제는, 간단하게 상향식 접근으로 문제를 풀 수 있지만, 메모리 초과가 계속 발생한다. 따라서, 계속 사용되는 DP 값들만 저장해둬야 한다는 아이디어가 필요하다. 점화식은 다음과 같이 작성할 수 있다. R = ROW(1 ~ N) C = COL(1 ~ 3) 만약 C가 1이고, DP를 R, C까지 온 최댓값이라고 정의하자 DP[R][C} = max(DP[R - 1][0], DP[R - 1][1]) + arr[R..

티스토리툴바