[CodingTest]코딩 테스트 스터디

우테코 코딩테스트 알고리즘 스터디

💻240715~240721

1. 달리기 경주(Lv.1) 178871

해시

• 파이썬 내장함수 list.index()를 사용하면 O(n)이기 때문에 시간 초과가 난다.

• 플레이어 초기 등수를 dict{이름: 랭킹}에 저장한다.

• 이름이 불린 선수의 랭킹-1, 그 앞 선수의 랭킹+1을 한다.

• 무결성을 유지하기 위해 리스트의 순서도 바꿔준다.

💻240722~240728

1. 도서관(골5) 1461

그리디

음수

• 음수는 오름차순으로 정렬하면 0번째가 제일 멀리있다.

• M으로 나눈 나머지가 0인 곳만 더해준다.

• 나머지가 0인 곳만 궁금하고 나머지는 궁금하지 않기 때문

ex) -45 -26 -18 -9 -4 22 40 50

양수

• 양수는 내림차순으로 정렬하면 0번째가 제일 멀리있다.

• M으로 나눈 나머지가 0인 곳만 더해준다.

ex) 50 40 22 -4 -9 -18 -26 -45

최종 계산

• 제일 멀리 있는 곳에 도착해서 끝나는게 정답이다.

• 제일 멀리 있는 곳 빼고 다 x2한 값을 더한다.

2. 결혼식(실2) 5567

BFS

• 건너건너 친구까지이기 때문에 depth 2까지만 센다.

• visited에 depth를 저장한다.

3. 점프 ( 실1) 1890

DP

• 현재 적혀있는 수만큼 오른쪽, 아래쪽 answer에 현재 위치의 answer를 더한다.

• 그렇게 값을 누적해나가면 도착지로 갈 수 있는 경우의 수가 다 더해진다.

4. 죽음의 비 (골4) 22944

BFS, 구현

• visited는 3차원으로 할 필요없이 '체력+우산내구도'를 저장하면 된다.

• 주의: 우산을 새로 쓴 곳도 비가 오기 때문에 30번째 줄에 nd = D가 아닌 nd = D-1이다.

• 끝까지 E를 만나지 못 한다면 while문을 탈출하여 -1를 출력한다.

💻240729~240804

1. 안정적인 문자열 (실1) 4889

그리디, 스택

• '}'인데 stack이 비어있으면 일단 cnt+1을 해주고 stack에 뒤집어서 '{'로 넣어준다.

• '{'가 추후에 '}'를 만나 사라질 수 있게 하기 위해서다.

3. 농장 관리 (골5) 1245

BFS

• 입력 받으면서 max_height를 구한 후 0부터 max_height까지 돌면서 해당 높이를 만날 때 마다 bfs를 호출한다.

• bfs의 용도는 '봉우리 존재 여부 반환'과 '방문 처리'이다.

• 기본적인 bfs의 코드와 동일하며 '봉우리인지'를 찾기 위해 16, 27, 28번째 줄이 추가되었다.

4. 꿈틀꿈틀 호석 애벌레 - 기능성 (실1) 20167

재귀

dp로 나와있지만 기능성은 재귀로도 시간초과 없이 풀 수 있다. 효율성은 dp로 다시 생각해 봐야 할 듯..?

1. 이전 total값이 K보다 큰 경우

최소 만족도가 K 이상이면 먹는 것을 멈춘다고 나와있으므로 에너지를 계산한 후 0으로 초기화 한다.

2. 이전 total값이 K보다 작은 경우

• 이전 total이 0이면, 현재는 안 먹을 수도 안 먹을 수도 있다.

• 이전 total이 0이 아니면, 무조건 연속적으로 먹어야 하므로 현재 만족도를 더해준다.