Jonyo Programming

[프로그래머스 124 나라의 숫자] 프로그래머스 LEVEL 2 문제를 다 풀려고 한다. LEVEL2와 백준을 비교해봤을 때 대략 백준 실버~골드하위 정도 되는것 같다. 이번 문제는 숫자를 입력받아 그 숫자를 124 나라의 규칙에 맞게 변환해야 한다. 숫자가 규칙적이 아니라 단순히 mod연산으로는 구할 수 없지만 문제를 잘 읽어보면 규칙이 보인다. n[4]는 n[1]에 1을 붙인꼴, n[5]는 n[1]에 2를 붙인 꼴, n[6]은 n[1]에 3을 붙인 꼴이다. n[7]부터는 n[2]에 1을 붙인꼴 ... 이런식으로 흘러간다. 따라서 입력을 받은 후에 자신의 앞에 붙일 수들이 무엇인지 재귀를통해 찾도록 구현했다. 예를들어 13을 입력받으면 n[13]은 n[4]에 1을 붙인꼴이고, n[4]는 n[1]에 1을 ..

이번 방학목표로 했던 플레티넘을 달성했다. 이번에 SDS 알고리즘 특강을 들으면서 세그먼트 트리, 트라이 등 새로운 자료구조를 배우고 그를 이용하여 문제를 많이 풀었기에 가능했던 것 같다. 이제는 티어 높은 문제 풀겠다고 새로운거 공부 하는것보다 코테에 자주나오는 기본적인 유형들에 좀 더 집중해야 할 것같다. 아직도 기본적인 DP문제도 어려운걸 보니 갈 길이 먼 것같다. 확실히 SDS 특강을 시작한 후 부터 빠르게 올라가기 시작했다.. 역시 나는 동기가 있어야 움직이는 것 같다. 아무런 도움없이 풀이법을 생각해 내어 코딩으로 옮기고 한번에 AC를 받는 짜릿함을 알아버렸기에 취업을 하고도 백준은 꾸준히 들릴 것 같다. 계속 열심히 나아가다 보면 언젠가는 다이아를 찍을 날도 오지 않을까 ..?

