10주차 스터디

[eunseongman]

[Bumnote]

발표자: 동휘 (문제: BOJ 1796 찾기)

내용

• 해당 문제 제출 코드
• KMP 알고리즘을 적용하여 푸는 문제

QnA

• 태희쌤 코드
• 동휘는 인덱스를 1부터 했고, 태희쌤은 인덱스를 0부터 시작

Reference

Abdul Bari 교수님 KMP 강의
https://www.youtube.com/watch?v=V5-7GzOfADQ&t=659s

[Bumnote]

발표자: 지인 (문제: BOJ 16900 이름 정하기)

내용

• 해당 문제 제출 코드
• KMP 알고리즘을 응용하여 푸는 문제
• 주어진 문자열이 이미 존재하므로, (K - 1)
• long 자료형에 주의하자.

QnA

• KMP 너무 어렵다.

Reference

[Bumnote]

발표자: 주혜 (문제: BOJ 1305 광고)

내용

• 해당 문제 제출 코드
• KMP 알고리즘을 응용하여 푸는 문제 / BOJ 16900 이름 정하기 문제와 흡사
• 1바퀴 순환하기 때문에 원본 문자열에 2배를 해서 문제를 접근하자.
• 마름모 도형을 연달아서 붙여서 생각하는 것이 이해하는 데 도움이 된다.

QnA

• KMP 너무 어렵다.

Reference

[Bumnote]

발표자: 은성 (문제: BOJ 7575 바이러스)

내용

• 해당 문제 제출 코드
• KMP 알고리즘을 브루트포스 기법으로 적용한다.
• k개의 문자열의 길이를 투포인터 적용
• 역방향인 경우를 고려해서 실패함수를 2개 만든다.
• KMP + 완전 탐색 문제이다.

QnA

• KMP 너무 어렵다.

Reference

[Bumnote]

발표자: 예림 (문제: BOJ 23300 웹 브라우저 2)

내용

• 해당 문제 제출 코드
• 스택을 활용해서 문제했다.

QnA

• 큐로 써서 활용했다.
• 중간 데이터를 삭제할 때는 LinkedList 자료구조도 생각해보면 좋을 것 같다!

Reference

[Bumnote]

발표자: 건휘 (문제: BOJ 25319 Twitch Plays VIIIbit Explorer)

내용

• 해당 문제 제출 코드
• 빡구현 문제
• 이동 횟수가 최소일 필요는 없다. -> 즉, 최단 경로일 필요가 없다.

QnA

• 닉네임의 길이가 절댓값 ?
  -> 길이가 음수인 것은 말이 안된다.

• ID 카운트를 Map으로 쓴 이유
  -> 해당 알파벳의 원소들을 가져올 수 있으니까 이게 편해서 Map을 사용했다.

Reference

[Bumnote]

발표자: 권민 (문제: BOJ 18119 단어 암기)

내용

• 해당 문제 제출 코드
• 비트마스킹 기법 활용하여 풀이
• 알파벳은 26자리까지 있고, int형은 2^32 까지 가능하므로, 비트마스킹 활용

QnA

Reference

[Bumnote]

발표자: 일우 (문제: BOJ 25289 가장 긴 등차 부분 수열)

내용

• 해당 문제 제출 코드
• 디버깅을 하나씩 해보면서 이해했다.
• 이 문제의 핵심은 수열들을 카운트해서 가장 많은 카운트를 가진 녀석이 가장 긴 부분 수열이 된다.
• 공차 개념을 생각하는 것이 중요하다.

성수 풀이

• 주어진 숫자의 개수가 매우 적으므로, 공차를 -99 ~ 99로 설정하여 dp 적용
• 등차 수열에서 과거의 정보는 공차를 하나 뺀 값이다.

QnA

Reference

[Bumnote]

발표자: 성수 (문제: BOJ 12763 지각하면 안 돼)

내용

• 해당 문제 제출 코드
• 시간을 기준으로 다익스트라 코드를 돌린다.
• 마지막에 비용을 0원부터 시작하여 가장 먼저 초기값이 아닌 값이 나오면 그게 바로 최소 비용이다.

은성 풀이

• DFS 알고리즘으로도 풀이가 가능하고, 훨씬 간단하다.

private static void dfs(int now, int time, int cost) {
        if (now == N) {
            answer = Math.min(answer, cost);
            return;
        }

        for (Edge edge : lists[now]) {
            if (visited[edge.next] || time + edge.time > T || cost + edge.cost > M) {
                continue;
            }

            visited[edge.next] = true;
            dfs(edge.next, time + edge.time, cost + edge.cost);
            visited[edge.next] = false;
        }
    }

QnA

Reference