WEEK01 알고리즘 TIL(3월14일 금요일)

앞으로 한 달간 알고리즘에 대해 공부한 내용을 TIL로 포스팅할 예정이다.
컴퓨터 시스템이라는 책을 1-4까지 읽고 백준으로 알고리즘 문제를 풀었다.

 

본격적인 백준 문제를 풀었다. https://github.com/prtky/JungleBackjoon 해당 링크로 내가 풀었던 내용을 주석과 함께 올렸다. 주석을 달면서 해석을 쓰는데 시간이 오래걸릴 수 있지만, 설명을 달면서 내가 이해했는지 다시금 이해할 수 있을거라 생각한다.

 

2번 문제(10869) 사칙연산

한줄에 값을 입력해서 사칙연산 값을 구하는 문제이다.
한줄에 입력시, map을 통해 같은 줄에 입력 값을 줄수 있다. map(function, iterable)을 통해 펑션은 각 요소에 적용할 함수, 인터에이블은 함수를 적용할 데이터 집합이다. 인풋을 받아 공백만큼 split 한 후 map함수를 통해 int를 바꿔준다.(x,y,w,h = map(int, input().split()))
또한 나눗셈의 몫만 구할 때는 /가 아닌 //로 구한다. /는 일반적인 나눗셈으로 소수점까지 나온다.

 

3번 문제(2588) 곱셈

A값과 B값 3자리수를 곱하는 과정을 표현하기.
막막한 점은 3자리 수 곱하기 3자리 수를 할 때, 각각 자리를 곱한 값을 어떻게 표현 해야하는가? 이다. 솔직히 수학도 그렇게 잘하지 않고 파이썬의 리스트형을 잘 쓰면 될 것 같은데 어떻게 풀이할 지 아이디어가 생각 나지 않았다. 그래서 여러 블로그 글을 참고 했고, 좋은 아이디어가 있었다.
이 문제를 풀기 위해서는 A를 정수로 처리하고 B를 문자열 형태로 취급해서 각 자리를 뽑아낸 다음 각 자리 수를 정수형으로 변환해 곱해야된다는 사실이다. B를 문자열로 해서 일의 자리 숫자, 십의 자리 숫자 등 나누어서 각각 곱하면 된다. 문자형이 었기 때문에 자연수로 바꿀 int 정수 자료형으로 변환해야한다. 또한 맨 오른쪽 수부터 계산해야하므로 리스트 2부터 시작이다. 참고로 리스트에서 첫번째 자리 수는 0이다.
for문으로 루프 돌려서 풀수도 있다.

근데 같은 팀원에 한 분이 엄청난 방법을 생각하신게 있었다. 각자리 수를 100, 10, 1의 값으로 나눠서 값을 추출하는 것이다. 이러면 int형 변환을 쓰지 않아도 된다. A 값은 그대로 놓고 다른 B값을 10자리 곱해서 값 추출하고 10자리에서 몫만 꺼내 곱하고 100자리 곱해서 값 추출하는 형식으로 답을 구한다. 최종적으로 곱하면 답이 차례대로 나온다. 굉장히 수학적 관점에서 본 풀이여서 신기했다. 알고보니 수학교육과 출신이셨다. 팀플을 하면서 다른 풀이법이 존재함에 다양성을 느낄 수 있었다.
https://like-a-happy-cat.tistory.com/10 해당 글을 참고 해서 풀었다.

 

4번 문제(9498) 시험성적

받은 시험 성적을 커트라인에 따라 표현하는 것이다.
시험 점수 값은 0보다 크거나 같고 100보다 작거나 같다는 전제와 각 A,B,C,D 등으로 성적을 매길 수 있어야한다.
시험 점수 값 범위 지정을 먼저 한해야 할까? 일단 관계 연산자로 커트라인 끊어서 if문으로 성적을 매기면 될 것 같다. 나는 조건문 if문을 통해 입력값을 특정 범위에 따라 정해진 출력값을 출력하도록 구상했다. 값 제한은 관계연산자로 하고 if문을 조금 이나마 줄이기 위해 or 논리 연산자를 사용헀다. 어렵지 않게 풀었다.

 

5번 문제(2753) 윤년

윤년을 구하는 문제이다.
윤년은 4의 배수이고 100의 배수가 아닐 때, 4의 배수이고 400의 배수일 때를 말한다.
두가지 조건을 if와 논리 연산자를 쓰면 되지 않을까 싶다.
윤년의 케이스 두가지의 경우 1을 출력하고 나머지 경우를 0으로 출력하게 하면된다.

 

6번 문제(1085) 직사각형 탈출

직사각형 탈출 문제이다.
(0,0), (x,y), (w,h)에서 직사각형 크기는 (w,h)가 결정 짓는다. 그럼 (x,y) 기준으로 직사각형의 모서리에 도달하는 최단 거리를 구하는 문제이다. 내가 봤을땐 x,y기준으로 0,0 뺀 값하고 w, h를 뺀 값하고 비교해서 제일 작은 값을 표현하면 되지 않나 싶다.
파이썬의 내장함수 min, max를 사용하여 간단하게 표현했다. map을 통해 한줄에 여러 값을 입력 받을 수 있게 했다.

 