[BOJ 13537(P4)리뷰] 유명한 수열과 쿼리 1번문제다. 세그먼트 트리 + 이분탐색을 이용하여 문제를 해결할 수 있다. 세그먼트 트리를 구성할때 각 부모노드들은 자식의 값들을 정렬된 상태로 갖는 형태여서 머지소트 트리 라고도 불리는 것 같다. 이렇게 트리를 구성함으로 우리는 각 구간별 정렬된 값들을 가질 수 있다. 쿼리가 들어오면 구간을 확인한 후에 K보다 큰 값들의 개수를 출력하면 된다. 정렬된 상태이기 때문에 upper_bound를 통해 쉽게 구할 수 있다. 1. 구간에 맞지 않는 경우 2. 구간에 걸친 경우 3. 구간에 완전히 속하는 경우 위 세가지의 경우로 처리하여 반환되는 값들의 합을 출력하면 정답처리를 받을 수 있다. /* 21.01.25 BOJ : 13537 수열과 쿼리 1 (http..

[BOJ 16562(G3)리뷰] 유니온 파인드를 응용하는 문제다. 친구 관계가 주어지고, 같은 관계 안에 있는 친구는 모두 친구로 삼을 수 있다. 이 때, 모든 친구들과 친구가 되기위한 최소비용을 구해야 한다. 유니온파인드 알고리즘에 최소 친구비를 추가하는 로직만 추가해주면된다. 친구 관계를 이어주는것은 일반적인 유니온파인드 과정과 똑같고, 모든 관계에대해 처리를 하고나면 같은 집합의 친구들끼리 묶일것이다. 이때, 각각의 집합의 최소비용을 구하여 모두 더한다음 그 값이 준석이가 가지고있는 돈으로 가능하다면 출력해주면 된다. 나는 기존 union함수에 최소 친구비를 추가하는 코드한줄을 추가했다. 매개변수로 들어온 a,b에 대하여 find함수를 돌리면 결국 그 친구가 속해있는 집합의 번호가 나오므로 굳이 일..

[BOJ 2098(G1)리뷰] 컴퓨터 분야에서 TSP 라고 불리는 굉장히 유명한 문제라고 한다. 한 도시에서 출발하여 N개의 도시를 모두 방문하였을 때 최소비용을 구해야 한다. 처음에 그냥 간단한 최소 스패닝 트리를 구성하는 문제거나, 최단거리를 구하는 문제인 줄 알았는데 모든 도시를 방문해야 하며(방문이 가능할 경우) 다시 도착점으로 돌아와야 한다는 등의 조건때문에 결국 완전탐색을 해야 한다. 하지만 이 문제의 N의 최대값은 16이므로 완전탐색으로 구현하게 되면 16!이라는 어마어마한 시간복잡도를 가지게 된다. 따라서 다이나믹 프로그래밍을 이용하여 시간효율을 증가시켜야 한다. 그리고 이 때, DP를 효율적으로 사용하기 위하여 비트마스킹 이라는 개념을 사용한다. 나도 이 문제에서 처음사용해봤는데 굉장히 ..

[BOJ 1613(G3)리뷰] 플로이드-와셜을 이용한 알고리즘이다. 보통 모든 노드간의 최단거리를 구하는데 사용되지만 이러한 문제에도 응용할 수 있다. 결국 각각의 노드는 모든 노드에 대해 자신과 연결된 노드를 이용하여 노드간의 관계를 정의할 수 있냐 없냐로 나뉜다. 그리하여, 플로이드-와셜 알고리즘을 통하여 모든 연결을 확인하여 연결이 가능한 경우에만 배열에 기록하면 된다. 예를들어, "1 2"라는 입력은 1번사건이 2번사건보다 먼저 일어났다는 의미이다. 이후에 "2 3"이라는 입력이 있다면 1->2->3의 관계를 통해 1번사건이 3번사건보다 먼저 일어났다는것을 알 수 있다. 이렇게 알고리즘을 적용하고나면 연결여부를 기록한 배열에는 각각의 노드마다 자신보다 뒤에 일어난 사건의 번호들의 index를 가지..

[BOJ 9470(G3)리뷰] 처음에 문제 설명만 읽고는 문제를 이해하기 힘들었다. 결국은 위상정렬 문제인데 특별한 조건이 추가된 위상정렬이라고 생각하면 된다. 강이 시작하는 노드(들어오는 간선이 없는 경우)의 순서는 1번부터 시작한다. 입력은 "1 3"이런식으로 주어지는데 1번강에서 3번강으로 물이 흘러나간다는 소리이다. 이 때 들어오는 간선이 존재하는(3번노드) 노드의 정보는 자신에게 들어오는 노드 중 가장 큰 값의 크기에 따라 결정된다. 가장 큰 값이 2개 이상일 경우 이전 강의 값에 +1, 2개 미만일 경우는 이전 강의 정보를 그대로 가진다. 위 조건을 만족하기 위하여 별도의 배열을 만들었다. 해당 번호에 들어오는 물 중 가장 큰 값과, 그 갯수를 저장하는 코드를 추가했다. 나머지는 위상정렬 알고..

[BOJ 11062(G3)리뷰] 언뜻보면 시뮬레이션 문제처럼 보이기도 하고, 그리디 문제처럼 보이기도 하지만 DP문제이다. 항상 가장 오른쪽,왼쪽에 있는 카드만 가능할 수 있다는 점 때문이다. 만약 [1,2,5,2]라는 카드가 있을 때, 근우가 더 큰 2라는 카드를 가져가게 되면 최종 점수는 3점밖에 얻지 못한다. 그 이유는 명우 역시 최선의 전략으로 플레이하기 때문이다. 그렇기에 첫 턴에서 근우가 1이라는 카드를 가져가야 다음턴에 5라는 카드를 가져갈 수 있고 6이라는 최대 점수를 얻을 수 있다. 이렇게 문제를 이해하고 나서도 코드를 짜는게 굉장히 어려웠다. 이걸 어떻게 짜야할까 고민을 많이 했다. 그래서 머리에 구상한 그대로, 근우가 게임을 플레이하는 함수와 명우가 게임을 플레이하는 함수 두개를 구현..

[BOJ 3860(P5)리뷰] 시작점부터 시작하여 목적지까지 도착해야 한다. 묘지가 있는곳으로는 이동할 수 없으며, 귀신 구멍이라는 특정한 칸으로 이동하면 다른 곳으로 시간을 워프하여 이동할 수 있다. 이때 시간을 과거로 되돌릴 수 있다. 인접한 칸을 간선으로 갖고, 귀신 구멍이라는 특별한 간선을 갖는 그래프라고 생각하면 된다. 다만, 과거로 되돌아 갈 수 있다고 했으니 음의 가중치를 갖는 그래프이다. 문제에서 최단거리를 구하라 했으니 최단거리를 구하는 알고리즘을 사용해야 한다. 시작지와 목적지가 주어져 있으므로 다익스트라 알고리즘이 적합하겠지만, 간선에 음의 가중치가 붙을 수 있으므로 벨만포드 알고리즘을 사용해야 한다. 만약 음의 사이클이 존재하면 "Never"를, 음의 사이클은 존재하지 않지만 목적지..

[BOJ 11438(P5)리뷰] 트리에서 두개의 정점이 주어졌을 때, 두 정점의 최소공통조상을 찾아야 한다. 최소 공통조상 이란 두개의 노드가 만나게 되는 부모 노드 중 가장 가까운 것을 말한다. 아래의 과정을 통해 구할 수 있다. dfs를 통해 모든 정점의 깊이를 기록하며 이때 자신의 위에있는 부모노드의 번호를 저장한다. 두개의 정점을 입력받고, 두 정점의 깊이를 맞춘다. 같아진 깊이로부터 위로 올라간다. 이 때, 만약 서로 같은 노드를 만나게되면 그게 최소공통조상이다. LCA 문제는 위 과정을 코드로 구현하면 풀 수 있으나 이 문제는 이방법으로는 풀 수 없다. 왜냐하면, 노드의 개수와 명령의 개수가 최대 10만개이므로 만약 리프노드에서 루트노드까지 찾는과정을 반복해야 한다면 시간초과가 날 수밖에없다...