본문 바로가기

전체 글

 (147)
백준 2418: 해밍 경로 https://www.acmicpc.net/problem/2481 이 문제는 한 눈에 보아도 너비 우선 탐색을 사용해야한다.문제는 해밍 거리가 1인 이진수 코드를 그래프로 그리는 법이다.반복문을 두 번 돌려서 그래프를 그리는 방법이 먼저 생각나지만, N이 100,000까지 올라가서 시간 초과가 날 것은 뻔하다. 그렇다면 1의 갯수로 각 이진수 코드를 분류한뒤, BFS를 돌 때 (현재의 이진수 코드의 1의 갯수 + i (-1 예로 K가 최대 30일 때, 1의 갯수가 15개인 그룹은 30C15 가지의 가능성이 있는데, 이 갯수는 굉장히 많다. 그렇다면 다른 방식을 찾아야한다. 그렇게 떠오른 것이, HashMap을 사용하는 것이다. 먼저 Queue에 String을 넣고, BFS를 돌며, 현재 값을 한 번씩 변..
백준 1626: 두 번째로 작은 스패닝 트리 https://www.acmicpc.net/problem/1626 지금까지 다이아 5가 푼 문제 중 최고 난이도였던 내가, 다이아 4인 이 문제를 도전하게 된 것은 의외의 계기가 있었다.https://www.acmicpc.net/problem/15481이 문제를 해결하기 위해서, 아이디어를 하나 떠올렸는데, 마침 이 문제에 적용할 수 있을 것 같아서 도전을 하게 되었다.  당시 아이디어는 이러하다.각 간선 하나를 미리 Union해서 MST 알고리즘을 돌리면 문제를 해결할 수 있을 것 같은데, 그러면 십중팔구 시간초과가 발생할 것이다. 그렇다면, 어떻게 해결해야할까?각 간선의 길이와 번호는 동일하다고 하자. 이 문제의 MST는 1, 2, 3번 간선을 이으면 된다.그런데, 4번 간선을 연결한 MST는 어떨까..
백준 14391: 종이 조각 https://www.acmicpc.net/problem/14391 이 문제는 몇 번 마주했지만, 도저히 답을 떠올릴 수가 없어서, 계속 넘어갔었다.N과 M이 4 이하의 자연수라서 Bruteforce를 사용하는 것은 명백한데, 어떻게 해야할지 감이 잡히지 않았다.문득, 알고리즘 태그에 눈이 갔는데, 비트마스크 사용을 장려해서 비트마스크를 어떻게 사용하면 될까?에서부터 고민을 시작했다. 그러자, 하나 아이디어가 떠올랐다. 종이를 자르는 방법은 가로로 자르거나 세로로 자르거나 둘 중 하나이다. 그렇다면, 각 종이를 자르는 방식을 비트마스크로 나타낼 수가 있다. 이 방법의 문제는 가로로 연속으로 자르거나, 세로로 연속으로 자르는 방식은 나타낼 수 없는다는 점인데, 이 문제의 답은 합의 최대이기 때문에 연속으로..
백준 1328: 고층 빌딩 https://www.acmicpc.net/problem/1328 이 문제는 마주칠때마다 몇 번을 도전했었고, 이제서야 답안을 떠올릴 정도로 난이도가 있는 DP 문제다.최근에 해결한 DP 문제는 골드 수준이였지만, 이 문제는 간만의 플레티넘 문제여서 아이디어를 떠올리기 힘들었다. 모든 높이는 1과 N 사이고, 같은 높이를 가지면 안되므로 1부터 시작해 빌딩의 위치를 정하면 된다.만약 현재의 빌딩 높이가 h라면, 가장 왼쪽에 두었을 경우, 가장 오른쪽에 두었을 경우, 다른 빌딩에 숨겨진 경우를 구하면 된다. 그렇다면 가운데를 기준으로 가장 큰 빌딩부터 순서대로 다른 경우의 수를 구하면 문제가 해결된다.사실 여기까지는 그렇게 어렵지 않았다. 하지만, 문제는 "다른 빌딩에 숨겨진 경우" 였다. 이것을 어떻게 ..
백준 1119: 그래프 https://www.acmicpc.net/problem/1119 이 문제는 보자마자 숨이 턱 막혔었다.도대체 어떻게 풀어야할지 감이 전혀 잡히지 않았다.분리 집합을 사용하려해도, 분리집합에선 집합 연결을 끊는 것까지 배우지 않아서, 이 방법은 폐기했고, DFS로 순회하며 BruteForce를 사용하려 해도, 구현이 힘들것 같았기에 다른 방법을 찾아야만 했다. 그렇기에, 일단 나는 처음으로 돌아가보도록 했다. 방법을 구하는 게 아니라, 도로를 수정할 경우 합쳐지는 경우가 어떤것인지 생각을 해보았다. 일단 처음 생각한 예제는 다음과 같았다.이 그래프는 아무리 도로를 수정해보아도, 하나로 연결될 수가 없었다. 그러면 여기서 어떻게 도로를 변경했을 때, 하나의 집합으로 만들수 있을까?로 생각을 옮기자, 다른 ..
백준 2378: 불필요한 수 https://www.acmicpc.net/problem/2378 비록 골드 3의 난이도지만, 이 문제를 풀기 위해서, 하루이틀 동안 많은 생각을 했고 드디어 스스로 해결을 하였다.많은 시도를 한 문제지만 처음엔 그냥 단순하게 생각했다. 아무 생각없이, 각 난수의 계수들은 1,2,3,4,5,6... 순서대로 올라가다, 내려가는 형태일 것이라고 생각했고, 각 계수가 M으로 나누어질 때, 그것이 답이다라 생각하며, 그냥 그대로 코드를 제출했다.#include #include using namespace std;vector ans;int N, M, R[100001];int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin ..
백준 17371: 이사 https://www.acmicpc.net/problem/17371 이 문제는 몇 번 맞닥뜨렸지만, 예제를 보고, 내가 모르는 공식이 있어서 풀기 어려울거라 생각해서 계속 넘어갔었다.그런데 오늘, 다시 마주했을 때, 풀 수 있을 것 같다는 자신감이 갑자기 생겨서, 풀이를 고민하였다. 일단 예제에선 소수가 눈에 띄는데, 내가 아는 알고리즘 내에서 이 문제에 적용할 수 있고, 소수가 사용되는 것으로 이분 탐색이 막연히 떠올랐다. 그런데, 문제의 분류를 보니 "스페셜 저지"가 보였다. 즉, 예제의 답은 많은 답 중 하나일 것이다. 란 생각에 이르렀고, 만약 이 문제가 내가 아는 공식 내에서 풀 수 있는 문제라면, 단순하게 생각을 해보자까지 이르렀다. 다시 말해서이 예제는 혼선을 주기 위한 페이크이고, 단순한 ..
백준 1687: 행렬 찾기 https://www.acmicpc.net/problem/1687 이 문제에서의 반성점은 내가 너무 낙관적이란 점이였다.4중 for문을 사용해서 두 점 사이의 0의 갯수를 구하면, 시간초과가 될 것이 뻔한데, 가지치기하면 어떻게든 되지 않을까? 란 너무 낙관적인 생각으로 인해 이 문제를 틀렸다. 내가 너무 가지치기를 과대평가했다.. #include using namespace std;int N, M, A = 0, ans = 0;int G[335][335];char ch;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; for(int i = 1; i > ch; G[i][j] = G[i - ..

티스토리툴바