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 dfs를 이용해서 치킨집을 갯수만큼 정해주고, 만약 m과 치킨집의 수가 맞으면 각 좌표값을 이용하여 집집마다의 치킨 거리를 계산할 수 있는 문제였다. Code #include #include #include #include #include using namespace std; int n,m; vector chicken, house; long mins=9999999999; void dfs(int x, vector v){ if(v.size()==m) { int nu=0; for(int i=0; i

Concept & Idea 간단한 체크함수를 만듬으로써 문제를 비교적 간단하게 해결 할 수 있었다. check_s(3개짜리 정사각형 체크)함수는 구현하는데 생각을 좀 했어야 했다. 간단하게 row값과 col값을 3으로 나누고 거기서부터 3개씩 체크해주면 되는 파트였다. 처음에는 스도쿠에 빈 공간에 들어갈 숫자를 찾는데 10개짜리 배열을 계속 체크해주어야 한다고 생각했다. 그래서 배열을 계속 넘기고, 체크하고, 넘기고 다시 false인 요소의 값을 dfs돌려야 한다고 생각했는데, 확실히 감이 많이 죽은 것 같다. 그냥 For문을 10번씩 돌면서, 해당하는 숫자가 들어갈 수 있는가? 아닌가? 를 체크하면 간단하게 해결할 수 문제였다. DFS 안에 함수를 생각보다 복잡하고 비효율적으로 구현했었는데, 어차피 완..

Concept & Idea 간단한 완전탐색 문제였다. n도 최대 20밖에 안되서 dfs로 쉽게 해결할 수 있었다. 코드도 나름 깔끔하게 짰다고 생각하는데,, startScore랑 linkScore를 어떻게 하면 함수를 합칠 수 있을것 같은데,, 나름 만족한다. Code #include #include using namespace std; int n,map[21][21]; bool check[21]; int res=2000001; int startScore(vector start){ int cnt=0; for(int i=0; i

Concept & Idea 이 문제에서 가장 중요한 아이디어는 다익스트라를 두번 사용해야 한다는 점이다. 어떤 지점에서 X까지 도달하는 최소 거리 + X에서 어떤 지점까지 도달하는 최소 거리의 합의 최댓값을 구하는 문제였다. 필자는 시간초과 문제를 마주하여,, 몇 시간동안 고민했지만 바보같은 사고를 하였다. X에서 어떤 지점까지 가는 최솟값은 두번째 다익스트라로 해결하였다. 어떤 지점에서 X까지 가는 것은 N번 돌렸었는데, X의 지점을 최대한 이용하여, 역방향 거리를 가지고 있는 벡터를 만들어서 그 벡터를 X에서 출발하면 해결할 수 있는 문제였다. 해당 테스트 케이스에서 DP1에는 4,0,6,3 DP2에는 1,0,3,7 이 들어있어서 정답 10을 구할 수 있다. Code #include #include ..