본문 바로가기
반응형

전체 글1307

[BOJ] 백준 10090 Counting Inversions 출처: https://www.acmicpc.net/problem/10090 Approach 합병 정렬(Merge Sort) 합병 정렬(Merge Sort) Merge Sort 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법 → O(N * logN) - 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다. - 2단계 정복(Conquer) - 해결이 용이한 수준.. zoosso.tistory.com ▷ (4,2) (4,1) (4,3) (2,1) (7,1) (7,5) (7,6) (7,3) (5,3) (6,3) 총 10개 완전탐색의 경우에는 O(N2)으로 TLE 발생. 병합정렬에서 Merge되는 과정을 이용합니다. O(N logN) Inversion 개수 = 1.. 2021. 2. 26.
[BOJ] 백준 2751 수 정렬하기 2 출처: www.acmicpc.net/problem/2751 Approach 합병 정렬(Merge Sort) 합병 정렬(Merge Sort) Merge Sort 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법 → O(N * logN) - 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다. - 2단계 정복(Conquer) - 해결이 용이한 수준.. zoosso.tistory.com 병합 정렬은 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법 - 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다. - 2단계 정복(Conquer) - 해결이 용이한 수준까지 분할된 문제를 해결한다. - 3단계 결합(Combin.. 2021. 2. 26.
[BOJ] 백준 2098 외판원 순회 출처: https://www.acmicpc.net/problem/2098 Approach ※ 비트마스크 (Bitmask) 비트마스크 (Bitmask) 비트마스크 정수의 이진수 표현(Bit)을 자료 구조로 쓰는 기법 현대의 모든 CPU는 이진수를 이용해도 모든 자fy 표현 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 zoosso.tistory.com 완전 탐색으로 접근하는 경우 TLE 발생. ▶ 동적 계획법과 비트마스크 활용. 비트마스크를 이용해 방문한 노드를 표시합니다. ex) 0번과 2번 도시를 방문하였다면 → 0101 표시 → 배열로는 십진법으로 표현하기에 22 + 20 = 5 즉, 어느 도시를 방문했는지를 저장하기 위함. 모든 도시를 방문했다면 1111 = 24 - 1 =.. 2021. 2. 26.
[BOJ] 백준 2174 로봇 시뮬레이션 출처: https://www.acmicpc.net/problem/2174 Input 5 4 2 2 1 1 E 5 4 W 1 F 7 2 F 7 Output Robot 1 crashes into the wall 로봇의 위치와 방향을 아래와 같이 변경하여 표현 명령을 순차적으로 수행하므로, 명령을 수행하는 로봇의 위치에 따라 결과 출력. - 로봇이 F 명령을 수행하면서, 범위밖인지 혹은 다른 로봇과 부딪혔는지 확인합니다. - 방향을 바뀌는 경우, 4의 배수로 회전한다면 1바퀴를 회전하기 때문에 주어진 반복 횟수 % 4 처리합니다. 그 후, 시계 및 반시계 방향에 따른 방향 전환 처리를 해줍니다. #include #include using namespace std; typedef pair XY; typedef .. 2021. 2. 26.
[BOJ] 백준 1592 영식이와 친구들 출처: https://www.acmicpc.net/problem/1592 Input 5 3 2 Output 10 player[]에 공을 받은 횟수 저장합니다. (처음 1번 선수가 받은 공도 횟수에 포함됩니다.) player = [1 0 0 0 0] (※ 인덱스를 1번부터라고 가정) ▶ 공을 3번에게 던진다 → player = [1 0 1 0 0] ▶ 공을 5번에게 던진다 → player = [1 0 1 0 1] ▶ 공을 2번에게 던진다 → player = [1 1 1 0 1] ▶ 공을 4번에게 던진다 → player = [1 1 1 1 1] ▶ 공을 1번에게 던진다 → player = [2 1 1 1 1] ▶ 공을 4번에게 던진다 → player = [2 1 1 2 1] ▶ 공을 2번에게 던진다 → pl.. 2021. 2. 26.
[BOJ] 백준 1526 가장 큰 금민수 출처: https://www.acmicpc.net/problem/1526 Input 100 Output 77 N 이하의 숫자에서 찾는 것이므로 N ~ 1까지 순환하며 4와 7로 이루어진 확인합니다. #include using namespace std; bool is47(int num){ int digit; while (num) { digit = num % 10; if (!(digit == 4 || digit == 7)) return false; num /= 10; } return true; } int main(void){ int N; cin >> N; for (int i = N; i >= 1; i--){ if (is47(i)){ cout 2021. 2. 26.
[BOJ] 백준 9517 아이 러브 크로아티아 출처: https://www.acmicpc.net/problem/9517 Input 5 6 70 T 50 P 30 N 50 T 30 P 80 T Output 7 3분 30초 = 210초로 계산해서 question[]에 대답하기까지 걸리는 시간 answer[]에 대답 종류를 저장하여 시뮬레이션 #include using namespace std; int question[101]; char answer[101]; int main() { int K, N; cin >> K >> N; for (int i = 1; i > question[i] >> answer[i]; } int quizTime = 210; // 3분 30초 // 항상 사람이 폭탄을 들고있었을 때 터지는 입력만 주어지므로 // 문제가 부족한 경우는 .. 2021. 2. 26.
[BOJ] 백준 1022 소용돌이 예쁘게 출력하기 출처: https://www.acmicpc.net/problem/1022 Input -3 -3 2 0 Output 37 36 35 34 38 17 16 15 39 18 5 4 40 19 6 1 41 20 7 8 42 21 22 23 주어지는 r1, c1, r2, c2 있는 그대로 배열을 만들면 메모리가 초과합니다. 문제상에서는 음수로 인덱스가 잡혀있기에 이에 대한 조정이 필요합니다. (r2-r1) × (c2-c1) 크기의 배열을 만듭니다. 음수 인덱스의 경우, (x - r1, y - c1)로 값을 계산해서 (0, 0) ~(r2 - r1, c2 - c1) 영역으로 대체합니다. 결과적으로 x-r1 >=0 && x-r1 =0 && y-c1 > r1 >> c1 >> r2 >> c2; while(!(( map[0.. 2021. 2. 26.
[BOJ] 백준 11657 타임머신 출처: https://www.acmicpc.net/problem/11657 Input 3 4 1 2 4 1 3 3 2 3 -1 3 1 -2 Output 4 3 음수 가중치를 포함하는 유향 그래프에서 최단 거리를 구하는 문제이므로 벨만-포드 (Bellman-Ford) 벨만-포드 (Bellman-Ford) 개념 가중 유향 그래프에서 최단 경로를 구하는 알고리즘입니다. 벨만 포드 알고리즘은 동작원리는 다익스트라(Dijkstra)와 유사합니다. 차이점은 벨만 포드는 음수 가중치가 존재하는 경우에도 zoosso.tistory.com ▷ 음수 사이클을 형성하는 경우 Input 3 4 1 2 4 1 3 3 2 3 -4 3 1 -2 Output -1 Input 3 2 1 2 4 1 2 3 Output 3 -1 ▷ [1.. 2021. 2. 26.
벨만-포드 (Bellman-Ford) 개념 가중 유향 그래프에서 최단 경로를 구하는 알고리즘입니다. 벨만 포드 알고리즘은 동작원리는 다익스트라(Dijkstra)와 유사합니다. 차이점은 벨만 포드는 음수 가중치가 존재하는 경우에도 적용할 수 있으며 시간 복잡도가 O(VE) 입니다. (V: 정점 개수, E: 간선 개수) 다익스트라 알고리즘에서 우선순위 큐를 이용한 방식으로 시간구현하면 시간 복잡도 O(VlogV)이므로 벨만 포드 알고리즘보다 실행속도가 빠릅니다. 다익스트라 알고리즘의 한계 정점 A → C로 갈 때, 두 가지 경로가 존재합니다. ① A → B → C cost: 7 + (-4) = 3 ② A → C cost: 5 결과적으로는 ① 경로가 최단 거리 비용이지만, 다익스트라 알고리즘에서는 정점 [A]와 연결된 정점 [B], [C] 중에서.. 2021. 2. 26.
반응형

티스토리툴바