[1주차] 이예진

[yeahdy]

📗 월요일

[CT] 불안한 무빙워크

🤔 시간복잡도 고려사항

• 알고리즘: 일반 구현

💡 풀이 아이디어

• 문제의 구현과정과 조건을 정확하게 이해하고 순차적으로 로직 작성
• 1턴의 실험과정을 각각 메소드로 구현 해 과정에 맞게 조립하는 형태로 코드 작성 필요

1. 한칸 진행
2. 앞선 칸에 사람있는지 and 안정성이 0보다 큰지
3. 없으면 다음 칸에 타기 3-1. 기존에 있는 사람 전진 ?? 3-2. 신규로 새로 타기
4. N 번째 칸에 왔으면 내리기 4-1. 판의 갯수 충족 했을 경우 종료

[CT] 자율주행 자동차

• 알고리즘: BFS
• 시간복잡도:3 ≤ n, m ≤ 50 범위로 BFS 의 O(n)로 가능

💡 풀이 아이디어

• BFS로 순회할 때 요구사항에 맞는 구현을 잘 정리해서 로직을 작성해야함
  1. 자동차는 첫 시작을 기준으로 좌회전한다
  2. 해당 방향이 방문했거나 인도인 경우 계속 좌회전한다
  3. 좌회전 중 도로가 있을 경우 이동한다
  4. 만약 4방향 모두 전진이 불가할 경우 바라보는 방향을 유지한 채로 한칸 후진한다
  5. 후진한 후 4방향을 탐색한다
  6. 후진이 불가하다면 작동을 멈춘다

📗 화요일

[BOJ] 2531_회전 초밥

🤔 시간복잡도 고려사항

• 알고리즘: 투 포인터
• 시간복잡도: O(n)
• 처음에는 문제를 잘못 이해해서 조합으로 풀었는데, 조합은 O(2^n) 시간복잡도이기 때문에 시간초과 발생
  • N ≤ 30,000 / d,k ≤ 3,000 으로 범위가 10^4 이상이기 때문에 조합 불가

💡 풀이 아이디어

• 처음 접시부터 마지막 접시까지의 하나의 회전을 하기 위해서 N-1번 회전이 필요
• 처음 접시부터 마지막 접시까지의 이어진 k 개의 연속된 묶음을 고려했을 때 횟수가 N-1 번 회전하기 때문
• 회전을 반복할 때는 처음과 끝을 index를 기준으로 하나의 k 개로 묶어서 확인해야함
• 슬라이딩을 위해 처음에 k 개 묶음만큼 초기 셋팅이 필요함

📗 수요일

[BOJ] 3020_개똥벌레

🤔 시간복잡도 고려사항

• 알고리즘: 이분탐색
• 시간복잡도: O(NlogN)
• N ≤ 200,000 / H ≤ 500,000 범위
• 완전탐색으로 구현 시 O(2^n) 시간복잡도이므로 시간초과 발생

💡 풀이 아이디어

• 순서가 상관없다면 이분탐색을 위해 정렬을 활용하자
  • 정렬할 경우 중간을 기준으로 왼쪽/오른쪽 나눠서 원하는 조건 탐색 가능
• 이분탐색 응용 방법: 동굴의 전체 범위에 대해 위 아래를 구분해서 동시에 각각 탐색하기
• 이분탐색 시중간을 기준으로 왼쪽에 해당 할 경우 충돌이다

📗 목요일

[PG] 야근 지수

🤔 시간복잡도 고려사항

• 알고리즘: 우선순위 Queue
  • 시간복잡도: O(n)

💡 풀이 아이디어

• 내림차순 정렬을 통해 가장 큰 숫자들부터 작게 만들어서 최소값 구하기
• PriorityQueue를 사용하면 우선순위에 따라 숫자가 먼저 반환된다

[PG] 롤케이크 자르기

🤔 시간복잡도 고려사항

• 알고리즘: HashSet
• 시간복잡도: O(n)
• topping의 길이 ≤ 1,000,000 범위로 O(nlogn) 부터 불가

💡 풀이 아이디어

• 전체 토핑 수를 기준으로 철수와 동생이 각각 토핑을 가져간 수를 카운팅했을 때
  • 철수(왼쪽) [1,2,2,3,3,4,4,4]
  • 동생(오른쪽) [4,4,4,4,3,3,2,1]
• 철수가 왼쪽에서 토핑 하나를 가져갔을 때 동생은 오른쪽을 기준으로 +1 개까지만 토핑을 가져갈 수 있다
  • (동생의 토핑수를 담은 배열 정렬은 뒤에서 부터 자름)
• 따라서 n(철수) == n+1(동생) 이 같을 때 평등하게 토핑을 나눌 수 있다

📗 금요일

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

🤔 시간복잡도 고려사항

• 알고리즘: Stack
• 시간복잡도: O(n)
• numbers의 길이 ≤ 1,000,000 범위로 O(NlogN)부터 불가
• while문 내 조건을 통해 n 만큼 반복하게 로직 작성했더니 시간복잡도가 O(n^2)되어 시간초과 발생

💡 풀이 아이디어

• 전체에서 하나씩 더 큰수를 찾으며 비교하면 안됨 > 시간복잡도 O(n^2) 발생
• 전체 반복을 돌면서 기존 수과 다음에 오는 수를 계속해서 비교하는데 이때 이전에 누적된 수도 함께 갱신할 수 있어야한다.
• 또한 배열에 담긴 수를 가져오기 위해 index 를 활용해서 Stack에 index를 담고 이전에 누적된 수를 가져오도록 한다

[PG] 49994_방문 길이

🤔 시간복잡도 고려사항 － 알고리즘: BFS

• 시간복잡도: O(n) dirs의 길이는 500 이하로 단순 구현으로 풀어도 가능할 것으로 예상 (아직 문제를 다 못푼 상태)

💡 풀이 아이디어

• BFS로 순회할때 방문한 지점을 방문처리 하는 것이 아닌 다녀간 길을 방문처리 해야 함
• 현재 위치(x,y) + 다음 위치(x,y) 를 문자열 형태로 저장
  • 중복일 경우 이미 다녀간 경로!
• 다음 위치(x,y) + 현재 위치(x,y) 를 문자열 형태로 저장
  • 위아래 또는 좌우 왔다갔다한 경로도 이미 다녀간 경로!