본문 바로가기

알고리즘10

[BOJ] 1238 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 www.acmicpc.net 다익스트라 문제.. 이 문제를 이전에는 인접 행렬로 풀었었는데 N = 1000이기 때문에 인접 행렬은 총 1,000,000개의 int 변수가 필요하다. 하지만 총 간선의 개수가 10000개 이하로 정해져있기 때문에 인접 행렬보다는 인접 리스트가 메모리상 효율적이고 시간복잡도 상에서도 더욱 효율적이다. 좀 더 최적화적인 관점에서 문제를 바라볼 필요가 있겠다. 그리고, C++은 기본적으로 우선순.. 2020. 5. 22.
[BOJ] 1238 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 www.acmicpc.net 플로이드 워셜이나 다익스트라 알고리즘을 사용하면 되는 문제 중요한건 다익스트라를 거꾸로 오는 경로로 생각했어야 했다. 그렇지 않으면 시간초과난다!!!!! #include #include #include #include #include #define INF 1000000 using namespace std; int N, M, X; int adj[1001][1001]; priority_queue.. 2020. 5. 22.
[BOJ] 16235번 나무 재테크 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 시뮬레이션 문제 문제를 잘 읽고 이를 시각화 시키는 연습이 필요할 것 같다. 조급해 하지 말고 문제 집중해서 제대로 읽기 #include #include #include using namespace std; int N, M, K; int A[11][11]; int map[11][11]; vector tree[11][11]; int dx[] = { -1,-1,-1,0,0,1,1,1 .. 2020. 5. 21.
[SWEA] 점심 식사시간 조합, 우선순위 큐를 사용하여 풀었다. 주의해야 할 점은 조합을 구할 때 기저 값 넘겨주는 것 그리고 정확하게 진행되는 상황을 종이에 써서 명확히 이해하고 코딩할것 !!!!!!!!!!!!! #include #include #include #include #include #include using namespace std; int T, N, answer; vector peoples; vector stairs; vector dist[2]; vector stairVal; void solution(int selected) { priority_queue pq[2]; for (int i = 0; i < peoples.size(); i++) { if (selected & (1 = 3) continue; count++.. 2020. 5. 13.
[BOJ] 17471번 게리멘더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 1번부터 N번까지 번호가 매겨진 N개의 구역이 있다. 구역을 두 개의 선거구로 나누고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 한다. 인구 차이의 최솟값을 구해보자 풀이 비트마스킹을 이용한 부분집합 + BFS를 이용하여.. 2020. 4. 28.
[BOJ] 17822번 원판 돌리기 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j www.acmicpc.net 작년 하반기 삼성 기출문제 주사위 윷놀이와 같이 나온 문제로 알고 있는데, 이것도 2달 전에 풀었는데 반례를 찾지 못해서 방치했다.. 2020. 4. 28.

티스토리툴바