[2023 알고리즘 스터디] 3조 #1주차 - 백준 1316, 1475, 2960, 3085번 코드 리뷰

3조(박제형, 선병범, 성동현, 신의석) 알고리즘 스터디 블로깅은 돌아가면서 진행하기로 했습니다.

1주차를 맡게된 신의석입니다.

 

 

1316번 - 그룹 단어 체커

1316번: 그룹 단어 체커 (acmicpc.net)

1316번: 그룹 단어 체커

• 알고리즘 유형: 구현, 문자열
• 문제: 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.
• 그룹 단어란? 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다.

예제 입력

3
happy
new
year

예제 출력

3

• 예제 설명: 예제를 기준으로 3을 입력한 후 3개의 단어를 입력하면 3개 중 3단어 모두 그룹단어로 판단해 3을 출력했다.

# 그룹 단어 체커
# https://www.acmicpc.net/problem/1316
num = int(input())

count=0
for i in range(num):
    w = input()
    wBool =1
    for j in range(len(w)-1):
        if w[j]==w[j+1]:
            wBool=1
        elif w[j] in w[j+1:]:
            wBool=0
            break
    if wBool:
        count +=1

print(count)

 

• 풀이
  그룹 단어임을 확인해주는 wbool을 따로 선언
  각 단어에서 연속적으로 같은 철자일 경우 wbool은 1, 연속적이지 않고 같은 철자가 단어안에 있을 경우 0으로 바뀜
  한 단어 탐색을 마치고 wbool의 값에 따라 count 값이 늘어나거나 유지
• 아이디어
  한 단어를 다 탐색한 이후에 그룹단어 여부를 판단할 수 있으므로 wbool이라는 변수를 선언

 

1475번 - 방 번호

1475번: 방 번호 (acmicpc.net)

1475번: 방 번호

• 알고리즘 분류: 구현
• 문제: 다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)
• 입력: 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.
• 출력: 첫째 줄에 필요한 세트의 개수를 출력한다.

# 방 번호
# https://www.acmicpc.net/problem/1475
num = input()
numList = []
for i in range(0,10):
    numList.append(num.count(str(i)))

special = (numList[6]+numList[9])//2 + (numList[6]+numList[9])%2
numList[6] = special
numList.pop()
print(max(numList))

• 풀이
  num에 들어온 숫자에서 0부터 9까지의 숫자의 개수를 numList에 넣음
  special에 6과 9를 처리한 값을 넣고 numList 리스트에 6번째를 special로 초기화
  numList에서 9번째를 삭제
  numList의 최댓값 출력
• 아이디어
  index와 숫자가 동일할 수 있도록 list 넣기
  count 함수, max함수 사용

 

2960번 - 에라스토테네스의 체

2960번: 에라토스테네스의 체 (acmicpc.net)

2960번: 에라토스테네스의 체

• 알고리즘 분류: 수학, 구현, 정수론, 소수 판정, 에라토스테네스의 체
• 문제: 에라토스테네스의 체를 구현하면서 N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.
• 에라토스테네스 체란? N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
  1. 2부터 N까지 모든 정수를 적는다.
  2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
  3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
  4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
• 입력: 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)
• 출력: 첫째 줄에 K번째 지워진 수를 출력한다.

# 에라스토테네스의 체
# https://www.acmicpc.net/problem/2960
Num, K= map(int, input().split())
numList = []
for i in range(2,Num+1):
    numList.append(i)
order = 0
while True:
    if order>=K:
        break
    temp = min(numList)
    unit = min(numList)
    i = temp - 2
    while temp <= Num:
        if numList[i] == temp:
            order += 1
            if order == K:
                print(numList[i])
                break
            numList[i] = 1001
        i += unit
        temp += unit

• 풀이
  numList에 2부터 Num까지 넣음
  에라스토테네스의 체 알고리즘에 맞게 구현하면서 order이 K와 같아지면 그 숫자를 출력하고 루프탈출
• 아이디어
  Num과 비교할 temp, index와 temp를 변경해주는 unit을 min 함수로 정해주기
  min함수에 오류가 없도록 이미 뺀 숫자는 1001로 바꾸기

 

3085번 - 사탕 게임

3085번: 사탕 게임 (acmicpc.net)

3085번: 사탕 게임

• 알고리즘 분류: 구현, 브루트포스 알고리즘
• 브루트포스 알고리즘이란? 완전탐색 알고리즘으로 모든 가능한 경우의 수를 탐색하면서 해답을 구하는 알고리즘
• 문제
  가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
  사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
• 입력
  첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
  다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
  사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
• 출력
  첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

예제 입력

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력

4

예제 설명: 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.

# 사탕 게임
# https://www.acmicpc.net/problem/3085
def eatMax(cList):# 최대로 먹을 수 있는 값을 출력하는 함수
    Max = 1
    for i in range(num):
        countrow = 1
        for j in range(num-1):
            if cList[i][j] == cList[i][j+1]:
                countrow+=1
                Max = max(Max,countrow)
            else:
                countrow = 1
    for j in range(num):
        countcol = 1
        for i in range(num-1):
            if cList[i][j] == cList[i+1][j]:
                countcol += 1
                Max = max(Max,countcol)
            else:
                countcol = 1
    return Max

num = int(input())
cList =[]

for i in range(num):# C,P,Z,Y가 들어오면 이차원 배열의 형태로 리스트 생성
    k=input()
    k = k.replace('C', ' C ')
    k = k.replace('P', ' P ')
    k = k.replace('Z', ' Z ')
    k = k.replace('Y', ' Y ')
    k = k.split()
    cList.append(k)

result = 0
for i in range(num):#행끼리 교환하면서 최대개수 result에 초기화
    for j in range(num-1):
        cList[i][j], cList[i][j+1]= cList[i][j+1],cList[i][j]
        temp = eatMax(cList)#eatMax에서 나온 값을 temp에 저장 후
        if temp>result:#result와 비교 후 result값 초기화
            result = temp
        cList[i][j], cList[i][j+1]= cList[i][j+1],cList[i][j]

for j in range(num):#열끼리 교환하면서 최대개수 result에 초기화
    for i in range(num-1):
        cList[i][j], cList[i+1][j] = cList[i+1][j], cList[i][j]
        temp = eatMax(cList)#eatMax에서 나온 값을 temp에 저장 후
        if temp>result:#result와 비교 후 result값 초기화
            result = temp
        cList[i][j], cList[i+1][j] = cList[i+1][j], cList[i][j]
print(result)

• 풀이
  주석 참조
• 아이디어
  max함수로 행과 열을 비교해서 최대로 먹을 수 있는 값을 반환하는함수를 생성
  알고리즘 분류가 브루트포스임으로 일일이 다 비교하는 루프문 생성
  result를 초기화해서 행과 열끼리 다음 것과 바꾸고 거기서 eatMax 리턴값과 result를 비교하면서 진짜 최댓값 얻기

 

지금까지 백준 알고리즘을 풀어봤습니다.

 

저희 3조는 4문제에 관한 각자의 코드를 설명하면서 비교하고 서로 질문하는 방식으로 스터디를 진행했습니다.

그 과정에서 새롭게 알게되는 것이 늘어나고 코드를 고쳐보는 시간을 가질 수 있었습니다.

 

조원들의 코드를 볼 수 있는 github

FOSCAR-Algorithm/Baekjoon (github.com)

GitHub - FOSCAR-Algorithm/Baekjoon

이렇게 1주차 스터디를 진행해봤습니다.

서로의 코드를 좀 더 자세히 보고 기록할 수 있게 잘 진행됐으면 좋겠습니다!

감사합니다.