오늘은 상당히 알찬 하루를 보냈다.
나만의 무기 만들기를 준비하기 위한 새로운 언어 습득도 열심히 했고,
팀원들과 끊임없는 토의를 통해 역할을 분담하고 기획 자체도 확장할 수 있었기 때문이다.
무엇보다도 우리가 구현하려는 핵심 기능에 대한 몇 가지 대안을 생각해낸 것이 아주 의미있었다.
알고리즘 풀이도 열심히 했는데, 특히 '최고의 집합' 문제는 처음에 전혀 접근을 못하다가, 어느순간 한 번에 풀었다. 진짜 머리를 싸매고 고민했는데, 너무 기뻤다. 말 그대로 유레카 ! ! 풀고나서 다른 사람의 풀이를 봤는데, 다른 사람의 추천을 받은 답안보다 내 풀이가 더 직관적이고 좋아보였다. 물론 내 풀이에 대한 반례가 있다면 얘기가 달라지겠지만...
나만의 무기 만들기
오늘은 저녁 전까지는 Flutter와 DART에 대한 학습을 각자 진행해보았다. 주로 참고한 강의자료는 '코딩애플' 에 올라온 무료 강의인데, Flutter를 써서 다양한 것을 연습삼아 구현해보니 새로웠다. 저녁 이후에는 아이디어를 좀 더 구체적으로 확장하고, 역할을 분담했다. 우리가 구현할 서비스에는 일종의 '카드'가 들어가는데, 그 카드를 생성, 편집, 수정하는 부분을 다른 2명의 팀원과 함께 맡았다. 우리의 목표는 다음 주 수요일까지 일단 MVP의 일부를 끝내는 것인데, 아마 가능할 것 같다. 시간을 효율적으로 써서 열심히 한다면야 뭐든지 가능하니까...
웹프로젝트 경험도 사실상 정글와서 해본 미니프로젝트가 처음인데, 우리가 진행할 프로젝트는 웹이 아니라 앱이다. 그래서 걱정이 따르는 것도 사실이지만, 웹프로젝트도 정글와서 처음이지만 잘 해냈으니 이번에도 해낼 것이다. 조급해 하지 말고, 천천히 하나하나 해봐야지 ! 경험이 좀 있는 팀원들이 있어서 많이 배워갈 것 같다.
저번 미니 프로젝트에 이어 이번에도 느끼는 점이지만, 3전공에서 가져가는 이점이 분명히 있는 것 같다. 좀 더 다양한 관점에서 문제를 바라볼 수 있고, 특히 경영학 전공이 인사이트를 파악하는데 큰 도움이 되기 때문이다. 장차 개발자로 커리어를 쌓아나갈 때, 비즈니스 인사이트와 커뮤니케이션 역량을 갖춘 개발자 로 나라는 브랜드를 차별화하고 싶다. 경영학 + 신문방송학 + 융합소프트웨어 라는 3가지 전공을 다 활용할 수 있는 직업이 바로 개발자가 아닐까 싶다....! 🤗
알고리즘 스터디
오늘도 어제에 이어 백준 문제를 풀었다.
그리고, 시간이 남아서 일요일에 다른 스터디원들이 풀었던 문제도 풀었다.
백준 - 흙길 보수하기
우선 백준에서는 흙길 보수하기 라는 문제를 풀었다.
자주 접해본 유형의 문제였다. 하지만 완전히 똑같지는 않았다.
일단 마지막으로 설치한 널빤지의 끝지점보다 현재 덮어줘야 할 웅덩이의 시작지점이 뒤라면, 거기서부터 다시 설치하도록 하는 로직을 생각해내는 것이 관건이었던 것 같다. 만약 널빤지의 길이는 1, 한 웅덩이의 끝지점이 10 위치이고 다음 웅덩이의 시작지점이 20 위치라고 가정한다면, 굳이 11~19까지는 널빤지로 메워줄 필요가 없기 때문이다. (포인트 1)
또한, 각 위치가 1,000,000,000 이라는 것에서 유추할 수 있듯이 널빤지를 하나하나 설치하면 시간초과가 난다는 것도 생각해야 한다. 만약 어떤 하나의 웅덩이에 대해 시작 위치는 0, 마지막 위치는 10000이라고 생각해보자. 주어진 널빤지 L이 1이라면, 10,000개의 널빤지가 필요하다. L이 2라면 5,000개의 널빤지가 필요하다. 이걸 while문로 하나하나 설치하면 널빤지의 개수만큼 루프가 돌아야하므로, 매우 비효율적이다. 옛날에 비슷한 유형을 하나하나 설치해가는 식으로 처리했다가 자꾸 시간초과가 나서 왜 그런가 했었기에.... 같은 실수를 반복하지 않았다. (포인트 2)
이러한 2가지 포인트를 바탕으로, 다음과 같이 코드를 구성했다.
# 백준 # 흙길보수하기 # 5시 13분 시작 # 5시 33분 끝 # 20min sol
import sys
input = sys.stdin.readline
N, L = map(int, input().strip().split())
pools = [list(map(int, input().strip().split())) for _ in range(N)]
# 정렬 후에, start가 더 작아지면 안될듯. 따라서 start가 우선순위, end가 후순위.
pools.sort(key = lambda x: (x[0], x[1]))
def sol(pools, N, L):
now = 0
cnt = 0
for start, end in pools:
# 포인트 1
if start > now:
now = start
if end <= now:
continue
# 포인트 2
need, rest = divmod(end - now, L)
if rest:
need += 1
end += L-rest
cnt += need
now = end
return cnt
print(sol(pools, N, L))divmod를 사용한 이유는, 현재 기준에서 널빤지가 얼마나 필요한지를 한번에 구할 수 있기 때문이다.
만약 나머지(rest)가 없다면, 몫(need)만큼만 바로 널빤지 개수에 반영해주면 된다. 반면 나머지(rest)가 있다면, 몫(need)+1만큼을 널빤지 개수에 반영해주면 된다.
rest가 있는 경우에는 end도 조정해주어야 한다. 만약 널빤지의 길이(L)가 3이고, 어떤 웅덩이의 시작이 0, 끝이 4라고 가정해보자. divmod(4-0, 3) = 1,1 이다. 즉, L(3)로 나눴을 때 현재 위치 기준으로는 나머지가 1이다. 그럼 딱 나눠떨어지게 하려면, 3-1 = 2를 더해줘야 한다. 그래서 현재위치 4에 L-rest = 2 를 보정해줘서 6으로 만들어줘야 하는 것이다. 이를 한 줄로 요약해보자면, 나머지가 있으니 널빤지를 하나 추가로 설치해준 결과 널빤지 2개가 각각 0~3, 3~6 범위에 설치되었다.
이렇게 해서 제출해주니, 한 번에 풀렸다. 굿굿 !
다만 풀고나서 보니 N은 맨 처음에 input을 받을 때 외에는 사용을 안해서...
sol의 인자로 넣을 필요는 없었던 것 같다:)
프로그래머스 - 최고의 집합
시간이 남아서 지난 일요일에 데이트 이슈로 불참한 스터디에서 푼 문제를 커버했다.
최고의 집합 이라는 문제인데... 이렇게 생겼다.
처음에 보자마자, 머리가 멍-했다. 아니 이걸 어떻게 구하지?
아니, 조합이 진짜 너무나도 다양하게 있을텐데... 슬쩍 실행 눌러보니 역시나 효율성도 있었다.
이 문제는 다른 5명의 스터디원이 모두 푼 문제라서, 와 다들 어떻게 풀었지...하다가,
야 ! 나도 할 수 있어! 라는 마인드로 다시 접근했다. 고민 후 15분 만에 뭔가를 적기 시작.
우선 첫 번째로 떠오른 아이디어는, 자연수의 개수 n이 총합 s보다 크면 안된다는 것이다.
자연수 n개로 만들 수 있는 가장 작은 s는 n이다. [1,1,...1] 이런 형태가 최소집합이니 말이다.
따라서, 이를 우선 처리해주었다.
def solution(n, s):
if n > s: return [-1]그럼, 나머지 경우를 어떻게 할 것인가....... 우선 주어진 케이스를 살펴보았다. s가 9일때와 s가 8일때는 한 끗 차이라는 생각이 들었다. 그리고, 둘 다 4를 포함하고 있다. 보니까 4는 s를 n으로 나눈 몫, 즉 s // n 에 해당하지 않나? 이게 두 번째 아이디어였다.
세번째 아이디어는, 곱셈을 하는 경우를 생각해보았다. s가 10이고 n이 2라고 할 때, 5 x 5 를 이길 수 있는 조합은 없다. 즉, 최대한 s // n이 많이 나오는 것이 유리하다고 생각했다. 그러면 [s//n, s//n, ... s//n] 은 무조건 만들고 시작해야겠다는 생각이 들었다.
마지막 아이디어는, s % n, 즉 s를 n으로 나눴을 때 나머지가 존재하는 경우였다. 머리에 떠오른 예시는 s가 10005, n이 10000인 경우였다. s // n = 1이고, s % n = 5이다. 그럼 우선 [1,1,1,...,1]을 만든 후에, 나머지가 5니까 다섯개만 +1씩 해주면 되지 않을까? 라는 생각이 들었다. 1x3 보다는 2x2가 크고, 1x1x4 보다는 2x2x2가 크니까, 그런 흐름에 따라 특정 숫자에 +1 이상의 값, 즉 +2~+5 를 해주는 것은 고려하지 않아도 될 것 같았다.
따라서 최초로 구상해서 제출한 코드는 다음과 같다. 심플!
# 프로그래머스 # 최고의 집합 # 5시40분 시작 # 5시57분 끝 # 17min sol # 이걸 ? ? ?
def solution(n, s):
answer = []
if n > s:
return [-1]
magic, rest = divmod(s,n)
if rest:
answer = [magic] * (n-rest) + [magic+1] * rest
else:
answer = [magic] * n
return answer 이걸 좀 더 짧게 바꿔보자면, 아래와 같이 3줄로도 가능할 것이다.
def solution(n, s):
if n > s: return [-1]
magic, rest = divmod(s,n)
return [magic] * (n-rest) + [magic+1] * rest if rest else [magic] * n코드를 제출한 결과는 .......
효율성도 뛰어나다. 오케이!
오늘도 성공했다 :)
내일도 나만의 무기 만들기, 알고리즘 스터디 모두 성실히 해내보자!