7번 문제(2739) 구구단

구구단 문제이다.
출력을 N으로 받고, 출력형식과 같게 N1부터 N9까지 출력하면 된다. 내 생각엔 노가다 형식의 코드를 써도 되지만 코드 최적화를 위해 for문을 통해 반복문으로 표현해 볼까 한다.
생각보다 간단하지 않았다. for의 range를 걸어서 9단까지 반복하도록 설정했다.
변수 N이나 여러 값(N * (int(i+1)))이 정수 형이어서 출력을 하지 못해 str로 형 변환을 해서 출력하도록 했다.

 

8번 문제 (10950) A+B - 3

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성합니다. 조건이 있다. 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (0 < A, B < 10)이거는 T라는 테스트 케이스를 설정하고 그만큼 수를 받고 결과를 표현하는 것을 어떻게 하는지 몰라 헤멧다.
for range에서 range를 T로 설정하고 입력을 받으면 테스트 케이스 횟수를 지정 가능하다. 그러고 입력 받을 식을 쓰면 된다. 난 한번에 입력하고 한번에 나와야하는 줄 알았는데, 그건 아니었다.

 

9번 문제(2438) 별찍기 - 1

첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제이다.
for 루프문으로 +1 씩 증가시키면서 별을 찍도록 하면 될 것 같다. 별을 찍으려면 range를 사용해서 범위를 지정해서 출력할 수 있게끔해야한다. 주의해야되는 점은 range의 마지막변수-1이라는 것이다. range에서 마지막변수-1 까지 출력하여 3를 입력하면 2까지 출력되므로 입력값+1을 해준다.
제출을 했는데, 문제 답이 잘 나오는데도 출력 오류가 났었다. 알고 보니 내가 * 사이에 공백을 넣어서 그런거였다.

 

10번 문제(10871) X보다 작은 수

정수 N개로 이루어진 수열 A와 정수 X가 주어진다. 이때, A에서 X보다 작은 수를 모두 출력하는 프로그램을 작성하는 문제이다. list의 여러값 인풋 받는 것도 map을 사용하여 자료형을 int로 전환해서 한 줄로 넣을 수 있다.
맨처음에는 리스트 요소를 꺼내서 비교를 해서 작으면 뽑아 내는 것을 어케하는지 몰랐다. 더욱 조사해서 알아보았는데, 문제의 핵심인 리스트에 있는 값을 자연수와 비교하려면 for문과 if문을 쓴다. 정수 N개라는 제한을 걸어야하므로 for의 range(N)으로 범위를 제한하고, if로 X와 비교해 작은 리스트의 요소만 출력되게 한다.

 

 

18시 ~ 19시
맛있는 콩불을 먹고 왔다. 전부터 계속 풀고있는 백준 10번 문제를 풀어봤다. 하다가 집중이 안되서 커피를 사왔지만 정답을 맞췄다. 블로그 참조도 했었다. 뭔가 이런거 푸니까 하나 풀때마다 희열감이 알게 모르게 있다. 한 개 못풀 때 스트레스 받긴한데, 코치님이 어제 말씀하신 거인의 발자취를 따라가는 거기때문에 못할 수 있고 좌절하지 말라는 조언을 되새기며 진행하고 있다.

 

19시
팀원들과 지금까지 풀었던 백준 문제 코드 리뷰를 했다. 각자만의 코딩 스타일이 있고 다양한 방식으로 푸셨다.
특히, 같은 팀원 중에 수학교육과 한 분이 계셨는데, 수학적으로 접근하시는게 멋있으셨다.

팀원과 이야기하며 갑자기 든 생각.
x,y,w,h = map(int, input().split())로 한줄에 여러 자료형을 지정해서 입력 받을 수 있는데. 같은줄에 각각 다른 자료형을 출력하려면 어떻게 해야하는가? → map은 일괄 처리 기능이라 다른 자료형 받으려면 각각 선언해줘야한다.라는 답을 받았다.

 

20시 30분
백준을 이어서 풀어보겠다.

11번 문제(2562) 최댓값

9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성해야한다.
9개의 다른 수를 받고 max를 사용한 다음에 몇 번째 수인지 출력하면 되겠다. 새리스트를 만들고 append를 통해 입력 받은 값을 리스트에 추가한다. 인덱스를 통해 리스트에서 원하는 값이 몇번째 수인지 출력 가능하다. 이렇게 하면 답은 제대로 나오는데, 틀렸다고 해서 찾아봤더니 리스트 인풋 받는 입력값이 자연수여서 int로 받아야한다고 한다.

문제를 효율적으로 풀기 위해 input.txt를 사용해서 파이썬에 입력값을 효율적으로 넣으려 했는데 파이썬 환경설정이 안잡혀 있어서 파이썬 깔고 맥 자체에 환경설정하느라 시간이 좀 걸렸다.그래도 백준에 있는 입력값 하나씩 넣느라 시간이 좀 걸렸는데, 앞으로 효율적으로 할 수 있게 되서 다행이다.

 

