문제BOJ 19598번 : 최소 회의실 개수https://www.acmicpc.net/problem/19598 문제풀이시간 복잡도N이 (1 ≤ N ≤ 100,000) 이므로 O(N^2) 미만으로 풀어야 한다.순회를 할 때 O(N^2)가 안되도록 접근해야 한다.따라서 O(NlgN) 이하의 자료구조를 사용해야 한다. 구현 아이디어처음에 아이디어를 바로 떠올리지 못해서 연습장에 테스트 케이스들을 직접 구성하느라 시간을 20~30분 정도 사용하였다.제약 사향- 동시에 진행되는 회의는 다른 회의실에서 진행해야 한다. - 최소 회의실 수를 구해야 한다. 문제 접근1. 회의실을 최대한 재사용을 많이 해야한다.2. 회의가 끝나는 시간을 추적해서 끝나는 시간보다 시작시간이 더 큰 회의들 중 끝나는 시간에 가장 가까운..
문제BOJ 2573번 : 빙산https://www.acmicpc.net/problem/2573 문제풀이시간 복잡도N x M 2차원 배열이므로 배열 초기화, BFS, DFS 등등 대부분 O(N * M) 정도로 될 것이다.하지만 year만큼 반복하므로 O(N*M*year)라고 볼 수 있다. 구현 아이디어1. 빙산 배열을 여러 번 녹이므로 빙산 배열을 여러 번 돌리기 위한 최외곽 while(1)이 필요2. while문 안에 visit 배열을 선언하여 다음번 while문에 초기화시킨다.3. 빙산 배열을 탐색하는 2중 for문 구성 후 bfs를 안에서 돌린다.4. bfs에서 탐색하면서 0을 마주치면 빙산을 -1 하기5. bfs횟수로 덩어리 계산 및 year 증가 등등 나머지 조건문 => 구현 실패 아이디어 수정녹..
문제BOJ 2667번 : 단지번호붙이기 문제풀이시간복잡도N의 크기가 25 이하완탐으로 풀어도 무방하다. 구현 아이디어(DFS로 풀어도 무방하지만 이미 DFS로 풀어봤던 문제라 BFS로 풀었다.)입력숫자가 붙어있으므로 char로 입력받고 -'0'을 해준다.설계1. 보드입력이 완성된 상태에서 2중 for문으로 방문검사 및 보드검사를 한다.2. bfs에서 4방향 탐색을 통해 방문처리 및 단지 아파트 개수를 카운트한다.3. bfs 함수에서 카운트한 아파트 개수를 리턴한다.4. 리턴 받은 값을 백터에 저장한다.5. 백터를 오름차순으로 정렬하고 백터의 사이즈가 단지개수 이므로 출력하고 아파트 개수를 출력한다. 코드#include#include#include#includeusing namespace std;#defi..
문제BOJ 1697번 : 숨바꼭질https://www.acmicpc.net/problem/1697 BOJ 2606번 : 바이러스https://www.acmicpc.net/problem/2606숨바꼭질 문제풀이시간복잡도N이 100,000이라고 하여 O(NlgN) 이하로 풀어야 한다.일차원 배열 구조라서 BFS를 돌려도 O(N)에 풀 수 있다고 생각하였다. 구현 아이디어뒤로 한 칸 or 앞으로 한 칸 or 2배 순간이동처음 수빈이의 위치에서 시작하여 수빈이가 갈 수 있는 곳을 BFS를 돌리면 끝난다.처음 시작이 5라면 큐에 4, 6, 10을 넣고 기존 노드의 값에서 +1을 해준다. 그러면 4, 6, 10에는 2가 들어가고 4에서 뒤로, 앞으로, 순간이동을 또 큐에 넣게 되면 자동으로 동생으로까지의 최단경로..
문제BOJ 1260 DFS와 BFShttps://www.acmicpc.net/problem/1260 문제풀이시간 복잡도노드의 수 (N) : 최대 1,000간선의 수 (M) : 최대 10,0001,000 * 1,000 = 1,000,000따라서 O(N^2)의 DFS와 BFS를 구현하더라도 충분이 넉넉한 시간이다. 구현 아이디어1. 이차원 배열을 사용하여 그래프를 인접 행렬로 표현하기 - node_matrix[a][b] = 1, node_matrix[b][a] = 1로 간선 표시하기2. DFS를 구현할 때 재귀함수 사용하기 - 노드 방문 처리 - 현재 노드와 연결된 모든 노드를 순서대로 확인하기 - 연결되어 있고 방문하지 않은 노드 재귀 호출3. BFS를 구현할 때 큐 사용하기 -..
문제BOJ 2470 두 용액https://www.acmicpc.net/problem/2470 문제풀이 시간복잡도 고려하기N이 100,000 이므로 O(NlgN) 미만의 접근 방식을 사용해야한다.따라서 보자 마자 떠오른 O(N^2)의 사고는 접어두고 다른 풀이를 떠올렸다. 구현 아이디어어제 푼 문제와는 조금 다른 유형이지만 이분 탐색의 개념만 빌려쓰는 느낌이다.아마 투 포인터를 사용하면 조금 더 쉽게 풀리고 시간 복잡도도 O(N)으로 풀 릴 것이다.하지만 99클럽에서 이번주는 이분 탐색으로 문제를 계속 주는 것으로 보아 이분 탐색으로 풀어보라는 의도 인것 같아서 이분 탐색으로 풀었다.문제 접근1. 배열 정렬 2. 배열을 순회하면서 합이 0에 가장 가까운 다른 용액을 이분 탐색으로 찾는다. 3. arr[..
문제BOJ 2343번 기타 레슨https://www.acmicpc.net/problem/2343 문제풀이시간복잡도 고려하기N의 최댓값이 100,000이므로 O(NlgN)으로 풀어야 한다. 구현 아이디어제약 조건1. 정렬되어 있지 않은 벡터를 순서대로 더해야 한다.2. M개를 모두 사용해야 한다.3. 모든 블루레이의 크기가 동일해야 한다.???이분 탐색을 4일째 풀고 있지만 이번에는 아이디어가 좀처럼 떠오르지 않았다.단순히 강의가 들어있는 크기가 N인 벡터를 이분탐색하면 정렬되어 있지 않기 때문에 답이 나오지 않는다.일단 STL을 활용하여 쓸 수는 없으므로 직접 이분탐색을 구현해야 하고 이분탐색을 할 대상은 강의의 길이를 저장한 벡터가 아니라는 것은 알아냈다.강의 길이의 합을 이분탐색하기이분탐색 시작점 ..
문제BOJ 11663번 선분 위의 점https://www.acmicpc.net/problem/11663 문제풀이시간복잡도 고려하기N의 최댓값이 100000이므로 O(NlgN)의 풀이로 풀어야 한다. O(N^2)의 풀이인 배열탐색으로는 시간초과가 발생한다. 따라서 이분탐색을 활용해서 풀어야 한다. 구현 아이디어주어진 조건 1. 크기가 N인 탐색할 배열 또는 벡터2. 탐색 범위 (선분 시작점, 선분 끝점)3. 범위 내 조건을 만족하는 개수를 구해야 한다.STL 활용binary_search() 함수는 벡터 안에 값이 있는지 없는지만 알려주므로 딱히 도움이 되지 않는다.lower_bound() 함수는 벡터에서 찾고자 하는 값보다 작지 않은 첫 번째 요소를 가리키는 iterator를 반환한다.upper_boun..
