PS
BOJ 7576 - 토마토
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net BFS 를 이용해 풀어야 하는 문제이다. 이 문제에서 주의해야될 것은 BFS 의 시작점과 날짜 계산에 대한 부분이다. 단순하게 1이 최초로 나온 좌표 부터 시작해서 쭉 BFS 를 돌리면 제대로 시간계산이 되지 않는다 동일한 날짜에 동시에 1인 여러 좌표에서 부터 시작해서 BFS 를 탐색해야 한다. 예를들면 예제 입력 3 에서 맨 처음 값이 1인 좌표는 (0,0) , (3,5) 이..
BOJ 1697 - 숨바꼭질
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net BFS 를 이용해서 풀어야 하는 문제다. 이전 까지 내가 풀었던 BFS, DFS 문제들은 2차원 배열과 새 x,y 좌표를 위한 dx, dy 배열을 이용해 풀었다면 이 문제는 문제에서 제시된 세가지 식 (x + 1, x - 1, 2 * x) 를 이용해서 BFS 를 돌려야 했다. 그리고 시간에 대한 계산 부분은 큐를 한사이클 돌릴때마다 추가를 해줘야 했다 예를 들면 문..
BOJ 1038 - 감소하는 수
https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 �� www.acmicpc.net 어떤 숫자가 맨 앞자리 부터 맨 끝자리 까지 수가 감소하는 모양이면, 감소하는 수 라 부른다 예를들면, 321, 54321, 620 등 은 감소하는 수 이고, 881, 922 등은 감소하는 수가 아니다. 처음에 이 문제를 풀때는, 수의 범위를 잘못 잡아서 틀렸었다 입력 N 은 N 번째 감소하는 수가 무엇인지 묻는 것인데, #define MAX 1000000 으로 잡고 0 ~ M..
BOJ 11279 - 최대힙, BOJ 1927 - 최소힙
https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net 둘은 구현 방식에 있어서 큰 차이가 있는 문제가 아..
BOJ 2667 - 단지번호 붙이기
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net DFS 를 이용해서 주어진 인접 행렬에서 구분된 구역의 갯수와 구역 내의 원소의 총 갯수를 구하는 문제이다. DFS 에 대한 기본적인 개념을 다지기 좋은 문제이다. - c++ #include #include #include #include using namespace std; int n, cnt; // 총 노드의 수 (5 ~ 25), 갯수 출력 변수 int checked[25][25]; // 방문..
BOJ 1012 - 유기농 배추
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net DFS 를 이용해서 구분된 구역의 총 갯수를 구하는 문제였다. 이 문제를 풀면서 깨달았던 것은 1. 테스트 케이스가 여러개 주어지면 memset 으로 배열 초기화 작업을 해줘야 다음 테스트 케이스에서도 사용이 가능하다. 2. 인접 행렬에 대한 구분 구역의 갯수는 메인 함수에서 구하며, 구역 내에서의 찾고자하는 원소의 총합은 dfs 함수 내에서 구해야한다. 2번에 대한 부분은 BOJ 2667 문제를 풀면 이..
BOJ 1764 - 듣보잡
https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. �� www.acmicpc.net 이 문제를 풀면서 배웠던 두가지가 있는데 첫째는, c++ STL vector 를 사용할때, 초기에 size 를 설정하지 않고 push_back 을 하면 2^n 만큼의 메모리 크기를 잡는다는것. 그래서 resize 를 통해서 미리 크기를 잡아주면 연산 속도도 줄이고, 메모리 크기도 줄일수 있다는 점을 알게 되었다. 둘째는, 코드 작성의 편리성 측면에 근거하여, algorithm header ..
BOJ 3085 - 사탕 게임
https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고 www.acmicpc.net 이 문제는 주의할것이 한가지 있는데, DFS 같은 방식으로 푸는 문제가 아니다. 브루트포스 방식으로 풀어야 하는데, 1. 양옆으로 자리를 바꿨을 때, 2. 위아래로 자리를 바꿨을 때 이 두가지 경우를 고려하면서 코드를 작성해야 한다. 또한 사탕의 갯수를 고려할때, 가로로 계산했을때 최대 몇개인지 세로로 계산했을때 최대 몇개인지를 따져야한다 다만 주의 할 것은 행,열을 빙고처럼 완성하는..