본문 바로가기

코딩테스트15

[Softeer][c++] 성적 평균 문제 출처: https://softeer.ai/practice/info.do?idx=1&eid=389 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 N명의 학생들의 성적이 학번순서대로 주어졌다. 학번 구간 [A, B]가 주어졌을 때 이 학생들 성적의 평균을 구하는 프로그램을 작성하라. 제약조건 1 ≤ N ≤ 106 인 정수 1 ≤ K ≤ 104 인 정수 1 ≤ Si ≤ 100 인 정수 1 ≤ Ai ≤ Bi ≤ N 입력형식 첫 번째 줄에 학생 수 N과 구간 수 K가 주어진다. 두 번째 줄에는 학생의 성적 Si (1 ≤ i ≤ N)가 주어진다. i + 2 (1 ≤ i ≤ K)번째 줄에는 i번째 구간 Ai, Bi가 주어진다. 출력형식 i번째 줄에 i번째 구간의 성적평.. 2023. 5. 11.
[백준2178][c++] 미로 찾기 문제 출처: https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 소스 코드: #include #include #include #include using namespace std; int n,m; char map[101][101]; // 미로를 입력받을 배열 bool visited[101][101] = {false,}; // 방문 확인 배열 int check[101][101] = {0,}; // 칸을 세기 위한 배열 int dx[4]={-1,1,0,0}; int dy[4]={0,0.. 2023. 4. 17.
[백준10828][c++] 스택 문제: https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 접근: 2년 전, 자료구조 수강 당시 c로 풀어본 이력이 있었다. c++ stack 라이브러리를 활용하니까 확실히 간결하고 편했다. 별다른 코드 작성 없이 stack 메소드 활용해서 작성한게 전부이고 스택 비어있을 때 "-1" 출력 조건 정도만 덧붙여 작성하면 끝 소스코드: #include #include using namespace std; stack s; void pu.. 2023. 4. 16.
[백준17298][c++] 오큰수 문제: https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 접근: 엘지 코테 당시, 해당 오큰수문제와 거의 비슷하게 출제되었는데 당시 문제를 풀 때는, 인덱스 뽑아서 2중 반복문으로 돌리다보니 ( 시간복잡도 O(N^2) ) 테스트케이스는 통과를 했지만, 히든 케이스에서 10^6 x 10^6 = 10^12 에서 분명히 시간초과가 발생했을 것이다. 다른 솔루션을 찾아본 결과, 스택으로 (O(N)) 시간초과 없이 해결한 케이스가 있어 이를 참고하였다. https:.. 2023. 4. 16.

티스토리툴바