분류 전체보기
BaekJoon 14502번: 연구소
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이법 1) 바이러스가 퍼지는 것을 방지하기 위해 벽을 정확히 3개 세울 수 있다는 것에 유의하며 문제를 풀어야 한다. 2) 8x8 배열이므로 완전 탐색을 진행하였으며 벽을 세우는 것은 dfs 알고리즘을 활용하였다. 3) 벽이 3개 세워진 이후에는 bfs 알고리즘을 활용하여 안전 지대의 크기를 확인하여 문제를 해결하였다. (기존의 입력 값의 배열을 그대로 사용 시에 문제를 해결할 수 없다. 꼭 같은 크기의 배..
BaekJoon 14938번: 서강그라운드(C++)
https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이법 1) 다익스트라를 반복하여 문제를 해결하면 쉽게 풀 수 있는 문제이다. 2) ans라는 배열에 각 start Node로 부터의 거리를 담아 최대 값을 찾으면 해결이 가능하다. #include #include #include #include #include #define INF 987654321 using namespace std; int n, m, r; int arr[101][101]; int ..
BaekJoon 2638번: 치즈(C++)
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이법 1) while 반복을 통해, 빈 배열이 나올때 까지 반복하여 총 걸리는 시간을 확인한다. 2) 치즈의 상태가 담길 배열을 arr, arr2로 두개 선언하였다. 시간이 종료된 후에 한번에 바꾸는 것이 결과값에 영향을 끼치지 않기에 두 개를 선언하여 문제를 해결하였다. 3) visited는 현재 치즈가 있는 배열을 의미하며, visited2는 현재 외부공기를 의미한다. 4) (0..
BaekJoon 11779번: 최소비용 구하기 2(C++)
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이법 1) m개의 반복을 통해 들어갈 값들은 단방향 그래프임을 잊지 말자 2) a에서 b까지 가는 버스의 값이 여러 개 주어질 수도 있다. (min 함수를 활용하여 더 적은 것을 입력 값으로 활용하는 것을 배제하면 7%쯤에서 error가 발생한다.) 3) 다익스트라 알고리즘을 활용하여 최소 비용을 구해야 하는 문제이다. 기존의 다익스트라 문제와 달리 경로를 구해야..
BaekJoon 2573번: 빙산(C++) + 문제 오류
https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제의 예제인 그림 3번에 오류를 발견했다. 그림 3은 다음과 같이 설명되어 있으나 정확한 정답으로는 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 4 0 0 0 0 3 2 0 0 0 0 0 0 0 0 0 0 위의 정답과 같은 세 덩이의 배열이 되어야 한다. 풀이법 1) while 반복을 통해, 덩이의 차이 없이 완전히 녹은 경우를 파악하여 0을 출력해야 한다. (allMe..
BaekJoon 1600번: 말이 되고픈 원숭이(C++)
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이법 1) BFS를 활용하는 문제이며, 문제에서 주어진 w,h 값이 정확히 무엇인지를 먼저 확인하는 것이 중요하다 2) 체스의 knight 처럼 움직일 수 있는 배열과, 상하 좌우로 움직일 수 있는 배열을 따로 만들어 주었다. int vx[4] = { 1,0,0,-1 }; int vy[4] = { 0,1,-1,0 }; int bx[8] = {-1,-2,-2,-1,1,2,2,1};..
BaekJoon 5014번: 스타트링크(C++)
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이법 1) 두개의 배열과 bfs를 활용하면 쉽게 풀 수 있는 문제이다. 2) 현재의 값을 queue에 차근 차근 넣고, now+u>f 일경우 continue로 배열에 넣지 않는다. 3) now-d f >> s >> g >> u >> d; bfs(); }
BaekJoon 7662번: 이중 우선순위 큐(C++)
https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이법 1) 제한시간이 6초이기에 넉넉하다고 생각하여, for문이나 정렬을 하게 되면 무조건 시간 초과가 나는 문제이다. 2) 문제를 해결함에 있어 중복이 가능하고 RBTree의 형태를 가진 set 자료형을 사용하였다. 3) 값을 insert하게 되면 오름차순으로 알아서 정렬이 되기에, set 자료형을 사용한다면 쉽게 문제를 풀 수 있다. set 자료형 사용 시 주의 사항 auto it=set..
BaekJoon 18870번: 좌표 압축(C++)
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이법 1) 두개의 배열을 만들어서 좌표를 압축하기 위해 sort 알고리즘을 두 번 반복하여 문제를 해결했다. 2) 첫번째 입력 값에 대하여, 현재의 값과 index를 담을 수 있는 배열을 만들어 현재의 값을 오름차순으로 정렬시켰다. 3) 두번쨰 배열의 경우, 오름차순 된 첫번째 배열의 크기에 맞게 index를 새로 부여하여 새롭게 만들어야 하는 ..
BaekJoon 1620번: 나는야 포켓몬 마스터 이다솜(C++)
https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이법 1) Map 자료형을 두개 사용하면 쉽게 풀 수 있는 문제이다. 겹치지 않는 string 배열이 두개 있다고 생각하여, map map를 만들어 둠으로서 시간복잡도에서 벗어나지 않게 코딩할 수 있었다. 2) map.count() 함수를 이용하여 해당 key 값에 맞는 value 값이 있는지 확인하여, 입력에 따라 다른 map 자료형에 접근하여 값을 꺼내올 수 있게..