본문 바로가기

학습 노트/알고리즘 (Python)

Q1. 방 배정 하기

서론


파이썬 문법을 마무리 한 날 남은 시간 동안 문제를 한 번 풀어보기로 했다.

문제는 군 복무 중이던 시절 남는 시간에 공부라도 해보자 해서 구해뒀던 한국정보올림피아드 초등부 문제로,
지금은 주관이 바뀐 탓인지 홈페이지에서 구할 수가 없다.
C언어는 1학년때 배웠었고, 입대한 건 2학년이 끝난 후였고, 공부를 시작한 건 상병이 다 돼서였으니
이미 기억의 저편으로 사라져 버린 언어에 대한 지식과 손 코딩의 한계로 딱히 제대로 건드려 볼 수가 없었다.

실제 문제 풀이는 Python으로 작성할 생각이고,
적당한 코드 리뷰 후에는 Swift로 옮겨볼 생각이다.

 

본론


문제

Egg's

import math
import datetime as date

#initial data
tot_num = 0
max_for_room = 0

#generate student data
class student:
  data = [[0,0,0,0,0,0],
          [0,0,0,0,0,0]]
  def __init__(self, gender, year):
    self.gender = int(gender)
    self.year = int(year) - 1

    student.data[self.gender][self.year] += 1

#input K, N
while (1 > tot_num) or (tot_num > 1000):
  tot_num = int(input("type total student amount: "))
while (1 > max_for_room) or (max_for_room > 1000):
  max_for_room = int(input("type max for room: "))

#input S, Y
for _ in range(tot_num):
  inputVal = input("student info: ")
  spliceVal = inputVal.split(" ")
  
  student(spliceVal[0], spliceVal[1])

#cal room amount
def roomCal(param):
  result = 0

  for gender in param:
    for year in gender:
      result += math.ceil(year/max_for_room)

  print(result)

#logging start time
str_time = date.datetime.now()

#process
roomCal(student.data)

#logging end time
end_time = date.datetime.now()

#cal processing record
print(end_time - str_time)
결과

type total student amount: 3
type max for room: 3
student info: 0 3
student info: 1 5
student info: 0 6

3
0:00:00.000192

중간에 발생한 컴파일러 오류를 포함해 한 시간 정도 걸린 것 같다.
우선 문제에서 필요한 정보를 거르는데 시간이 좀 걸렸고,
입력을 제대로 받아오는 것이 생각보다는 오래 걸렸던 것 같다.

입력이 됨과 동시에 입력된 값을 통해 클래스 변수를 통해 데이터를 구조화 하도록 구현했다.
이후 구조화 된 데이터를 계산해 출력한다.

간단한 코드임에도 시간이 많이 소요된 부분은 처참한 결과다.

 

Whale's

import math

student=input("총 학생 수 :",)
inStu=input("들어갈 학생 수 :",)

getStu=[]
sumStu=[0,0,0,0,0,0,0,0,0,0,0,0]
devStu=[]

for i in range(int(student)) :
  sex=input("남녀 표시(여자:0, 남자:1) :", )
  grade=input("학년 :",)
  stu=[grade, sex]
  getStu.append(stu)

print(getStu)

for j in range(int(student)) :
  if int(getStu[j][1])==0:
    a=(int(getStu[j][0])*2)-2
    sumStu[a]=sumStu[a]+1
  elif int(getStu[j][1])==1:
    b=(int(getStu[j][0])*2)-1
    sumStu[b]=sumStu[b]+1
  else :
    print(getStu[j][1])

# for k in range(len(sumStu)) :
#   re=int(sumStu[k])/int(inStu)
#   re2=math.ceil(re)
#   devStu.append(int(re2))

for k in sumStu :
  re=math.ceil(int(k)/int(inStu))
  devStu.append(int(re))

room=sum(devStu)

print("총 방의 수 :", room)
결과

총 학생 수 :3
들어갈 학생 수 :3
남녀 표시(여자:0, 남자:1) :0
학년 :3
남녀 표시(여자:0, 남자:1) :1
학년 :5
남녀 표시(여자:0, 남자:1) :0
학년 :6
[['3', '0'], ['5', '1'], ['6', '0']]
총 방의 수 : 3

배열을 적극적으로 사용했다.

역시나 입력부에서 문제가 생겨 확인하던 도중 input의 자료형이 String으로 고정돼 있다는 것을 놓쳐 해당 부분을 수정하고.
이후 비슷한 문제가 발생하는 경우 if-else 문을 사용해
사이드이펙트를 간편하게 확인할 수 있을 거라는 의견도 주고받아 반영이 된 모습이다.
연산부에서 코드 리뷰 후 지적했던 for문의 바인딩을 적극적으로 사용하도록 코드를 수정한 것도 확인할 수 있다.

 

