본문 바로가기

알고리즘

 (82)
[백준] 11659번 구간 합 구하기 4 C++ 문제풀이 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 풀이 누적합 배열을 생성해서 구간 합 문제를 해결했다. 처음 제출했을 때 시간복잡도가 O(N)이였는데도 시간초과가 나와서 당황했다. ios::sync_with_stdio(false); cin.tie(nullptr); 코드를 작성해서 main안에 넣어주니 시간 초과 문제가 해결되었다. 위의 코드들에 대해서는 다음번에 자세히 설명해 볼 예정이다. 소스 코드 #include..
[백준] 1003번 피보나치 함수 C++ 문제풀이 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 처음에는 재귀 함수 안에 count를 했는데, 시간초과가 나왔다. 따라서 pair fibo 배열을 만들어서 first에는 0이 나오는 횟수, second에는 1이 나오는 횟수를 저장하고 2부터 40까지 증가하는 순서로 배열을 채웠다. 소스 코드 #include using namespace std; pair fibo[41]; int main() { int T; cin >> T; //fibo 배열 만들기 fibo[0].first = 1; fibo[0].second = 0; fibo[1]..
[백준] 2606번 바이러스 C++ 문제풀이 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 문제 풀이 dfs를 이용해 방문한 지점들에 대해서 check 배열을 true로 바꿔주었다. check 배열의 true값의 갯수를 이용해서 count를 구했다. 소스 코드 #include #include using namespace std; bool check[101] = { false }; vector graph[101]; void dfs(int idx) { if (check[idx] == false)..
[백준] 1012번 유기농 배추 C++ 문제풀이 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 풀이 dfs를 이용해 문제를 풀었다. for문을 이용해 배추밭인 land와 방문 여부 배열인 check를 이용해 문제를 해결했다. 배추가 있는 곳 + 방문을 안했다면 count를 해주었다. 연결된 지점에 있는 배추들은 dfs를 이용해 미리 방문 여부를 true로 설정해줬기 때문에 배추가 있더라도 count가 되지 않는다. 소스 코드 #include using namespace std; int M, N, ..
[백준] 1018번 체스판 다시 칠하기 C++ 문제풀이 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 풀이 브루트포스 문제임을 알아도 어떤식으로 해결해야할지 막막했다. 다른 블로그 글을 참고하니 8X8의 체스판이라는 말이 중요했다. 8X8 체스판을 미리 만들어 두고 값이 다른 횟수가 최소인 경우를 출력하면 되는 문제였다. 소스 코드 #include #include using namespace std; string board[51]; string WB[8] = { "WBWBWBWB", ..
[백준] 1946번 신입 사원 C++ 문제풀이 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 풀이 일단 서류 심사 결과를 기준으로 정렬한 뒤, 서류심사 결과가 1등인 사람부터의 면접성적을 기준으로 min_value를 설정해 서류심사의 성적이 낮은사람의 면접성적이 min_value 보다 낮으면 count를 하고 min_value를 수정했다. 소스 코드 #include #include #include using namespace std; int main() { in..
[백준] 16953번 A -> B C++ 문제풀이 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A > A >> B; while (B >= A..
[백준] 1783번 병든 나이트 C++ 문제풀이 https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 맨 처음에는 이동하려는 4가지 경우에 대한 함수를 작성해서 문제를 풀어보려 했으나 계속 틀렸다. 이 문제의 핵심은 나이트가 오른쪽으로만 이동한다는 것이다. 만약 N == 1이라면 나이트는 움직일 수 없으므로 1을 출력하고 N == 2라면 2, 3의 방법만을 이용하고 최대 4회를 넘으면 안된다. N이 3보다 큰 경우에는 세로에는 영향을 안받고 가로의 길이에 맞춰서 코드를 작성했다 소스 코드 #include using namespace std; int m..

티스토리툴바