Dev:P

문제 이번에 다뤄볼 문제는 1697번 문제 '숨바꼭질'입니다. 숨바꼭질 문제에서 연습해야하는 key-point는 큐입니다. 큐(queue)란 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 뜻합니다. visited라는 배열을 하나 만들어 방문 된 위치는 재탐색을 하지 않도록 하였습니다. 그리고 큐를 활용하여 문제를 해결하였는데요. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include using namespace std; int visited[100001]; int q[100001]; int front = 0, rear = 0; int tmp_f = 0, tmp_r = 0; ..

문제 이번에 다뤄볼 문제는 2468번 문제 '안전 영역'입니다. 안전 영역 문제에서 연습해야하는key-point는재귀함수입니다. 재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업울 수행하는 방식의 함수를 뜻합니다. real_map과 map 이라는 2차원 배열을 두개 만들어 map의 값은 영역 체크가 끝나게 되면 0으로 바꿔주어 다시 탐색하지 않도록 하기 위함이고 real_map의 경우 처음 들어온 초기값을 유지하고 있는 2차원 배열입니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include using namespace std; int real_map[101][101]; int map[101][101]; int dirX[4] = { 0, 0, 1, -1 }; int ..

문제 이번에 다뤄볼 문제는 1012번 문제 '유기농 배추'입니다. 유기농 배추 문제에서 연습해야하는 key-point는재귀함수입니다. 재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업울 수행하는 방식의 함수를 뜻합니다. 배추가 최초 확인 되었을 경우 b_count값을 증가시켜준뒤 재귀로 들어가 인접한 배추들을 다시 탐색하지 않도록 2로 값을 바꿔줍니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include using namespace std; int map[51][51] = {0}; int dirX[4] = {0,0,-1,1}; int dirY[4] = {-1,1,0,0}; int xx = 0, yy = 0; int t, m, n, k; int b_count = 0;..

문제 이번에 다뤄볼 문제는 4963번 문제 '섬의 개수'입니다. 섬의 개수 문제에서 연습해야하는 key-point는 재귀함수입니다. 재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업울 수행하는 방식의 함수를 뜻합니다. 문제를 읽어봤을때 한 정사각형과 가로, 세로 또는 대각선으로 가는 방향 까지도 고려해야 하므로 총 8가지 방향을 탐색하게 합니다. 재귀를 통해 구현 했으며 최초로 발견되는 육지가 발생하면 i_count값을 증가시켜준뒤 재귀로 들어가 이어지는 육지들의 값을 2로 바꿔주어 다음번에 다시 탐색하지 않게 합니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include using namespace std; int map[52][52]; const int dsize..

문제 이번에 다뤄볼 문제는 2178번 문제 '미로 탐색'입니다. 미로 탐색 문제에서 연습해야하는 key-point는 BFS입니다. BFS는 너비 우선 탐색을 뜻하는데요. 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다. 문제를 살펴보면 N을 소인수분해 했을때 나타날 수 있는 인수중 가장 큰 값은 루트N입니다. 따라서, 2부터 루트N까지 for문을 돌면서 N을 나눌 수 있다면 계속 나눠주면 됩니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include #include #pragma wa..

문제 이번에 다뤄볼 문제는 1152번 문제 '단어의 개수'입니다. 문장을 입력받고 문장이 끝나는 부분까지의 개수(문자+띄어쓰기)를 구해낸 다음 for문을 돌며 띄어쓰기가 발견될때 num값을 증가시켜줍니다. 만약 문장의 끝 혹은 시작에서 띄어쓰기가 포함되어 있다면 num을 하나 빼줍니다. 마지막에서 띄어쓰기만 입력되었을 경우를 예외처리 해주면 마무리가 됩니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include #include using namespace std; int main() { char arr[1000001]; int count = 0, num = 0; cin.getline(arr, 1000001); while (arr[count] != '\0') count+..

문제 이번에 다뤄볼 문제는 1913번 문제 '달팽이'입니다. 달팽이 문제에서 연습해야 하는 key-point는 2차원 배열과 이중포문입니다. 이번 문제는 아래 코드를 보며 같이 설명드리겠습니다. rcheck = 0, ccheck = 0 // 왼쪽 끝, 위쪽 끝을 나타내기 위한 값입니다. rlimit = 0. climit = 0 // 오른쪽 끝, 아래쪽 끝을 나타애기 위한 값입니다. rlimit, climit의 경우 N값을 입력 받았을때 N-1값으로 대체시켜줍니다. 이후 for문을 돌며 4개의 분기문을 만들어줍니다. 2차원 배열을 (0,0)부터 채워나가기 시작 할 것이므로 N*N값부터 1씩 줄여가며 배열을 완성합니다. N을 소인수분해 했을때 나타날 수 있는 인수중 가장 큰 값은 루트N입니다. 따라서, 2부..

문제 이번에 다뤄볼 문제는 10799번 문제 '쇠막대기'입니다. 쇠막대기 문제에서 연습해야 하는 key-point는 스택입니다 쉽게 생각해보면 어렵지 않게 풀 수 있는 문제입니다. 레이저가 생기는 순간까지 몇개의 쇠막대기가 열려있는지를 판단하면 됩니다. 문제에서 주어진 예시를 보면 첫번째 레이저에서는 잘라지는 막대기가 존재하지 않습니다. 그러나 두번째 레이저를 보면 3개의 쇠막대기가 열려있는걸 볼 수 있습니다. 그럼 두번째 레이저에 의해 3개의 조각이 나올 수 있습니다. 세번째 레이저에서도 여전히 3개의 레이저가 열려있습니다. 그러므로 3개의 조각이 더 나오게 됩니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include #include using namespace s..

문제 이번에 다뤄볼 문제는 9012번 문제 '괄호'입니다. 괄호문제에서 연습해야 하는 key-point는 스택입니다 스택은 선입후출 방식의 자료구조인데요, 가장 먼저 들어온 값이 가장 마지막에 빠지는 구조라고 생각하시면 됩니다. 예를들어 우리가 원통 기둥안에 물건을 하나씩 쌓아서 넣은뒤 그걸 다시 꺼내려면 가장 마지막에 넣었던 물건부터 꺼내게 되는데 이걸 스택이라고 합니다. 이 문제에서 스택을 사용할때는 "top"이라는 변수를 활용하겠습니다. top변수는 스택으로 사용할 배열에서 현재 어느 위치까지 값이 들어갔는지 어느 위치까지 값을 꺼내왔는지를 알기위한 일종의 Index라고 생각하면 됩니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include #include usi..

문제 이번에 다뤄볼 문제는 2581번 문제 '소수'입니다. M이상 N이하의 자연수 중 소수를 에라토스테네스의 체를 활용하여 구하고 처음으로 만나게 되는 소수가 최소값이므로 최초 소수를 min에 저장합니다. 이후 나오는 모든 소수들의 합을 구하면 됩니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(C++) #include using namespace std; int main() { bool arr[10001] = { false }; int m, n, min; int sum = 0, check = 0; cin >> m; cin >> n; for (int i = 2; i