코딩테스트 - 패스트캠퍼스 챌린지 47일차

수강한 강의

Part 5. 패캠 제작 문제 풀이

Chapter 01. 문제풀이
- 나동빈의 패캠 제작 문제 해설 1

학습 후기

SQL 강의가 끝나고 이제 알고리즘 문제 풀이에 들어간다.

강의에서 풀이해주는 알고리즘 문제는 백준 사이트에서 확인할 수 있다.

 

1. https://www.acmicpc.net/problem/21918

21918번: 전구

시간제한 1초, 메모리 제한 512MB

문제 파악: N개의 전구가 있고 맨 왼쪽 전구를 첫 번째라고 한다. 전구의 상태는 1: on, 0: off

전구 제어 명령어

1) [i x] - i번째 전구의 상태를 x로 변경

2) [l r] - l번째부터 r번째 까지 전구 상태를 변경, toggle

3) [l r] - l번째부터 r번째까지 전구 off.

4) [l r] - l번째부터 r번째까지 전구 on.

 

input

1번째 줄 - N: 전구 개수, M: 명령어 개수

2번째 줄 - 초기 전구 상태 s

3번째 줄 ~ M + 2 - 명령어 a b c

a는 명령 번호 b, c는 l, r

 

제한 시간 20분

단순 구현 문제로 N개의 전구를 초기 상태 s로 초기화하고 M 개의 명령어 입력을 받으면서 수행하면 되는 간단한 문제이다. 명령어를 함수로 작성하여 해당 명령어 번호에 따라 다른 명령어가 수행하도록 작성한다.

 

2. https://www.acmicpc.net/problem/21919

21919번: 소수 최소 공배수

시간제한 1초, 메모리 제한 512MB

문제 파악

길이가 N인 수열 A에서 소수를 골라 최소 공배수를 구하여라.

input

1 <= N <= 10000

수열 A의 원소 값 범위 2 <= Ai <= 1,000,000

답이 2^63 미만인 입력만 주어진다. 이걸 봤을 때 자료형 long을 선택한다.

유클리드 호제법을 이용하여 쉽게 문제를 풀 수 있다.

a, b의 최대공약수 gcd(a, b)

gcd(a, b) = gcd(b, a % b)

if (a % b = 0) gcd => b

else gcd(B, A%B)

a, b의 최소 공배수 lcm(a, b)

lcm(a, b) = a * b / gcd (a, b)

 

3. https://www.acmicpc.net/problem/21920

21920번: 서로소 평균

시간제한 1초, 메모리 제한 512MB

문제 파악

길이가 N인 수열 A에서 X와 서로소인 수들을 골라 평균을 구한다.

첫 번째 줄 N, 2 <= N <= 500,000

두 번째 줄, 수열 A를 나타냄

수열 A에 X와 서로소인 수가 최소 1개 이상 존재

마지막 줄 X, 2 <= X <= 1,000,000

gcd(a, b) == 1일 때 두 수는 서로소라고 말할 수 있다. 이것을 가지고 문제를 해결해본다.

 

4. https://www.acmicpc.net/problem/21921

21921번: 블로그

시간제한 1초, 메모리 제한 512MB

문제 파악

블로그 시작한 지 N일이 지났다.

X일 동안 가장 많이 들어온 방문자 수와 그 기간을 알고 싶다.

input

첫째줄, 1 <= X <= N <= 250,000

둘째 줄, 방문자 수 배열 - 0 <= 방문자 수 <= 8,000

슬라이딩 윈도우 개념을 활용하여 문제를 풀 수 있다.

 

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.