[1주차] 이혜원

[icegosimperson]

📗 월요일

[CT] 자율주행_자동차

🤔 시간복잡도 고려사항

• 3 ≤ n, m ≤ 50, 4방향 탐색 nm4 = 4nm => O(nm)

💡 풀이 아이디어

• 네 방향으로 이동할 수 있을 때 : d = (d + 3) % 4 : 왼쪽 방향으로 회전
• 네 방향 모두 이동할 수 없을 때 : 후진 가능 여부 판단

[CT] 불안한_무빙워크

🤔 시간복잡도 고려사항

• n, k, d(판의 안정성)이 모두 1000미만 범위가 작아서, 시간 복잡도를 고려하진 않았습니다

💡 풀이 아이디어

• int 레일 배열, boolean 사람 위치 배열 추가 함께 위치를 고려
• 뒤에서부터 사람이 이동할 수 있는지 확인하며 이동하는 movePerson 함수

📗 화요일

[BOJ] 2531_회전초밥

🤔 시간복잡도 고려사항

• 시간 복잡도 : 슬라이딩 윈도우를 이용하여 시간 복잡도를 O(N)으로 개선

💡 풀이 아이디어

• 슬라이딩 윈도우를 이동할 때 맨 뒷 값과 이전 슬라이딩 윈도우의 맨 앞 값을 계산

[SQL] 조건에 맞는 사원 정보 조회하기

💡 풀이 아이디어

• 문제에서 필요한 테이블만 선택(HR_DEPARTMENT 필요X)
• 평가 점수 = (상+하반기 점수)

📗 수요일

[BOJ] 3020_개똥벌레

🤔 시간복잡도 고려사항

• 시간 복잡도 : 시간 제한 1초, 장애물의 크기 : O(NlogN)
• N(200,000) H(500,000) = 100,000,000,000회 O(NH)불가

💡 풀이 아이디어

• O(NH) 시간 복잡도가 불가하기에 각 높이에 대해 장애물(석순, 종유석)을 하나씩 탐색하면 시간 초과
• 누적합을 사용하여 모든 높이에서 장애물(석순, 종유석)의 길이를 미리 계산하여 시간 복잡도를 줄임

📗 목요일

[PG] 132265 롤케이크 자르기

🤔 시간복잡도 고려사항

• topping길이 : 백만 O(NM) X , O(N), O(N logN) ...

💡 풀이 아이디어

• 토핑의 개수보다 종류가 더 중요하기에 HashSet을 이용해서 중복 제거
• 두 배열(left, right) 사용
• 두 배열을 N/2, N/2로 나누지 않는 이유는 모든 절단 위치를 고려하기 때문
• 배열 인덱스 주의 : 철수: 0~i, 동생 : i+1 ~N-1 (N 포함 x : 동생이 먹을 최소한의 몫)

[PG] 12927 야근 지수

🤔 시간복잡도 고려사항

• n =1,000,000
• O(N), O(N log N)...
• 우선 순위 큐 삽입, 삭제 시 시간 복잡도 : O(N logN)

💡 풀이 아이디어

• 피로도를 낮추기 위해서는 가장 큰 값부터 - 해줘야함
• 높은 숫자가 우선순위가 높은 우선순위 큐 사용 (내림차순)
• while(n(야근 피로도) > 0) -> queue.poll() -> work -=1 -> queue.offer() -> n-=1
• 정답 값 출력 시 poll()할 때 Queue size 줄어드는 것을 방지하여 미리 size 선언

[SQL] 평균 일일 대여 요금 구하기

💡 풀이 아이디어

• ROUND(AVG(평균구할것), 0) => 소수 첫째자리 반올림

📗 금요일

[PG] 49994_방문 길이

🤔 시간복잡도 고려사항

• dirs길이 = 500 이하 자연수 -> 일반 배열로 불가능
• HashSet을 이용 O(N)

💡 풀이 아이디어

• 방문한 좌표제거를 위해 HashMap 이용
• 좌표 양수 변환, 이유 : 음수 좌표는 계산 번거로움
• 좌표 양수 변환했기에 시작 위치 (0,0) -> (5, 5)로 변경

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

🤔 시간복잡도 고려사항

• numbers <= 1,000,000 / O(N^2) 불가
• 이중 반복문으로 비교시 시간 초과 다른 알고리즘 필요

💡 풀이 아이디어

• 스택과 스택 인덱스를 배열로 사용한 이유: 오른쪽에->왼쪽 역 탐색이 효율적을 이라서 그렇다는데 다른 분들의 의견이 궁금합니다

• 스택이 비어있지않고, 현재 수열 값이 top에 해당하는 수열보다 클 때까지 pop

• 정답 배열에 오큰수를 저장 -> 크지 않을 경우 push

• 스택이 빌 때까지 정답 배열에 -1 저장

• 백준 17298_오큰수 문제와 동일 (https://www.acmicpc.net/problem/17298)