Victoree's Blog

Concept & Idea 메모리 초과로 인해서 고생했다.. 맨처음에 생각을 좀 잘못해서, dfs 인자로 stack과 스트링을 넘겼기 때문.. 최대 스트링이 200인데, DFS 로 풀었을 때, 2^200개의 노드가 생기기 때문에 그렇게 풀면 안된다. + Match 를 기록하는 함수 역시 For 문으로 앞뒤에서 체크하는걸로 구현했는데,, () + () 이러한 수식의 경우, 잘못 체크될 수 있기 때문에 아래와 같이 stack으로 푸는것으로 변경하였다. (괄호하면 스택인듯..) DFS 인자에는 현재의 Index만 넘기고, 해당 함수내에서 넣기로 선택한 ()의 경우, choice를 True로 하고 ) 인 경우, 이전 매칭되는 녀석이 들어왔을 때에만 선택되도록 해줘야한다. Code #include #include..

Concept & Idea 우선순위큐를 너무 오랜만에 사용하다 보니.. 솔직히 말하면 다익스트라 문제 풀때나 조금 사용해봐서 낯설다 ㅎ 직접 Comp 함수 구현해서 Sort 하도록 한게 너무 오랜만이라 가져와 본 문제이다. 문제는 위 사진을 읽기만 해도 무슨 문제인지 알 것 이다. priority_queue를 pair 형으로 제작했다. {절댓값, 원값} 의 형태로! comp 함수를 정의해서 내가 Sort하는 순서를 정할 수 있는데, 절댓값이 같을 땐 원값이 작은 순으로, 그 외에는 절댓값 순으로 소팅되는 형태이다. comp 함수 작성하는 데에 생각보다 시간이 오래걸린 거 같다. :( 아쉬운 마음 그득,, Code #include #include #include using namespace std; str..

Concept & Idea 처음에 문제 이해가 잘 안되서 좀 당황했다. 나는 N번째 큰수 라는 제목을 보고 왜 뒤에서 N번째로 큰수라고 해석했는지.. 문제는 간단하다. 입력대로 받은 수 중에 N번째로 큰수를 찾으면 되는 문제! 이 문제에 키포인트는 메모리에 있다. N이 1500이면 우선순위큐에 데이터를 1500*1500개까지 받을 것이냐? 그렇지 않다. 어차피 앞에서 몇번째로 큰지가 중요하기 때문에 뒤에서 뒤에 쓸모없는 작은 숫자들은 버려져도 된다. 처음엔 어떻게 해서 뒤에 녀석들을 다 빼지..? 포문을 돌려..? 라는 생각을 했으나 전체 수에 -를 곱해서 넣으면 해결 할 수 있다. 12 -> 7 -> 9 -> 15 -> 5 순서로 들어와도 -5 -> -7 -> -9 -> -12 -> -15 순으로 입력..

Concept & Idea 이 문제는 트리의 노드가 중간에 사라지면, 그 트리 하단부를 제외한 나머지 노드의 리프노드 수를 구하는 문제이다. 처음에 생각을 잘못해서 전체 노드의 리프 노드 수를 구하고, 사라진 노드의 리프노드 수의 차로 결과를 냈는데, 그렇게 하면 문제가 있다. 만약 특정 노드가 사라졌을 때, 루트노드도 리프 노드가 되는경우! 이다 그 부분만 수정해서 풀까 했는데,, 사실 deleted_node 자체를 탐색하지 않음으로 Dfs 함수 한번으로 해결 할 수 있는 문제였다. 인접 행렬에서 deleted_node가 들어있으면, 해당 노드는 탐색하지 않고, 나머지 리프 노드들의 수를 누적해서 해결할 수 있다. Dfs 를 Void 함수로 작성해서 많이 풀곤 하는데, Int 를 반환하는 함수로 누적합..

Concept & Idea 간단히 재귀함수로 구현할 수 있는 문제였다. 완전 이진 트리이기 때문에 입력은 당연히 2^k-1만큼 들어올것이다. 전체 리스트의 left, right의 중간 지점 녀석이 현재 depth의 루트인 녀석이다. 재귀함수를 구현할 때, 가장 먼저 해야할 점은 해당 함수의 인자와 종료 조건을 결정하는 것이다. 종료조건은 보통의 이진탐색 로직의 모습과 거의 유사하다. 그 이후엔 어떤 순서로 이 함수를 다시 호출할지 적어주면 된다. 이 문제에서는 트리의 출력이 좌측부터이기 때문에 그냥 왼쪽부터 재귀하도록 구현했다. Code #include #include #include using namespace std; vector result[10], input; void make_tree(int d..

Concept & Idea 큐 자료구조를 이용해서 문제를 해결하는 아주 간단한 문제라 할 수 있습니다. count로 요래조래해서 풀 수 있지 않을까 싶었는데, 안되는거 같길래 그냥 큐에 초기화시켜서 돌리는 방식으로.. 해결했네요 :( Code #include #include using namespace std; int main(int argc, const char * argv[]) { int n,k; queue qu; cin>>n>>k; for(int i=1; i

Concept & Idea 문제 접근을 어떻게 할까 하다가 앞에 요소를 체크하려 했는데, 결국 과거의 값을 되돌아 생각해보는 것으로 생각해보니 해결되었다. row가 0일 경우에, row가 1이고 && col이 자기 자신보다 -1,-2인 값중 큰 값을 누적하여 더한다.row가 1일 경우에, row가 0이고 && col이 자기 자신보다 -1,-2인 값중 큰 값을 누적하여 더한다. DP배열에는 누적으로 최대값을 쌓아가고, 최종적으로 마지막 col의 최댓값을 출력하면 해결되는 문제였다. Code #include using namespace std; int t; int map[2][100001]; int cnt=0; int dp[2][100001]; int main() { cin>>t; for(int i=0; i..

Concept & Idea 어려운 문제는 아니었다. 우선 이차원 dp[i][j]배열의 첫번째 요소 [i]값은 n자리수를 뜻한다. 또한 두번째 요소 [j]값은 마지막 자리가 0으로 끝나는 수의 갯수, 1로 끝나는 수의 갯수 로 설정해두었다.마지막 자리가 0으로 끝나는 수는 다음자리 수를 만들 때, 0과 1로 두 가지를 더 만들 수 있다.반면, 마지막 자리가 1로 끝나는 수는 11의 문자열을 가질 수 없기 때문에 0만 붙여서 만들 수있다. dp[i][0]=dp[i-1][0]+dp[i-1][1]; dp[i][1]=dp[i-1][0]; 이런 점화식을 만들어낼 수 있던 간단한 문제였다. 배열을 long long 으로 설정해두어야 한다. Code #include using namespace std; long lon..

Concept & Idea 팰린드롬을 다이나믹 프로그래밍을 이용하여 푸는 문제였다. 또한 제한시간이 0.5초로 엄청 빡센 문제였다. 팰린드롬 체크를 단순히 떠오르는 방법으로 하게되면, 양쪽에서 체크하는 N^2만큼의 시간복잡도를 가진다. 그럼 이 문제를 다이나믹 프로그래밍을 이용하여 푸는 법은 무엇일까? 다이나믹 프로그래밍에서 가장 중요한 개념은 메모제이션이다. 또한 메모제이션을 어떻게 할 지 n에 대한 일반식으로 나타내는 것이 중요한 것 같다. 팰린드롬을 이전의 기록을 이용하여 체크할 때, ‘XXX라는 문자열이 팰린드롬이다’ && ‘_XXX_좌우에 붙는 문자들이 같다’ 라면 이 문자열 역시 팰린드롬이 된다. 이 Idea를 이용하여 다음 순서를 생각할 수 있다. 길이가 1인 문자열은 무조건 팰린드롬이다. ..

Concept & Idea 이전에 풀었던 팰린드롬? 의 문제의 코드를 이용해서 문제를 해결할 수 있었다. DP를 두 번에 걸쳐서 이용해야 했다. 일단 DP를 이용해서 i부터 j까지 팰린드롬인지 아닌지를 체크했다. 두번째는 약간 팰린드롬을 체크한 DP배열을 이용해서 분할의 최소값을 구하는 것이었다. D[i] = min(D[j-1]) + 1 이 공식을 생각하는 것이 어려웠다. 이 문제를 풀때 런타임 에러를 두 번이나 실수했다. 우선 팰린드롬? 문제를 풀 때는 인덱스를 1부터 시작했는데, 이 문자열을 0부터 시작하려고 하니까 계속 실수를 하게 되었다. 1. 두번쩨 for문으로 두 글자 팰린드롬을 체크할 때, 문자열 길이만큼 도는데 i와 i+1을 비교해서 실수를 했다. 2. 32번째 줄에 pel[i]>pel[j..