24480번: 알고리즘 수업 - 깊이 우선 탐색 2

24480번:  알고리즘 수업 - 깊이 우선 탐색 2사용 언어: C++ 풀이24479번과 동일한 풀이이지만 sort만 내림차순으로 한다.sort 함수에 greater을 넣어줘서 앞에 수가 뒤에 수보다 크면 true 리턴해서 내림차순으로 sort 된다.#include #include #include using namespace std;vector graph[100001];bool visited[100001];int order[100001];int cnt = 1;void dfs(int node){ visited[node] = true; order[node] = cnt++; sort(graph[node].begin(), graph[node].end(), greater()); for (in..

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

24479번:  알고리즘 수업 - 깊이 우선 탐색 1사용 언어: C++ 풀이무방향 그래프이므로 양쪽 인덱스에 넣어주고, 시작 노드부터 dfs를 돌린다.dfs에서는 visited를 true로 해주고, 방문한 노드의 순서를 order로 저장하고, 오름차순 방문이므로 sort를 하고 다음 인접 노드가 방문하지 않은 노드면 재귀를 돌린다.#include #include #include using namespace std;vector graph[100001]; bool visited[100001]; int order[100001]; int cnt = 1; void dfs(int node) { visited[node] = true; order[nod..

1654번: 랜선 자르기

1654번:  랜선 자르기사용 언어: C++ 풀이 2110번: 공유기 설치와 유사한 문제다. 최소 길이는 1, 최대 길이는 가장 긴 랜선의 길이로 잡는다. 이분 탐색으로 canCut(mid)를 해서 각 랜선을 mid == length 길이만큼 잘라서 나오는 개수가 N개 이상이면 true, 아니면 false. True가 리턴되면 low = mid +1 해서 더 긴 길이가 가능한지 확인하고, false면 high = mid - 1로 더 짧은 길이에서 가능한지 확인한다.다만, 유의할 점은 이 문제는 변수들이 int로 해결이 안된다는 점이다. 문제에서 "랜선의 길이는 2^31보다 작거나 같은 자연수이다." 라고 랜선의 길이가 int 값보다 작다고 주어지긴 하지만, mid = (low + high) / 2를 할 ..

2110번: 공유기 설치

2110번:  공유기 설치사용 언어: C++ 풀이공유기들 사이의 거리를 최대한 크게 둬야하기 때문에 이분 탐색을 생각하면 된다.1) 이분 탐색을 쓰려면 일단 정렬 -> sort2) 공유기 사이의 최대 거리 구하기 최대 거리를 구하려면 일단 첫 번째 집과 마지막 집을 시작과 끝으로 잡고 이분탐색을 시작한다.두 집의 중간 거리 값이 가능한지 canPlaceRouters(거리)를 통해 확인한다. 저 함수에서는 모든 집들 사이에 받은 (거리)만큼 떨어진 집에 설치가 가능한지 확인하고, 설치가 가능하면서 설치한 개수가 총 개수와 같다면 true를 리턴한다.canPlaceRouters가 true라면 low = mid + 1로 mid 거리를 벌려 더 큰 경우가 가능한지 확인하고, 만약  false라면 high = m..

11650번: 좌표 정렬하기

11650번:  좌표 정렬하기사용 언어: C++ 풀이1) struct Point안에서 연산자 오버로딩을 통해 비교 방법을 만들거나,2) bool Compare 함수를 만들어서 포인트들을 비교할 수 있는 방법을 만든다.아래는 오버로딩을 할때 쓸 코드bool operator  아래는 2)로 푼 코드#include using namespace std;struct Point{ int x, y;};bool Compare(const Point &a, const Point &b){ if(a.x != b.x) { return a.x > N; vector V(N); for(int i=0; i> V[i].x; cin >> V[i].y; } sort(V.begi..

18870번: 좌표 압축

18870번:  좌표 압축사용 언어: C++ 풀이 실제로 값들을 비교해서 푸는게 아니라, 값들을 받아서 정렬 후 (중복값도 빼주면서), 정렬하지 않은 배열의 원소가 정렬된 배열의 몇 번째 인덱스인지 알아내면 그 값이 그 원소가 다른 몇 개의 원소보다 큰지 개수다.#include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; int A[N]; for(int i=0; i> A[i]; } vector C; for(int i=0; i

1978번: 소수 찾기 (BOJ C++)

1978번: 소수 찾기 사용 언어: C++ 풀이 아래의 코드는 O(n)이지만, O(루트n)에 코드를 짤 수 있다. 해당 숫자의 루트 n까지만 확인하면 된다는 사실을 사용하는 것이다. for(int i=2; i*i> num; bool flag; while(num--) { int isPrime; flag = true; cin >> isPrime; if(isPrime == 1) continue; for(int i=2; i

1259번: 팰린드롬수 (BOJ C++)

1259번: 팰린드롬수 사용 언어: C++ 풀이 #include #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); stack stack; while(1) { string a; cin >> a; if(a == "0") break; if(a.length() == 1) { cout