구현 유형

리트코드 2243: https://leetcode.com/contest/weekly-contest-289/problems/calculate-digit-sum-of-a-string/

그냥 구현 문제다. 2243_1 풀이 보셈. 더 숏코드인데 바보같다 왜 이생각을 못했을까..

 

 

- 리트코드 2245: https://leetcode.com/problems/maximum-trailing-zeros-in-a-cornered-path/solutions/1955607/python-explanation-with-pictures-prefix-sum/

구현. prefix-sum 이란 개념을 알고 써먹어야하며, 걍 어려움 사실 아직도 이해 못해서 강의도 듣고 그랬는데도 아직도 모름

시간 지나서 보니 훨씬 이해 잘됨

 

 

카카오 2020 문자열 압축: https://school.programmers.co.kr/learn/courses/30/lessons/60057

난이도 낮은 문제가 실제로 맞으나, 인덱싱 부분이 생각보다 굉장히 헷갈리는 면이 있어 처음엔 자꾸 예외 케이스 1개를 통과 못했음. 그러다 세월 지나서 다시 풀어보니까 풀리는군.

 

 

- 카카오 2020 기둥과 보: https://yjyoon-dev.github.io/kakao/2020/12/21/kakao-pillarfloor/

내 풀이 inbspect_b 함수에서 보 설치해도 되는지 검사하는 좌표는 전부 정답임. 그래서 이 부분에 대해 더 볼건 없는데, 인터넷에 나오는 풀이들이 훨씬 간단함 (젤 짧고 간단 풀이: https://velog.io/@tjdud0123/%EA%B8%B0%EB%91%A5%EA%B3%BC-%EB%B3%B4-%EC%84%A4%EC%B9%98-2020-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EA%B3%B5%EC%B1%84-python). 근데 워낙 어렵게 느껴지는 문제다보니 이를 이해하는 데도 한참 걸렸음. 나아중에 다시 풀어볼 문제.

그리고! 이렇게 명시적으로 시간 복잡도에 대한 말이 없는 문제의 경우 보통 5초라고 생각하고 풀면 된다고 함!

시간 제한이 1초인 문제에 대해 N의 범위에 따른 시간복잡도를 계산해보면

N의 범위가 500인 경우 : 시간복잡도가 O(N³)인 알고리즘 설계 가능
N의 범위가 2,000인 경우 : 시간복잡도가 O(N²)인 알고리즘 설계 가능
N의 범위가 100,000인 경우 : 시간복잡도가 O(NlogN)인 알고리즘 설계 가능
N의 범위가 10,000,000인 경우 : 시간복잡도가 O(N)인 알고리즘 설계 가능
출처: https://blackon29.tistory.com/65 [BlackSwon:티스토리]

 

15686: https://www.acmicpc.net/problem/15686

이코테에 수록된 문제. 두 번 다 손도 못대서 아예 풀이 본 문제. 왜 손도 못 댔느냐? 구현 유형인걸 눈치채지 못해서. dp, dbfs 같은 이론으로 풀리지 않을까 하는 생각을 먼저 하다 보니 ... 그치만 주어진 조건으로 시간 복잡도를 따져 보면 구현이라는 답이 나온다. 그리고 나 뿐 아니라 다른 사람들도 같은 이유로 시간 초과를 한번 겪고 온 경우가 많았다.

걍 독해력 문제임 이 문제는. 2번째엔... 사실 풀이를 외웠기 때문에(문제만 이해하면 쉬운 문제라...?) 풀기 수월했다

 

발상을 설명한 글은 이게 가장 괜찮았다: https://crowdreport-defender.tistory.com/13

- 문맥 중 하나: 치킨 거리가 작을수록 가까운 거리에 치킨집이 있으니 수익이 많이 난다고 판단하는 것.

 

- 문제에서 이해 안됐던 것: "최대" M개를 고른다 => M개 이하로 골라도 된다 => 근데 이건 왜 안되고 다들 M개를 고르는 풀이로 푸는 걸까?

 

- 이유: M개 = 최소 치킨집 개수니까

 

카카오 2024 1번: https://school.programmers.co.kr/learn/courses/30/lessons/258712

조건 검사하고 answer 계산하는 파트 봐라 나랑 너무 차이 난다 내가 어쩌다 이렇게 됐는지 원... 수능 독해력 같은 문제다. 기업 기출 장점이 이런 류의 문제가 많다는 거..

 

- 카카오 2024 2번: https://school.programmers.co.kr/learn/courses/30/lessons/258711

진짜 하안참 생각하고, 블로그에 생각 과정도 적어둠: https://thewayaboutme.tistory.com/737

생각할 만큼 해보니까, 이쯤에서 로직 점검을 받는 게 좋겠더라고 그래서 카카오 공식 블로그 풀이에서 로직 확인하니 역시.. 타이밍이 좋았다. 많이 배웠다. 분명 어렵게 풀면 안되리라 생각했는데, 상상 이상이었다. 이건 그래프 탐색 문제 조차 아닌, 그 탈을 쓴 "구현" 문제다!

게다가 초특급 숏코드 가능. 현재 내 코드보다 더 짧은 코드 아무데도 없고, 인접 그래프 아니고 인접 행렬을 쓰되 다프 유형 C++로 풀 때처럼 배열 원소로 2차원, 3차원 배열 갖고 값 저장하는 방식 쓰는... : https://velog.io/@yssgood/%EB%8F%84%EB%84%9B%EA%B3%BC-%EB%A7%89%EB%8C%80-%EA%B7%B8%EB%9E%98%ED%94%84

위 코드도 짧고 발상도 좋은 풀이라 생각함. 시간 복잡도는 아마.. 위 풀이가 더 짧을걸 탐색 한 번에 다 끝내니까? 나는 집합 관련 메서드를 써서 그렇지, 이게 숏코드 아니라고 생각하면 시간복잡도 상수로 2~3배 될 거임

 

그 외 로직 자꾸 틀렸었던 포인트는 내 풀이에 주석으로 적어뒀고, 여기 적을 만한 건 특히 발목 잡았던 filter...

아래 코드를 봐. 겉보기에 아무 차이 없을 것 같은 이 코드가, 서로 다른 결과물을 내놓는다니까?

eight = [filter(lambda a: len(intro[a]) == 2 == len(outro[a]), union)]
eight = list(filter(lambda a: len(len(intro[a]) == 2 == len(outro[a]), union))

 

 

위아래 프린트 결과물 비교:

 

 

당연히 len 계산하면 위는 1,1. 아래는 0,2 나오겠지? 이것땜에 한참을 헤맸다...

타입 변환을 명시적으로 두번째 줄처럼 해줘야 하나봄.

근데 근본적으로 왜 이런 것인가? 에 대한 게 난 궁금한데.. 그걸 알려면 결국 관련 자료를 못찾는 이상은, 더 근본적으로 이해하려면 씨파이썬을 이해해야 할지도~? 아 참 그리고 필터 같은거 쓰는거 별로 안좋대. 파이써닉 웨이는 list comprehension 사용하는 거라고 함! 그래서 이거로 바꿔 사용했고, 이에 대한 자료는 https://www.daleseo.com/python-filter/

 

 

 

카카오 2023 1번 https://school.programmers.co.kr/learn/courses/30/lessons/150370

전형적인 구현 연습하려고 푼건데 풀수록 내 폼이 너무 죽어서 슬플 뿐 ㅠㅠㅠㅠ