요즘은 이분탐색 문제를 풀고 있다. 이분탐색은 코드를 짜는것 자체는 어렵지 않지만, 어떤식으로 어떤 값을 탐색해나가야할지를 알아내는 것이 어렵다. 보통, 1억개 연산에 시간이 1초가 걸리기 때문에 이를 고려하여 시간초과가 날 것 같으면 이분탐색을 해야한다. 이 문제 역시, 어떤값을 이분탐색해야할지를 찾지 못해서 다른 사람의 풀이를 참고하였다. https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.n..
백준의 자료구조 문제들을 풀다가 조금 응용이 필요해서 어려운 문제를 발견했다. 풀이가 흥미롭고 좋은 내용이기도 해서 정리해보려 한다. 자료구조 문제들에는 좋은 문제들이 많은 것 같다. 문제를 읽고 힙을 이용해야하는 것 같아서 힙을 이용해 풀긴 했다. 문제를 볼 때부터 시간 제한이 0.1초로 빡센게 느낌이 쎄했는데, 역시나 시간초과로 문제를 틀렸다. 푼 내용 자체는 틀린것같진 않은데 시간 제한에서 걸린 것 같았다. 어떤 풀이를 이용해 풀어야할지 감이 안잡혀서 구글링을 통해 다른 사람의 풀이를 참고해보았다. 풀이가 정말 흥미로웠다. 아래에서 설명해보겠다. https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N..
자료구조 기초 응용 문제이다. 나는 list로 문제를 풀었지만 stack 두개를 가지고도 문제를 풀 수 있다는 걸 다른사람의 풀이를 보고 깨달았다. 커서를 기준으로 왼쪽과 오른쪽을 스택에 넣어 푼다는 점이 흥미로웠다. 간단하지만 은근히 자료구조를 잘 활용해야 풀 수 있다는 점에서 좋은 문제라고 생각했다. https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net #include using namespace std; int mai..
요즘 백준에서 그래프 유형 문제를 많이 풀다보니 그래프 문제를 푸는 실력이 많이 좋아진 것 같다. 카카오 문제를 풀면 괜히 기분이 좋다 ㅎㅎ 문제를 보고 플로이드 와샬 문제라는 것을 깨닫고 풀었는데, 다익스트라로도 좋은 풀이가 있는 것을 보고 정리해보려한다. https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, ..
그래프 문제로 어려운 난이도는 아니지만 좋은 문제 같아서 정리해보려한다. 풀이를 생각하는 과정이 마음에 들었다. https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 마을 안의 도시끼리 한 길로만 연결되고 나머지 길은 없앨 수 있다는 점에서 최소 스패닝 트리를 생각했다. 크루스칼 알고리즘을 사용하여 풀 수 있다. 유지비를 최소로 하기 위해서 정렬 후 유지비가 작은 길부터 크루스칼 알고리즘을 사용하면 된다. 그런데..
예전에 풀어본적이 있던 유형의 문제 같은데 풀이가 잘 생각나지 않았다. 다른 사람의 풀이를 보고 대충 힌트를 얻어 구현했다. https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net #include using namespace std; int n, result = INT_MIN; string s; int cal(int a, int b, char op){ switch(op){ case '+': a += b; break; case '*': ..
dfs를 이용하여 푸는 문제이다. 풀이를 생각해보는데 쉽게 떠오르지 않았다. 고민 끝에 다른사람의 풀이를 참고하였다. https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net #include using namespace std; vector node[10002]; bool visited[10002] = {false,}; int result = 0; int endPoint = 0; void dfs(int p, int len){ if(v..
bfs 문제인데, 조금 응용이 필요한 문제였다. 풀이를 고민하다가 두가지 의문이 풀리지 않아서 다른 사람의 풀이를 참고하여 풀었다. 다음에 비슷한 유형의 문제에서는 잘 풀 수 있었으면 좋겠다. https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 위에서 말한대로 풀지 못했던 두 가지 의문을 다음과 같이 풀었다. 1) 이 문제는 지금껏 풀었던 문제와 다르게 방문했던 곳을 다시 방문할 수도 있다. 열쇠를 구하러 갔다가 다시..