[백준 / C++] 17144번: 미세먼지 안녕! (삼성 SW 역량 테스트 기출)

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 난이도: solved.ac 골드 4 구현 방법 각 1초 동안 진행되는 과정은 T를 1씩 줄여나가며 T가 0이 될 때까지 진행해주었다. (while(T--) {...} 방식으로) 미세먼지를 확산하는 과정에서 확산으로 인한 값의 변화 때문에 미세먼지 상태를 나타내는 배열은 단 하나만으로는 부족한데, 따라서 배열을 두 개 이용했다. 각 확산된 값을 임시 배열에 저장했다가 다시 원래 배열로 복사하는 식..

• format_list_bulleted PS/백준
• · 2023. 9. 3.
• textsms

[백준 / C++] 21608번: 상어 초등학교 (삼성 SW 역량 테스트 기출)

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 난이도: solved.ac 골드 5 구현 방법 문제에서 주어진 세 가지 조건 그대로 구현하면 되는 문제다. 먼저 첫 번째 조건을 살펴보자. "비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다." 이를 구현하기 위해 학생들을 배치할 공간 board[N][N]을 만들고, board가 0인 모든 빈자리를 기준으로 인접한 상하좌우 캉을 탐색해 좋아하는 학생이 몇 ..

• format_list_bulleted PS/백준
• · 2023. 8. 28.
• textsms

[백준 / C++] 2206번: 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 난이도: solved.ac 골드 3 알고리즘 분류 그래프 탐색, 너비 우선 탐색(BFS) 접근 방법 지금까지 풀었던 BFS 문제에서 사용했던 visited 배열에 한 차원을 더 추가시켜 벽을 부순 적이 없는 상태에서의 방문 표시는 visited[][][0]에 나타내고, 벽을 부순 적이 있는 상태에서의 방문 표시는 visited[][][1]에 나타내었다. 큐에는 현재 위치 ..

• format_list_bulleted PS/백준
• · 2023. 8. 17.
• textsms

[백준 / C++] 1238번: 파티

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 난이도: solved.ac 골드 3 알고리즘 분류 그래프 이론, 데이크스트라 (Dijkstra) 접근 방법 (풀이 1) 먼저 각 노드 i에서 X로의 최단 거리를 파악하기 위해 모든 노드에 대해 다익스트라 알고리즘을 N번 사용한다. 그리고 dist[X]의 결과를 ans[i]에 저장한다. 그 다음 X에서 다른 모든 노드로의 최단 거리를 파악하는 X를 기준으로 한 다익스트..

• format_list_bulleted PS/백준
• · 2023. 8. 15.
• textsms

[백준 / C++] 1629번: 곱셈 (그리디 풀이...?)

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 난이도: solved.ac 실버 1 분할 정복(Divide and Conquer)을 이용해 푸신 분들이 많던데 나는 그리디(?)로 풀어보았다. A를 B번 곱하는 것은 A의 B승을 구하라는 것과 같다. 따라서 A를 A^B로 만들어주기로 했다. A는 A^1이다. A^1을 A^B로 만드는 과정은 1을 B로 만드는 과정과 같다. 우선 거듭제곱의 성질 중 a^b * a^b = a^(2b) 를 알아야 한다. 2^3 * 2^3 = 2^6 (8 * 8 = 64)을 떠올리면 이..

• format_list_bulleted PS/백준
• · 2023. 8. 14.
• textsms

[백준 / C++] 11660번: 구간 합 구하기 5

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 다이나믹 프로그래밍 (dp), 누적 합 (prefix sum) 접근 방법 각 행 별로 1열부터의 누적 합으로 배열에 저장한다. Ex. sum[3][5] = (3,1)부터 (3,5)까지의 합 sum[4][7] = (4,1)부터 (4,7)까지의 합 그리고 x1, y1, x2, y2를 입력받아 (x1, y1)부..

• format_list_bulleted PS/백준
• · 2023. 8. 8.
• textsms