Will the Guru

Category: Algorithm

  • (KOR) 섬 연결하기

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://programmers.co.kr/learn/courses/30/lessons/42861 Solution Key Points MST 의 대표적인 문제. DFS를 이용하여 풀이하려 했으나, 크루스칼 알고리즘을 이용하여 풀 수 있는 대표적인 문제이기에 Kruskal Algorithm을 참조하여 풀이함. 다른 풀이 : https://hyem-study.tistory.com/90

  • Kruskal Algorithm

    Kruskal algorithm is a way to find a Minimum Spanning Tree(MST) from undirected edge-weighted graph. Minimum Spanning Tree(MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.  That is, it is a spanning tree whose sum of…

  • (KOR) 줄 서는 방법

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://programmers.co.kr/learn/courses/30/lessons/12936 Solution Key Points Next Permuatation을 구하는 방법으로 하면 20! 의 경우의 수를 다 계산해야 하는 경우가 있을 수 있다. Timeout 이 발생할 수 있으므로 다른 방법을 찾아야 했다. 풀이 방법 k 번째 수를 구할 때, 첫 번째 자리 수 첫 번째 자리 수가 1일 경우의 수는…

  • (KOR) 주사위 굴리기

    Problem – ⭐️ https://www.acmicpc.net/problem/14499 Solution Key Points 시뮬레이션 문제는 문제를 꼼꼼히 잘 읽어야한다! 주사위가 굴러갈 때 칸의 수가 변경되는 부분을 처리하지 않아서 디버깅하는 데 오래 걸렸던 문제

  • (KOR) 로봇 청소기

    Problem – ⭐️⭐️⭐️ https://www.acmicpc.net/problem/14503 Solution Key Points 시뮬레이션 문제는 보통 문제에서 하라는대로 그대로 구현하면 풀리는 문제가 많다 이 문제에서는 조건 c 를 체크하는 것이 헷갈렸던 문제“네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다” 그림의 파란색 선

  • (KOR) 프린터 큐

    Problem – ⭐️⭐️⭐️ https://www.acmicpc.net/problem/1966 Solution Solution 1 – NodeQueue 클래스 정의 Solution 2 – 2 개의 큐를 이용한 비교 – ⭐️⭐️⭐️ Key Points Solution1 은 문제에서 주어진대로 새로운 큐 클래스를 정의한 풀이이며 Solution 2는 일반 큐와 priority가 높은 순서대로 정렬시켜 놓은 큐를 이용하여 값을 비교하면서 풀이한 방법이다. Scanner scan =…

  • (KOR) 하노이 탑 이동 순서

    Problem – ⭐️⭐️ https://www.acmicpc.net/problem/11729 Solution Key Points 점화식을 떠올리는 것이 포인트였던 문제. 장대가 3개이므로 1~(n-1)까지는 1->2로, n 은 1->3으로, 그리고 1~(n-1)을 2->3으로 옮겨주면 된다. 점화식이 바로 떠오르지 않는 경우, 직접 시도해보면서 아이디어 떠올릴 수 있도록 하자

  • (KOR) 블랙잭

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/2798 Solution Key Points Iteration, Recursion 둘 다 연습해 볼 수 있는 좋은 문제. 주어진 배열을 우선 sort 한 후 sum을 계산하는 것이 더 시간효율적이다. 작은 수 더했을 때 M보다 크면 큰 수 더하는 작업은 해보나 마나 이기 때문. Recursion 의 경우 백트래킹의 수도코드처럼 isValid 할 경우만…

  • (KOR) 별 찍기 – 10

    Problem – ⭐️⭐️⭐️ https://www.acmicpc.net/problem/2447 Solution Key Points Board를 Grid로 나눠서 여러번 재귀를 호출하는 것이 주요 포인트였던 문제. 작은 문제를 재귀로 여러번 호출하는 것의 대표적인 문제 재귀는 본인을 반드시 한번만 부르는 것이 아니다

  • (KOR) 가사 검색

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://programmers.co.kr/learn/courses/30/lessons/60060 Solution Key Points Main Point 자료구조 트라이(Trie)를 사용하는 것 각 노드 당 몇 개의 Leaf node가 존재하는 지 정보를 저장하는 것 – 변수 wordCount 처음 풀이할 때는, wordCount를 저장하지 않고 DFS 로 탐색해서 count를 반환하도록 하였다. 그러나 이 방법은 extra 시간을 요구하므로 timeout. Word 길이당 다른…