[1주차] 배수빈

[baexxbin]

📗 월요일

[CT] 불안한 무빙워크

🤔 시간복잡도 고려사항

• n ≤ 100, k ≤ 2n, 판의 안정성 ≤ 1,000
• 최대 200*1000에 대해 검사할 수 있음 (10^5)

💡 풀이 아이디어

• 무빙워크 Node 객체
  • 번호, 안정성, 사람 여부, 체크를 가짐
• cnt가 K보다 작을때까지 돌면서 실험진행
  • 무빙워크 이동 (모듈러 연산)
  • 무빙워크 위 사람 이동
  • 0번칸 사람 올리기
• 근데 계속 시간초과…

[CT] 자율주행 자동차

🤔 시간복잡도 고려사항

• 50*50 = 2500
• 배열 전체 탐색 시 걸리는 시간.

💡 풀이 아이디어

• 자동차 클래스 생성: 자동차를 움직여야 함

  • 변수
    • 위치좌표, 방향, 움직인 횟수
  • 함수
    • moveGo: 좌회전 후 앞으로 이동
      • moveGo의 경우 새로운 칸으로 이동하므로 cnt++;
    • moveBack: 후진 이동

• play()

  • 본 격적인 자동차 이동이 이뤄지는 곳
  • canGo 변수값을 바탕으로 게임의 지속 여부 판단

• moveCar()

  • 좌회전 후 이동하는 함수
  • 바로 좌회전하는 위치부터 확인하는것 주의

• backCar()

  • 더이상 이동이 불가할때 후진하는 함수

📗 화요일

[BOJ] 2531_회전 초밥

🤔 시간복잡도 고려사항

• N=30,000, D,K= 3,000이므로 조합은 불가
  • 조합 시간복잡도: O(2^N)
  • 투포인터, 슬라이딩 윈도우 시간복잡도: O(N)

💡 풀이 아이디어

• 연속 먹는 접시 K가 정해져 있으므로 슬라이딩 윈도우 사용

  • right 초밥 처리
    • right-left < K-1일동안 초밥 먹기
  • 초밥 다 먹고 mx 값 업데이트
  • left 초밥 처리
    • left초밥 갯수 빼고, 0일 경우 딕셔너리에서 아웃

• 초기 아이디어

  • Set을 통해 현재 윈도우의 초밥을 관리함
  • left에 해당하는 초밥 삭제할때 아예 없어짐
    • 갯수에 따른 관리 불가로 딕셔너리로 변경

• 놓친 부분

  • 주어진 초밥은 리스트가 아닌 원형으로 이어져있음
    • left는 N-1까지 진행
    • right는 %N연산을 통해 올바른 인덱스에 위치하기
  • 해시맵 함수를 익히자…!
    • getOrDefault

[SQL] 연도별 평균 미세먼지 농도 조회하기

💡 풀이 아이디어

• 날짜 데이터를 YEAR함수를 통해 년도 별로 분리
• 소수점 반올림을 위해 ROUND함수 이용

📗 수요일

[BOJ] 2531_회전초밥

🤔 시간복잡도 고려사항

N= 30,000 D=3,000으로 조합 불가

💡 풀이 아이디어

• 먹어야할 K정해져있으므로 슬라이딩 윈도우

  • 0~N까지, 각 인덱스+K만큼 먹을 수 있는 음식 종류 세기 (해시맵)
  • 이때 쿠폰에 해당하는 음식은 빼고 세기
  • 앞으로 이동 시 제일 왼쪽 값 빼기

• 주의할 사항

  • 회전초밥이 일자가 아니고 원형으로 회전함
  • 모듈러 연산을 통해 N+k까지 다 살피기

[BOJ] 3020_개똥벌레

🤔 시간복잡도 고려사항

• (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)로, N*H불가, logN 또는 N 시간복잡도로 해결하기
• 순서 상관없이 특정 위치에서 부딪히는 갯수 일정 → 정렬 가능

💡 풀이 아이디어

• M번째에 위치할때 몇개 부딪히는지 구하기

  • 이분탐색으로 현재 리스트에서 i가 들어가야할 위치 찾기 (중복된 수 존재하니까 low-bound)
  • 전체 리스트 길이(M)-i == 부딪히는 갯수, (이때 리스트는 석순, 종유석 따로 관리)

• 석순, 종유석 리스트 따로 구하기

  • 석순i에서 종유석의 위치는 H-i+1번째
  • 시간복잡도 이분탐색O(NlonN)*2N

• 궁금증

  • 무한루프 방지를 위해 int mid = (left + (right-left)) / 2; 와 같이 적는걸로 아는데 이렇게 하면 무한루프 빠짐

📗 목요일

[PG] 야근 지수

🤔 시간복잡도 고려사항

• n = 1,000,000, works =20,000로 O(N)이하로 끝내기
• 자료구조 활용 잘하기
  • 큐 사용할 경우 큐 이용하기
  • for문으로 값 접근X

💡 풀이 아이디어

• works 중 큰 값씩 뽑아서 1시간씩 처리하기
  • 지수값을 줄여야하므로 최대한 골고루 작은 수들로 만들기
  • 우선순위큐 이용

[PG] 롤케이크 자르기

🤔 시간복잡도 고려사항

• 1,000,000, 10,000이므로 O(N)이하로 끝내기

💡 풀이 아이디어

• 초기 아디이어
  • 투포인터로 0(left), N-1(right) 각 끝에서 하나씩 오면서 반띵하기
  • 각 포인터로부터 하나씩 움직여보며 더 공평하게 나눌 수 있는지 확인
    • 가운데 1개 남는 토핑 처리등 예외처리해야할 부분 존재
• 두번째 아이디어
  • 가운데서 시작하는 것이 아닌, N-1맨 끝에서부터 같은 아이디어로 풀이
  • 동생이 마지막부터 거꾸로 하나씩 먹으며 공평하게 나눌 수 있는지 확인
  • 해시맵 이용

[SQL] 오랜기간 보호한 동물

💡 풀이 아이디어

• 보호기간이 제일 길었던 동물 두마리 아이디, 이름 조회
• DATEDIFF를 통해 날짜차이 구하기

📗 금요일

[PG] 154539_뒤에 있는 큰 수 찾기

🤔 시간복잡도 고려사항

• N= 1,000,000으로, O(N)이하로 풀기
• 리스트 한 번의 탐색으로 끝내기

💡 풀이 아이디어

• 뒤에서 부터 값 확정해나가기
  1. num[i+1] i바로 뒤에 값이 크다면 값 넣기
  2. 아니라면 큰 값 나올때까지 dp 돌기
  3. 이때 -1이 나오면 더이상 없는 것으로 탈출

[PG] 49994_방문 길이

🤔 시간복잡도 고려사항

• 보드가 10*10이므로 넉넉함
• 각 점에서 상하좌우로 값을 살핀다해도 10104로 넉넉함

💡 풀이 아이디어

• 왔던 길인지 확인
  • (x1, y1) → (x2,y2) 과 같이 출발좌표 도착좌표 넣어줌
  • (x1, y1, x2,y2), (x2, y2, x1,y1) 양뱡항으로 넣어주기
  • Set에 해당 좌표값 넣어주고, set길이 반환
• 입력에 따라 로봇 이동