N

문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는 2번 문..

문제 총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다. 감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다. 각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다. 각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (..

문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다. 출력 각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다. BFS를 이용하여 문제 ..

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14uWl6AF0CFAYD&categoryId=AV14uWl6AF0CFAYD&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com queue를 이용한 문제 풀이. test case는 10개인데, 문제에 써져 있지 않으므로 주의하여 코딩하자. 우선 8개의 숫자를 int형 queue인 q에 담아주자. 그리고 q.front() - count > 0일 때까지 사이클을 돈다. count는 1 ~ 5까지 빼는 수를 의미하므로, 6 이상이면 count = 1로 고쳐준다. ..

큐와 맵을 이용하여 문제를 푼다. 우선 string을 담을 수 있는 큐인 q와 map m을 선언한다. 그리고 보석 종류의 개수를 구하기 위한 gems_size, 진열대 시작 번호 start, 진열대 마지막 번호 end, 시작 지점 바꿔주기 위한 tmp를 0으로 초기화한다. 이제 보석 종류의 개수를 구하도록 한다. for문을 통해 gems를 순회하면서 m에 넣어주도록 한다. gems_size = m.size()로 하여 개수를 저장하고, m은 clear하여 비워주도록 한다. 다시 gems를 순회하면서 정답을 알아내면 된다. m을 초기화 하였으니 m[gems[i]] == 0이면 1을 넣어주고, 0이 아니라면 같은 보석이 이미 있는 경우이므로 해당 보석의 개수를 +1로 해준다. 그리고 q에 push. 모든 종류..

DFS/BFS에 관한 문제. DFS도 가능하지만 BFS 방식으로 풀었다. 우선 큐가 필요하다. 그리고 방문 여부를 확인하는 bool형 배열 visited, 그래프를 이어주는 bool형 배열 check를 선언하여 false로 초기화. 그리고 depth를 나타내는 int형 배열 dist도 선언하여 0으로 초기화 한다. for문으로 check 배열에 그래프를 이어준다. 사실상 상삼각행렬을 사용한다. 1부터 n까지 상삼각행렬을 그려주도록 하자. 그리고 1부터의 거리를 재야하기 때문에 큐에 1을 넣어주고, visited[1]도 true로 표시. 이제 while문으로 q가 비어잇을 때까지 반복한다. q의 앞부분을 가져오고 pop. 2 ~ n까지 for문을 돌면서 check[현재노드][i] == true && vis..

DFS, BFS 두 방법으로 풀 수 있는 문제다. 본인은 BFS로 풀었다..! 우선 큐를 만들어 준다. 단어를 탐색하고, 해당 단어의 인덱스까지 pair로 묶어주어 q에 넣어준다. tmp_q는 임시 큐로 단계를 올릴 때 사용한다. 그리고 answer는 1로 초기화 하였다. 1단계의 단어를 바로 찾기 때문에 1로 초기화 하였다. 우선 words에 target이 있는지 확인한다. 없으면 바로 0 리턴. target이 words 안에 있다면 탐색을 시작한다. 1단계의 단어를 탐색하기 위해 0 ~ words.size()만큼 반복한다. 그리고 count를 이용하여 begin과 words[i]를 비교하여 한 개의 알파벳을 바꿀 수 있는지 확인한다. count가 begin.size() - 1 이라면 한 개의 알파벳을..

#include #include #include using namespace std; int answer = 0, tomato = 0; queue q, tmp_q; int arr[1001][1001]; bool visited[1001][1001] = {false, }; void bfs(int M, int N, pair p) { int row = p.first; int col = p.second; q.pop(); //up if(row - 1 >= 0 && row - 1 = 0 && col < M && visited[row - 1][col] == false) { visited[row - 1][col] = true; arr[row - 1][col] = 1; tmp_q.push(make_p..