코딩테스트/백준_골드
-
[문제] 14502번: 연구소 (acmicpc.net) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [문제 풀이] n * m의 공간인 연구소에 바이러스가 퍼졌다. 2인 칸에서 부터 바이러스는 퍼지고 벽(1)의 부딪히거나 범위에 부딪히면 더 이상 퍼지지 못한다. 3개의 벽을 추가로 건설해서 바이러스를 최대한 덜 퍼트펴보자. 벽은 무조건 3개이고 0인 곳에 세울 수 있다. 그러니 0인 칸의 모든 좌표값을 알고 있을 때 이 중 3가지를 뽑아서 나올 수 있는 경우의 수가 문제에서 요구하는 거라고 봐도 무방할 것이다. 백준 n과..
[C++][백준 14502] 연구소[문제] 14502번: 연구소 (acmicpc.net) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [문제 풀이] n * m의 공간인 연구소에 바이러스가 퍼졌다. 2인 칸에서 부터 바이러스는 퍼지고 벽(1)의 부딪히거나 범위에 부딪히면 더 이상 퍼지지 못한다. 3개의 벽을 추가로 건설해서 바이러스를 최대한 덜 퍼트펴보자. 벽은 무조건 3개이고 0인 곳에 세울 수 있다. 그러니 0인 칸의 모든 좌표값을 알고 있을 때 이 중 3가지를 뽑아서 나올 수 있는 경우의 수가 문제에서 요구하는 거라고 봐도 무방할 것이다. 백준 n과..
2023.09.16 -
[문제] 14503번: 로봇 청소기 (acmicpc.net) 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net [문제 풀이] 방향을 고려하면서 청소기를 계속 이동시키는 시뮬레이션 문제이다. 보통 일반적으로 int dx[4] = {0,1,0,-1} 같이 쓰는 배열에서 방향이 중요한 문제. //북 동 남 서 int dx[4] = {-1,0,1,0}; int dy[4] = {0,1,0,-1}; 이번 문제에서는 이와 같이 두고 풀었다. dx는 y축 dy는 x축의 위치를 ..
[C++][백준 14503] 로봇 청소기[문제] 14503번: 로봇 청소기 (acmicpc.net) 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net [문제 풀이] 방향을 고려하면서 청소기를 계속 이동시키는 시뮬레이션 문제이다. 보통 일반적으로 int dx[4] = {0,1,0,-1} 같이 쓰는 배열에서 방향이 중요한 문제. //북 동 남 서 int dx[4] = {-1,0,1,0}; int dy[4] = {0,1,0,-1}; 이번 문제에서는 이와 같이 두고 풀었다. dx는 y축 dy는 x축의 위치를 ..
2023.09.07 -
[문제] 9205번: 맥주 마시면서 걸어가기 (acmicpc.net) 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net [문제 풀이] home에서 출발해서 거리가 1,000이하가 될때까지 갈수있는 편의점을 들리다가 rock 페스티벌 장소에 거리가 1,000이하가 되면 happy를 아니면 sad를 출력하는 문제이다. BFS를 이용해서 해당 문제를 풀도록 하자. home의 위치를 큐에 넣어주고 해당 큐에서 편의점 0번부터 n -1 번까지 돌아다니면서 아직 방문하지 않았고 거리가 1,000이하라면 해당 편의점을..
[C++][백준 9205] 맥주 마시면서 걸어가기[문제] 9205번: 맥주 마시면서 걸어가기 (acmicpc.net) 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net [문제 풀이] home에서 출발해서 거리가 1,000이하가 될때까지 갈수있는 편의점을 들리다가 rock 페스티벌 장소에 거리가 1,000이하가 되면 happy를 아니면 sad를 출력하는 문제이다. BFS를 이용해서 해당 문제를 풀도록 하자. home의 위치를 큐에 넣어주고 해당 큐에서 편의점 0번부터 n -1 번까지 돌아다니면서 아직 방문하지 않았고 거리가 1,000이하라면 해당 편의점을..
2023.09.06 -
[문제] 2573번: 빙산 (acmicpc.net) 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net [문제 풀이] 근처에 0이 있는 수만큼 양수가 줄어들 때(단 0이하로는 안 내려간다) 몇번을 반복해야 1번의 BFS / DFS로 모든 양수를 방문을 못하는지 알아보는 문제이다. 여기서는 BFS를 이용해서 문제를 풀었다. 해당 문제를 풀기 위해 크게 2개의 함수를 통해 조건을 나누었다. 1. 양수들을 방문하면서 근처에 있는 0의 수만큼 줄어들게 만드는 함수. 2. BFS를 이용했을때 한번에 모든 양수를 방문..
[C++][백준 2573] 빙산[문제] 2573번: 빙산 (acmicpc.net) 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net [문제 풀이] 근처에 0이 있는 수만큼 양수가 줄어들 때(단 0이하로는 안 내려간다) 몇번을 반복해야 1번의 BFS / DFS로 모든 양수를 방문을 못하는지 알아보는 문제이다. 여기서는 BFS를 이용해서 문제를 풀었다. 해당 문제를 풀기 위해 크게 2개의 함수를 통해 조건을 나누었다. 1. 양수들을 방문하면서 근처에 있는 0의 수만큼 줄어들게 만드는 함수. 2. BFS를 이용했을때 한번에 모든 양수를 방문..
2023.09.06 -
[문제] 17144번: 미세먼지 안녕! (acmicpc.net) 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net [문제 풀이] 시뮬레이션 문제이다. 문제에서 주어진 조건은 크게 1. 먼지를 확산 시켜라. 2. 공기청정기 바람을 이용해서 배열을 돌려라. 의 2가지 조건이다. 지문이 길다고 어려운것이 아니니 1번부터 천천히 해보자. 1번의 조건을 나눠보면 크게 a. 공기청정기로 가면 안된다. b. 범위내에서 이루어져야 한다. c. 독립적으로 영향을 준다. 의 3가지로 나눌 수 있다. a번과 b번은 여태까지 다른 ..
[C++] 미세먼지 안녕![문제] 17144번: 미세먼지 안녕! (acmicpc.net) 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net [문제 풀이] 시뮬레이션 문제이다. 문제에서 주어진 조건은 크게 1. 먼지를 확산 시켜라. 2. 공기청정기 바람을 이용해서 배열을 돌려라. 의 2가지 조건이다. 지문이 길다고 어려운것이 아니니 1번부터 천천히 해보자. 1번의 조건을 나눠보면 크게 a. 공기청정기로 가면 안된다. b. 범위내에서 이루어져야 한다. c. 독립적으로 영향을 준다. 의 3가지로 나눌 수 있다. a번과 b번은 여태까지 다른 ..
2023.09.05 -
[문제] 1062번: 가르침 (acmicpc.net) 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net [문제 풀이] 백트래킹을 이용해서 문자열을 만족할 수 있는지를 파악하는 문제였다. k가 만약에 5개 미만이라면 anta, tica 조차 만들 수 없으니 당연히 0을 반환하도록 하고 5개 이상이라면 visited배열을 이용해서 a, c, i, n, t 5개를 모두 1로 바꾼뒤에 백트래킹을 이용해서 조합을 만들면서 다른 알파벳들을 방문처리 하고 입력받은 string들이 모두 visited배열에서 방문을 했..
[C++][백준 1062] 가르침[문제] 1062번: 가르침 (acmicpc.net) 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net [문제 풀이] 백트래킹을 이용해서 문자열을 만족할 수 있는지를 파악하는 문제였다. k가 만약에 5개 미만이라면 anta, tica 조차 만들 수 없으니 당연히 0을 반환하도록 하고 5개 이상이라면 visited배열을 이용해서 a, c, i, n, t 5개를 모두 1로 바꾼뒤에 백트래킹을 이용해서 조합을 만들면서 다른 알파벳들을 방문처리 하고 입력받은 string들이 모두 visited배열에서 방문을 했..
2023.04.15