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