우당탕탕 개발일지

https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해결 방법주어진 수를 이진수로 변환하고, 배열 num에 넣는다.이진수 배열 num를 이용해 이진트리를 만든다.이진트리가 적합한지 판단한다. 만약 더미노드가 1을 자식으로 보유하고있다면, 적합하지 않다는 의미이다주의할 점이진수 배열 num의 개수를 꽉찬 이진트리 개수와 맞게 해야한다. 이진수가 모두 들어갈 수 있는 이진트리의 depth를 찾아 총 필요한 노드의 개수를 찾고, 앞을 0으로 채운다.이진수 배열 num은 거꾸로 저장되어있다. num이..

https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  문제 접근 방법간선의 연결 정보를 저장한다.간선 정보를 저장하기 위해 2차원 배열(인접 리스트)을 선언한다. 예를 들어 [1, 3]이라는 간선이 있으면, 1번 노드와 3번 노드 양쪽에 각각 연결 정보를 추가한다. 이렇게 하면 양방향 그래프로 간선을 쉽게 관리할 수 있다.하나씩 간선을 제거하면서 두 트리의 개수 차이를 계산한다.모든 간선을 하나씩 제거해 보고, 그때 두 개의 트리로 나뉘게 된다. 이때 0번 노드에서 시작해서 BFS로 탐색하며 한..

https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  해결 방법일반적인 다익스트라로 풀면 안된다. 일반적인 다익스트라로 풀경우, 몇 가지 테스트에서 실패가 나온다.🚩 문제의 핵심:✅ 1. 같은 좌표라도 "어떤 방향"으로 도착했는지가 중요하다!같은 지점 (x, y)에 도착했다고 해도, "어떤 방향으로 왔는가"에 따라 앞으로 이동할 때 비용이 달라질 수 있다.📍 예시:(0,0) → (0,1) → (1,1)로 이동하는 상황을 생각해보자. 1️⃣ 수평 이동: (0,0) → (0,1) (오른쪽으로 이..

https://school.programmers.co.kr/learn/courses/30/lessons/132266 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해결 방법이 문제는 Level 2. 배달  문제와 동일하게 다익스트라 알고리즘으로 푸는 문제이다. 여기에서 몇가지 주의사항이 늘어나서 Level 3이다.문제에서 제공한대로 각 지점에서 desination까지의 거리를 각각 찾지말고, destination을 출발지점으로 정하고 다익스트라를 하면 각 지점까지의 최소거리가 나온다. 지점의 수는 10만개까지이다. 즉 맵이 너무 크기때문에, 맵 정보 저장시 10만x10만의 배열로 만드는 것은 너무 비효..

https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해결 방법 1번마을에서부터 각 마을까지의 최단거리를 구한다.각 거리가 K이하인 마을의 개수를 반환한다.최단거리를 구하는 방법은 다익스트라를 사용한다. 주의사항이 문제에서는 최단거리 경로는 궁금하지 않고, 값만 궁금하므로, 이전노드를 저장하는 prev는 필요가없다!이 문제에서 도로는 양방향 도로이므로, map에 값을 넣을때 양방향 모두에 넣어줘야한다.getIndex()함수는, 다음으로 검사할 마을을 찾는 함수이다. visited되지 않았으며, 현..

https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이진트리 탐색으로 모든 경우의 수를 탐색하고, 그 중 양이 제일많은 경우를  찾는 문제이다.이 문제가 진짜 어려웠던 것은, visited했던 곳도 나중에 다시 찾아야 한다는 점이다. 한마디로 자신의 삼촌이나 조카노드까지 다시 검사를 해야한다.  내 아래에있는 자식들까지 모두 검사를 했다면, 내조카, 삼촌들을 위해서 visited = false로 변경해주는것이 핵심인 문제이다.   #include #include #include #include ..

https://school.programmers.co.kr/learn/courses/30/lessons/136797 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제는 DP (동적 계획법) 을 사용해야 하는 문제이다. 첫번째 문자열부터 시작해서, 결과값을 저장한다. 다음 문자열을 검사할 때, 이전 기록을 가져와 최적의답을 찾는다. 해결방법3차원 배열 m을 선언한다. m[1][2][3] 은 첫번째 문자열까지 눌렀고, 왼손이 2, 오른손이 3일때의 최솟값이다. 우리의 목표는 m[문자열사이즈] 에서의 최솟값을 찾는 것이다.m[0][4][6] = 0 을 넣는다. 이는, 시작할때 왼손에 4, 오른손에 6이..

https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해결 방법(실패)BFS를 이용하여 최단 거리를 찾으려 했다. S와 L, E 의 인덱스를 찾는다.S 에서 L 로 goSearch() , L에서 E로 goSerach() 를 수행하여 합을 리턴한다. 둘중 하나라도 -1이 나올 경우, 경로가 없다는 의미이므로 -1을 반환한다. goSearch() 는 아래와같이 동작한다.검사여부를 저장하는 visited와, 검사 대기줄인 queue를 생성한다. 시작점부터 queue에 넣고, 상,하,좌,우를 검사한다...