11주차 스터디

[jjsyeon]

[Bumnote]

발표자: 건휘 (문제: BOJ 1107 리모컨)

내용

• 해당 문제 제출 코드
• 브루트포스 기법으로 문제를 풀이
• 반복문을 0부터 시작하여 자릿 수가 낮은 숫자를 먼저 return 할 수 있도록 풀이

QnA

• 풀이가 바로 떠올랐나요?

GPT를 활용하여 중간과정에 방향성 도움을 받았습니다.

Reference

[ghpark7]

발표자: 권민 (문제: BOJ 14725 개미굴)

내용

• 해당 문제 제출 코드
• 기본적인 트라이 방식으로 해결

QnA

• 트라이 알고리즘 코드가 낯설어서 index 활용 목적의 설명이 필요합니다.

keyset을 통해 child가 더 있는지 여부를 확인하며 계속 진행하기 위해 사용했습니다.

Reference

[ghpark7]

발표자: 은성 (문제: BOJ 1949 우수마을)

내용

• 해당 문제 제출 코드
• 트리 구조에서의 DP와 DFS 방식을 모두 사용하여 풀이 (DP 문제가 방향성 트리 문제처럼 사고 가능하다는 Tip!)
• 2차원 DP 배열 생성 후 DFS, 이 때 트리 구조라 방문 처리는 필요 없이 parent로 되돌아가는 것만 막아준다.

QnA

• 이 풀이를 어떻게 떠올리셨나요?

Chat GPT의 조언과 백준의 알고리즘 분류 확인

Reference

• 용범님 추천 문제 - 문제: BOJ 2533 SNS)

[ghpark7]

발표자: 지인 (문제: BOJ 3108 로고)

내용

• 해당 문제 제출 코드
• 문제를 파악 후 유니온 파인드로 하면 되겠네!!
• 각 네모가 같은 소속인가 아닌가를 따지며 유니온 파인드 수행

QnA

• 은성: (0,0)까지 포함하는 이유가 뭐죠?

문제의 조건이 (0,0)부터 시작이고 고로 반드시 네모로 생각해야 하는 문항입니다.

Reference

[ghpark7]

발표자: 용범 (문제: BOJ 13913 숨바꼭질)

내용

• 해당 문제 제출 코드
• 처음 보자마자 BFS로 방향성 잡음 (가중치가 1이고 크게 제한에 걸리지 않을 것 같았기 때문)
• 다익스트라 역추적 문제가 생각나서 도입
• 문제 풀이 당시 범위를 넘어섰다는 에러를 자주 마주했는데 if문의 조건부에서 OR 양쪽의 순서를 바꿔보니 오류 발생하지 않음 (방문처리 우선 수행)
• 역추적을 해야하기 때문에 Deque을 선언해서 오름차순으로 저장하는 방식 채택

QnA

• 은성: 방문 배열 안쓰고 우선순위 큐 사용해도 되나요?

네, 상관없습니다. 다익스트라를 사용하셔도 됩니다!

• 은성: 다익스트라가 더 빠르지 않나요?

네, 파이썬 코드임에도 불구하고 다익스트라가 더 우수한 성능을 보이고 있습니다.

Reference

[ghpark7]

발표자: 주혜 (문제: BOJ 1563 개근상)

내용

• 해당 문제 제출 코드
• 2차원 배열을 채택
• 지각이 0회인 경우와 1회인 경우로 구분해 점화식 구축
• 지각이 0회인 경우는 가능한 시나리오 값만 더해서 갱신
• 지각이 1회인 경우가 다소 복잡한데 오늘 지각하는 경우, 출석하는 경우 다 고려해서 모든 dp값을 다 더해주면 됩니다.

QnA

• 은성: 어떻게 점화식 도출했나요?

일일이 다 경우를 계산했으며 성수님의 3차원 배열을 참고하여 도출했습니다.

• 동휘: 발상의 전환으로 지각이 한번도 없고 결석을 세 번 연속하지 않는 경우를 계산한다면 1차원 배열로의 풀이도 가능하답니다

우와 대단하네요!
세연: 어떻게 접근하셨나요?
Chat GPT의 도움을 받았습니다

Reference

[ghpark7]

발표자: 세연 (문제: BOJ 5052 전화번호 목록)

내용

• 해당 문제 제출 코드
• 트라이를 사용하지 않고, 문자열 사전순 정렬을 통해 문제 해결
• 안되는 경우는 하나만 찾으면 되므로, sort 후 연속된 두 개를 계속 비교 (TIP! startwith를 사용하면 간단하게 구현 가능)
• 시간 단축을 위해 문자열을 숫자로 바꾸고자 했지만 그 경우 0으로 시작하는 변수가 발생하기 때문에 파기했어요

QnA

• 트라이보다 훨씬 빠른데요?

그렇군요!

Reference

[ghpark7]

발표자: 은성 (문제: BOJ 1507 궁금한 민호)

내용

• 해당 문제 제출 코드
• 플로이드 워셜 알고리즘을 역으로 거슬러 가야함
• 플로이드 워셜을 한바퀴 돌릴때 갱신이 이루어지면 불가능한 경우로 판단해 0 출력
• 어딘가를 거쳐 가는 거리가 직행 거리와 동일하다면 직행 간선은 없어도 되는 것으로 판단
• 일반 플로이드 워셜과의 차이점은 k가 반복문의 가장 깊은 곳으로 들어가야 편리합니다. (TIP. i와 j를 고정해 놓고 k값을 바꿔가면서 하는게 유리하기 때문!)

QnA

• 용범: 도로의 갯수가 최솟값이 아니라는 조건은 왜 주어진 걸까요?

지금은 다 연결되어 있으니 최솟값이 아니라는 점을 명시한 것입니다.

Reference

[ghpark7]

발표자: 권민 (문제: BOJ 2470 Two 용액)

내용

• 해당 문제 제출 코드
• Two pointer기법 활용 (TIP. 왼쪽 오른쪽을 따로 컨트롤)
• 투포인터를 사용하지 않겠다면 명확하지만 길이가 길어지는 정렬 문제 풀이
• 절대값을 활용해서 붙어있는 값들의 합의 최솟값을 확인해봤습니다.

QnA

• 지인: 투 포인터 방식도 정렬한거 아닌가요?

오, 그렇네요!

Reference

[ghpark7]

발표자: 동휘 (문제: BOJ 25947 선물 Discount)

내용

• 해당 문제 제출 코드
• 우선순위 큐를 세 번 활용
• 물건을 싼 것부터 사면서 지나가다가 현 물품을 살때 예산 오버하면 할인쿠폰을 점검
• 만약 할인받은 제품이 있었다면 할인받은 구매 물품 중 가장 싼 것의 할인혜택을 취소하고, 현 물품에 할인을 적용
• 지금까지 구매했던 물품 중 가장 비싼 상품에 혜택을 적용하는 것이 유리하므로 우선순위 큐에서 갱신해가며 도출
• 우선순위 큐 세개의 활용이 너무 복잡해 Chat GPT를 활용해보니 물건을 sort시킨 뒤 이를 반값을 적용해서 누적합과 그리디 알고리즘을 활용합니다.

QnA

• 동휘: 2-1-1번 경우에서 a가 0이면 안해도 되는 거 아닌가요?

네, 안하셔도 되지만 모든 경우를 그냥 돌려봤습니다.

Reference