[1주차] 고다혜

[KodaHye]

📗 월요일

[CT] 자율주행 자동차

🤔 시간복잡도 고려사항

• 50 × 50 × 4

💡 풀이 아이디어

• 자동자의 현재 위치, 바라보는 방향을 저장하고, 조건에 따라 자동차를 이동하면서 정보를 업데이트해줌

[CT] 불안한 무빙워크

🤔 시간복잡도 고려사항

• arr: 최대 200
• v: 최대 100

💡 풀이 아이디어

• 무빙워크의 안정도와 사람이 있는지 확인하는 변수를 따로 만들고, 문제에서 요구하는 대로 구현함
• 무빙워크의 안정도는 위 아래 정보는 그냥 하나의 일차원 배열에 저장함
  • 0번 인덱스는 임시값 저장 용도로 사용
• 하나의 객체에서 모든 정보를 관리할 수 있지만, 너무 복잡해진다면 따로 따로 고려해보기
• 문제를 스스로 어렵게 만들지 말자

📗 화요일

[BOJ] 2531 회전 초밥

🤔 시간복잡도 고려사항

• 2 <= N <= 30,000, 2 <= d <= 3,000, 2 <= k <= 3,000
  • 반복문을 통해 완전 탐색한다면 최악의 경우 시간초과 발생
  • 30,000 * 3,000 (나머지 천만 번은 어디서 오는거지,,?,,)
• 투포인터를 사용한다면 O(N)이기 때문에 시간 초과가 발생하지 않음

💡 풀이 아이디어

• 시작(s), 끝(e) 인덱스를 설정해서 조건에 부합하다면 초밥 종류의 개수 세기
  • s ~ e 거리가 k보다 작다면 e += 1
  • s ~ e 거리가 k보다 크거나 같다면 s += 1
  • s ~ e 거리가 k와 같다면 초밥 종류의 개수 찾기
• 처음에는 int eat[]이 아닌 HashMap<Integer, Integer>를 통해 초밥의 개수를 구해줬었는데 시간, 메모리가 더 많이 사용됐음
  • 자료구조 주의해서 선택하기
• 구간의 길이가 명확하게 정해져 있으므로 슬라이딩 윈도우를 통해 구현하는게 더 좋았을거 같음

[SQL] Python 개발자 찾기

💡 풀이 아이디어

• where 절에 in을 사용하여 조건에 알맞는 데이터 출력
• in 다음 ( ) 안에는 찾으려는 데이터 뿐만 아니라 내가 찾을 데이터가 있는지 확인할 열을 넣어도 됨
  

📗 수요일

[BOJ] 3020_개똥벌레

🤔 시간복잡도 고려사항

• 2 <= N <= 200,000, 2 <= H <= 500,000이므로 모든 H에 대해 순차적으로 동굴의 길이만큼 탐색한다면 시간초과 발생
• 이분탐색 이용
  • 500,000 log(100,000) 2 < 1억

💡 풀이 아이디어

• 석순, 종유석 모두 정렬
• 모든 h에 대해서, 석순, 종유석에 대해 개똥벌레가 깨트릴 수 있는 개수 구하기

📗 목요일

[PG] 132265_롤케이크 자르기

🤔 시간복잡도 고려사항

• 선형 탐색으로 풀이

💡 풀이 아이디어

1. 토핑 종류의 개수 구하기
   • 토핑 종류를 구할 때, 각 토핑의 개수도 구하기
2. 0번 인덱스부터 탐색하며 철수가 가질 수 있는 토핑 종류의 개수 구하기
   • 동시에 철수가 해당 idx 까지 케이크를 가져갔을 때, 동생이 가질 수 있는 토핑 종류 구하기

[PG] 12927_야근 지수

🤔 시간복잡도 고려사항

• 이분 탐색, 투포인터로 구현할 수 없는 문제
• 우선 순위 큐(내림차순)를 사용하여 작업량의 최솟값 구함

💡 풀이 아이디어

• 퇴근까지 남은 시간동안 작업량이 많은 순서대로 차례로 작업량을 1만큼 줄이고 다시 pq에 넣어주기

[SQL] 입양 시각 구하기(1)

💡 풀이 아이디어

• 입양시각의 자료형이 DATETIME이기 때문에 HOUR() 함수를 사용해서 시간만 따로 추출해줌
• SELECT 문에서 시간을 HOUR 별칭으로 설정
• GROUP BY HOUR을 해서 시간대 별로 묶을 수 있도록 함

📗 금요일

[PG] 49994_방문 길이

🤔 시간복잡도 고려사항

• 단순 구현이므로 고려 X

💡 풀이 아이디어

• 3차원 방문배열 사용
  • 한 지점을 기준으로 상, 하, 좌, 우를 갈 수 있기 때문
• 방향 벡터 순서: 상, 좌, 하, 우
• 방문 처리
  • v[dir][p.r][p.c] 를 방문처리 해준다면 v[((dir + 2)) % 4][nr][nc]도 방문처리 해줘야 됨
  • 현재 위치에서 dir 방향으로 이동한 것과 nr, nc위치에서 (dir + 2) % 4 위치로 이동한 것과 같기 때문

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

🤔 시간복잡도 고려사항

• 4 <= numbers의 길이 <= 1,000,000 이므로 2중 for문을 사용하면 시간초과 발생함

• Stack 사용

💡 풀이 아이디어

• answer배열은 -1 값으로 초기화
• number.lengh - 1번째 idx부터 시작해서 0번째 인덱스로
  • numbers[i] < stack.peek()일 때까지 stack.pop()
  • answer[i] = stack.peek()
  • stack.push(numbers[i])