본문 바로가기
SW Jungle [예림]/Algorithm

[WEEK02] DAY16 & TMI

by novxerim 2022. 10. 10.

https://velog.io/@yerimii11/WEEK02-DAY16 2021년 11월 17일에 작성된 게시글 아카이브입니다.  (사유: 블로그이전)

 

[WEEK02] DAY16 & TMI

11866 요세푸스 출력 형식 보다가 조금 더 공부하게 된 건.https://www.delftstack.com/ko/howto/python/list-without-brackets-python/a = 1,2,3,4,5,6a_str = str(elem) for e

velog.io


DAY16


11866 요세푸스 출력 형식 보다가 조금 더 공부하게 된 건.

* [] 없애고 출력

https://www.delftstack.com/ko/howto/python/list-without-brackets-python/

a = [1,2,3,4,5,6]
a_str = [str(elem) for elem in a]
print('<%s>'%(', '.join(a_str)))

→ <1, 2, 3, 4, 5, 6>


.join 뜻

['a', 'b', 'c'] 같이 스트링으로 구성된 리스트일때

스트링.join(스트링 리스트) 쓰면 스트링 리스트를 합칠때 사이사이에 조인 앞에 있는 스트링을 넣어줌

예시 ''.join(['a', 'b', 'c']) → 'ab***c'


a = "".join(str(y))
a = result[1:-1]
print('<'+a+'>')

 

 

Slicing


완성 코드

10830 행렬 제곱 (분할 정복)

행렬을 곱하는 법을 알고있어야 일반항을 구할 수 있었다.
1629 곱셈 문제도 그렇고 이게 몇 년 만에 보는 수학들이었는지¨

.
.

for문 속의 [0] * n과 [0 for i in range(n)] 의 차이점

  • for문으로 [0]*n을 돌리면 같은 메모리 주소에 변수값이 저장이 되어 같은 값만을 배출하게 된다
  • 반면 [0 for i in range(n)]으로 [0]을 생성하게 되면 랜덤 메모리 주소에 저장이 되기 때문에 각각 다른 변수 값을 저장하게 된다

사진이 좀 크지만,,,
잊고살았던 단위행렬

.
.

* 시간초과

행렬제곱을 다 풀고 마지막에 시간초과가 났다.


# 지수를 나누면서 부분연산을 진행하는 재귀함수
def multi(b):
    if b == 1:
        return numbers
    
    # b가 짝수면 제곱
    if b % 2 == 0:
        # return mul_matrix(multi(b // 2), multi(b // 2)) #시간초과 이유
        val = multi(b // 2) 
        return mul_matrix(val, val)
    
    # b가 홀수면 지수-1 하고 입력받은 행렬 한번 곱해주기 (A^3 = A^2 * A)
    else:
        return mul_matrix(multi(b - 1), numbers)

문제가 됐던 해당 코드 부분인데, b를 나눠주며 크기를 줄이는 과정에서
return mul_matrix(multi(b // 2), multi(b // 2)) 부분이 문제였다(사진참고)


그래서
val = multi(b // 2)
return mul_matrix(val, val)
으로 b//2값은 따로 val에 저장해서 그 값을 불러오는 식으로 시간문제를 해결했다

도와준 원종/종호오빠 매우 감사감사


미완성 코드

1655 가운데를 말해요 (우선순위 큐)

힙 구조에 대해 이야기한 메모

힙을 leftheap, rightheap 2개로 나눠서 해결하는 풀이가 있었다.


6549 히스토그램에서 가장 큰 직사각형 (분할정복)

최소 높이인 1을 기준으로 자르고,
그 다음 또 높이가 다른 곳을 기준으로 반 자르고... 이렇게 반복하다가
핵심은 3, 4번째의 직사각형 크기를 어떻게 계산해낼지 찾는게 핵심이었던 문제이다.


추가메모

  • 리턴값 2개 받는 법도 찾아봐야겠다.

2021.11.16

오늘의 이야기

문제를 어떻게 풀지 구상을 다 하고, 정답이 그런 풀이과정이 맞았음에도 불구하고 왜 코드로 구현하는게 어려울까 생각해본 결과 내가 프로그래밍 언어에 있어서 기초적인 문법에 공백이 있어서라는 것을 알게되었다.
기본 문법 공백을 채우고나면 훨씬 코드구현에 익숙해질 수 있을 것 같다.
내일은 오늘보다 두 번 더 앉아 버티는 것을 목표로 공부해야지.

'SW Jungle [예림] > Algorithm' 카테고리의 다른 글

[WEEK02] DAY18 & TMI  (0) 2022.10.10
[WEEK02] DAY17 & TMI  (0) 2022.10.10
[WEEK02] DAY15 & 피보나치수열, 파라메트릭서치, DP(동적프로그래밍)  (0) 2022.10.07
[WEEK02] DAY13  (1) 2022.10.07
[WEEK02] DAY12 & TMI  (0) 2022.10.06

댓글