12번 문제(8958) OX퀴즈

테스트 케이스는 for in range로 설정하고 if문으로 문자열 불러 와서 O와 X를 관계 연산자로 하면 될 것 같다.
문제는 연속적으로 숫자를 맞추면 1이 추가된다(1+2+3 ...) 이걸 count를 사용해서 해결하나? ++i 같은 걸로 해결할지 고민이다. 문자를 연속적으로 맞추면 1을 카운트해서 올려준다음 더해주고, 만약 x가 나오면 1로 다시 초기화한다. 여기서는 더하고 변수에 재 할당하는 +=의 역할이 중요하다. 이거는 설명하기 좀 어려우니 주석 달린 코드로 설명을 하겠다.

x = int(input())

for i in range(x):
    OX = input() # 기본 인풋이 str이다.
    score = 0
    sum_score = 0  # 각 들여쓰기 할때마다 0으로 초기화한다.
    for i in OX :
        if i == "O":      # O가 나오면 더해줄 값이 1이 추가 된다. 1을 더한값이 score에 다시 할당된다.
            score += 1
        else:
            score = 0     # 그외의 값이면 0으로 초기화한다.
        sum_score += score   # 연속적으로 맞은 만큼 더해진다.
    print(sum_score)

# 답이 정상적으로 안나와서 확인해 봤더니 줄바꿈 문제가 있었다. 줄바꿈을 어떻게 하느냐에 따라 값이 달라진다.
# 좀 많이 어려운 문제였다. O 개수만큼 +1씩 더 더해지니 어려웠다. 나중에 한번더 이해해야겠다.

 

13번 문제(4344) 평균은 넘겠지

평균 구해서 평균을 넘는 학생의 비율을 계산하는 것이 주 핵심이다. 근데 두번째 줄부터 앞에 학생 수가 추가 되서 어떻게 입력을 받아야하는지 막막하다.
문제가 좀 복잡해서 해당 문제도 코드와 함께 설명하겠다.

C = int(input())

for _ in range(C):  #for문에서 _를 사용하면 변수가 필요 없이 밑에 과정을 반복한다.
    data = list(map(int, input().split()))  # 한 줄 입력받고 리스트 변환
    N = data[0]  # 첫 번째 값은 학생 수이므로 data 리스트 첫값을 N으로 뺀다
    scores = data[1:]  # 나머지 값을 학생들의 점수로 받는다.

    avg = sum(scores) / N  # 평균값 구하기
    avg_up_sum = sum(1 for score in scores if avg < score)
    # 이부분이 좀 어렵다. 먼저 for score in scores로 scores의 내부 요소를 score로 불러온다.
    # 그 후 1 for ~ 에 따라 평균과 비교를 해서 크면 1을 더한다.
    # 결론적으로 평균보다 높은 갯수가 avg_up_sum이 된다.
    print("%0.3f%%"% ((avg_up_sum / N)*100)) 
    # 백분율이므로 100을 곱해주고 %0.3f%% 를 통해 소수 3번쨰 짜리까지 백분율을 추출한다.

문제 너무 어려워진다. 솔직히 수학 못하는데… 약간 처음부터 어떻게 구축해 나가야할지 턱 막힌다.
GPT를 사용해서 도움을 좀 받는데, 계속 어려운 공식 써서 자력으로 작성하려 노력하고 있다.

 

14번 문제(2577) 숫자의 개수

다 풀긴 했는데 새벽2시라 머리가 안돌아가서 토욜날 정리했다. (하드 코딩 해버렸다 ㅎ...)
세 개의 자연수 A, B, C가 주어질 때 A × B × C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하는 것이다. 일단 3자리를 받을 수 있는 인풋을 받고 곱한다. 그럼 값이 나올 것인데 나온 값을 쪼개서 리스트화한다.(len쓰면 될 것 같다) 리스트에서 0~9까지 추출해서 갯수를 센다.

A = int(input())
B = int(input())
C = int(input())
ABC = A * B * C

x = []
for i in str(ABC):
    x.append(i)

cnt0 = x.count("0")
print(cnt0)
.
.
.

원래는 각 숫자를 카운트하는 부분을 일일이 반복 했었다. 너무 단순 무식하게 써서 for문으로 바꿀 방법을 찾고 있다. for문은 1부터 9까지 반복하는데, 그걸 str형식이랑 비교해서 추출할 수 있는지 몰랐다.
인터넷에서 글 찾고, 고민 고민하다가 GPT한테 물어 봤는데 반복하는 i를 str으로 변환해서 카운트하면 되는 간단한 문제였다...

15번 문제는 토요일에 풀 예정이다. 다른 분들이 빠르게 푸셔서 진도에 안맞을까 걱정이다. 일단 알고리즘 입문 책을 한번 읽어보려고 한다.