알고리즘 (25) 썸네일형 리스트형 [C++] BOJ-2512 문제풀이 1. 기본적인 binary search(이분탐색 문제) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include using namespace std; int main(){ ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, money, st, end, sum = 0; cin >> N; int arr[N]; for(int i = 0; i> arr[i]; } sort(arr,arr+N); cin >> money; st.. [C++] BOJ-9569 문제풀이 1. 3차원배열에서 bfs를 돌려주는 문제다. 2. 큐에 x,y,z좌표를 넣고 인접해있는 값이 0(익지 않은 토마토)이면 (현재 좌표값) + 1 을 해준 값을 인접하고 있는 배열에 집어넣는다. 3. 이 과정을 반복하여 마지막에 좌표에 넣었던 숫자를 반환한다. 4. 모든 과정이 끝난 후에도 0이 발견되면 -1을 반환한다. 38분 18초 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 7.. [C++] BOJ-1966 문제풀이 1. 중요도를 저장할 수 있는 priority_queue와 (문서의 처음 위치, 중요도)를 저장할 수 있는 queue를 2개 생성한다. 2. 우선순위큐는 가장 높은 우선순위가 top의 위치에 존재하기때문에 우선순위큐의 top과 queue에 있는 요소의 중요도를 체크해서 다르면 큐의 뒤로 넘기고 같으면 pop 한다. 3. pop이 될 때마다 count를 해주고 찾고싶은 문서가 pop이 되면 반복문을 종료한다. #include #include using namespace std; int main(){ int T; cin >> T; for(int test = 0; test < T; test++){ priority_queue pq; queue q; int N,M; int importance; int c.. [C++] BOJ-1932 문제풀이 1. 가장 왼쪽에 있는 숫자와 가장 오른쪽에 있는 숫자는 경우의 수가 하나이기 때문에 바로 위에 배치된 숫자만 더하면 된다. 2. 그 외의 숫자들은 모든 경우의 수를 계산해서 가장 큰 수를 다음 줄에 저장한다. #include #include using namespace std; int main(){ int n; cin >> n; int dp[501][501]; for(int i = 0; i dp[i][j]; } } for(int i = 1; i [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.. 이전 1 2 3 4 다음