Rabbit's

import math

print("인원 수와 방 최대 인원수를 적어주세요")
N, K = map(int, input().split())

student_list = []

print("성별(1 또는 0), 학년을 적어주세요")

for i in range(N):
    S, Y = map(int, input().split())
    student_list.append([S, Y])

a = [0,0,0,0,0,0]
b = [0,0,0,0,0,0]
boy_room = 0
girl_room = 0
room = 0

boy_list = []
girl_list = []

for i in range(N):
    if student_list[i][0] == 0:
        girl_list.append(student_list[i])
    elif student_list[i][0] == 1:
        boy_list.append(student_list[i])

#for i in boy_list:
#    a[i[1]-1] += 1
    
for i in range(len(boy_list)):
    for j in range(1,7):
        if boy_list[i][1] == j:
            a[j-1] += 1
            
for i in range(6):
    a[i] = a[i]/2
    a[i] = math.ceil(a[i])
    boy_room += a[i]
    
#for i in girl_list:
#    b[i[1]-1] += 1

for i in range(len(girl_list)):
    for j in range(1,7):
        if girl_list[i][1] == j:
            b[j-1] += 1
            
for i in range(6):
    b[i] = b[i]/2
    b[i] = math.ceil(b[i])
    girl_room += b[i]

room = boy_room + girl_room
print(room)
결과

인원 수와 방 최대 인원수를 적어주세요
3 3

성별(1 또는 0), 학년을 적어주세요
0 3
1 5
0 6

3

마찬가지로 배열을 적극적으로 활용했다.
각각의 배열에 대한 계산을 진행한 수 결과를 산출하는 방식이다.

마찬가지로 for문의 바인딩을 제대로 사용하지 못해 리뷰때 의견을 주고받았다.

 

결론


//
//  main.swift
//  algorithm_room
//
//  Created by Martin.Q on 2022/04/22.
//

import Foundation

var tot_num: Int = 0
var max_for_room: Int = 0

var data = [[0,0,0,0,0,0],
            [0,0,0,0,0,0]]

//input total student amount
while tot_num < 1 || 1000 < tot_num {
	print("type total student amount: ", terminator: "")
	if let input = readLine() {
		tot_num = Int(input)!
	} else {
		print("input must a number between 1 to 1000")
	}
}

//input max capacity
while max_for_room < 1 || 1000 < max_for_room {
	print("type max for room: ", terminator: "")
	if let input = readLine() {
		max_for_room = Int(input)!
	} else {
		print("input must a number between 1 to 1000")
	}
}

//structing data
func input_student(genderVal: Int, yearVal: Int) {
	data[genderVal][yearVal - 1] += 1
}

for _ in 0..<max_for_room {
	print("student info: ",terminator: "")
	let input = readLine()?.split(separator: " ")
	
	if let genderVal = Int((input?[0])!) {
		if let yearVal = Int((input?[1])!) {
			input_student(genderVal: genderVal, yearVal: yearVal)
		}
	}
}

//calculating room
func roomCal(param: [[Int]]) {
	var result = 0
	
	for gender in param {
		for year in gender {
			result += Int(ceil(Double(year)/Double(max_for_room)))
		}
	}
	print(result)
}

roomCal(param: data)

Python으로 작성한 코드를 Swift로 옮겼다.
특이사항은 Swift의 형 변환 문제로,
실제 방을 구하는 공식의 가독성이 심하게 나쁘다는 생각이 든다.
이후엔 이를 개선할 방안을 찾아봐야 한다.

실제 알고리즘을 풀어보니 몇 가지 문제가 있었다.

  • 문제에서 필요한 정보를 찾기가 아직 어렵다.
  • 한 문제에 소요되는 시간이 크다.

둘은 서로 상관있는 문제로 모여서 문제를 푸는 것은 비용 면에서도,
시간 효율 면에서도 나쁘다.

긍정적인 부분은

  • 서로 부족하지만 코드 개선과 좁아진 시야를 확보할 수 있다.

따라서 공부가 도움이 되긴 한다.

이에 따라 다음 시간부터는 실질적인 알고리즘 기술을 조금 더 다듬고,
문제 푸는 시간을 줄일 수 있도록 분야별로 정리된 난이도가 낮은 문제를 과제로 진행하고,
모이는 시간에는 코드 리뷰를 진행하는 것으로 가닥을 잡았다.

'학습 노트 > 알고리즘 (Python)' 카테고리의 다른 글

Stack #1  (0) 2022.06.04
선형 데이터 구조와 탐색  (0) 2022.05.03
Python #3  (0) 2022.04.18
Python #2  (0) 2022.04.15
Python #1  (0) 2022.03.23