[백준 / 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++ 2차원 벡터 동적 할당 사용법

그래프 문제를 풀 때 노드의 개수 N의 범위가 매우 크면 벡터의 크기를 함부로 설정하기가 난감하다. vector graph[100000]; 와 같이 할당하면 N = 10처럼 노드의 개수가 적은 경우에 메모리 낭비가 되고, 그렇다고 vector graph[10]; 처럼 작게 할당해버리면 N의 범위가 큰 경우에는 범위를 초과해버리기 때문이다. 따라서 vector의 2차원 동적 할당을 이용해 그래프를 만들어준다. vector v; 2차원 벡터란 위와 같이 벡터 안에 벡터를 또 집어 넣는 것이다. 이렇게 하면 v의 행과 열 범위를 동적으로 만들 수 있다. N개의 노드가 있고 M개의 간선이 있는 무방향 그래프가 있다고 해보자. 아래는 N과 M을 입력 받아 M개의 간선 정보를 통해 그래프를 그리는 예시이다. #in..

• format_list_bulleted C++
• · 2023. 8. 15.
• 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