전체 글 (29) 썸네일형 리스트형 [C++] BOJ-1931 문제풀이 1. vector에 회의실 시작시간과 끝나는 시간을 저장한다 2. 이 때 시작시간을 second, 끝나는 시간을 first에 저장해야한다. 왜냐하면 끝나는 시간을 기준으로 정렬을 해야하기 때문이다. 3. 회의가 끝나는 시간과 그 다음으로 빨리 끝나는 회의를 찾아서 회의시간이 겹치지 않는다면 count 해준다. #include #include #include using namespace std; int main(){ ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector v; int N; int a,b; cin >> N; for(int i = 0; i> a >> b; v.push_back(make_pair(.. [C++] BOJ-1916 문제풀이 1. 단방향 그래프를 만들고 다익스트라 알고리즘을 수행하면 된다. 2. 시작지점(src)를 다익스트라 함수에 넘겨주고 dist 배열에 각 도시의 최단경로를 저장한다. 3. 원하는 도착점으로 가는 최단경로를 출력한다. #include #include #include using namespace std; int N, M; int src, des; const int INF = 987654321; vector adj[1001]; vector dijkstra(int src){ vector dist(N, INF); dist[src] = 0; priority_queue pq; pq.push(make_pair(0,src)); while(!pq.empty()){ int cost = pq.top().first; .. [C++] BOJ-1699 문제풀이 1. cache배열의 인덱스 값을 제곱수로 생각하고 점화식을 구현하였다. cache[j] = min(cache[j], cache[j-dp_pow(i)]+1) 2. 전체 소스 #include using namespace std; int dp_pow(int a){ return a*a; } int main(){ ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; int cache[N+1] = {}; for(int i = 1; i [C++] BOJ-1654 문제풀이 1. 이분탐색 문제이다. 숫자의 범위가 int형이 훨씬 넘어가니 long long 형을 써야한다. 2. 가장 큰 랜선을 기준으로 시작하여 이분탐색으로 필요한 랜선의 수에 맞는 최적의 길이를 찾아야한다. 3. sum이 N보다 크거나 같으면 start = mid + 1, 그렇지 않으면 end = mid-1이 되게하여 점차 범위를 줄여나가는 방식으로 접근했다. #include using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); long long K,N; cin >> K >> N; long long wire[10000]; long long start = 1, end, mid; long long result = 0; for.. [C++] BOJ-1520 문제풀이 1. 백트래킹 + DP를 이용해서 풀었다. 2. 재귀함수를 통해 모든 경우의 수를 백트래킹으로 탐색하지만 그 중에서 이미 탐색했던 부분이 있으면 그 곳은 다시 탐색하지 않는다. 3. 좌표(N,M)에 도착하면 결과값에 return값에 1씩 더해준다. #include #include using namespace std; int dx[4] = {0,0,-1,1}; // 상하좌우 int dy[4] = {1,-1,0,0}; int arr[500][500]; int cache[500][500]; int N,M; int func(int x, int y){ if(cache[x][y] != -1) return cache[x][y]; if(x == M-1 && y == N-1) return 1; cache[x][.. [C++] BOJ-1238 문제풀이 1. vector에 단방향 그래프를 입력받는다. 2. 파티에 갈 때와 올 때의 길이 다를 수 있기 때문데 (집 -> 파티), (파티-> 집) 을 따로 다익스트라 알고리즘을 통해 최단경로를 수해야한다. 3. 그 경로의 합 중에서 최소를 구한다. #include #include #include #include using namespace std; const int INF = 987654321; int N,M,X; vector adj[1001]; int dijkstra(int start, int end){ vector dist(N,INF); dist[start] = 0; priority_queue pq; pq.push(make_pair(0,start)); while(!pq.empty()){ int c.. [C++] BOJ-1012 문제풀이 1. sort를 사용해서 vector를 정렬. 2. unique를 사용해서 중복이 되는 요소를 맨 뒤로 넘긴다. 3. 맨 뒤로 넘어간 중복되는 요소들을 삭제하고 출력한다. #include #include #include #include using namespace std; bool compare(string &s1, string &s2){ if(s1.size() == s2.size()){ return s1 > N; vector str; for(int i = 0; i.. [C++] BOJ-1012 문제풀이 기본적인 Queue 문제 #include #include #include using namespace std; int main(){ ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); queue q; int N, M; cin >> N >> M; for(int i = 0; i 이전 1 2 3 4 다음
