(시작기록)
> 23년 1월 25일 까지 기록
코드업 Python 기초 100제 (완)
프로그래머스 : 문제해결 19 (LEVEL 2 위주)
백준 solved : 브론즈 2 (브론즈 9, 실버 9)
최종목표 : 카카오 코테 풀 수 있을정도 실력 유지
계획 : 하루 2문
1. 프로그래머스 level 1, level 2 완독
2. 프로그래머스 좋은 코딩 모방, 공부
3. 백준 골드 완독 이후 플레 문제 시도
(중간기록)
> 23년 2월 23일 기록
프로그래머스
점수 : 1,260점
해결한 문제 : 35개
1. 프로그래머스 level 2문제는 다 풀어봤다.
2. level 3 문제를 다루고 있으나, 대부분 히든 테케 일부에서 막히는 느낌이 든다. 시간도 굉장히 많이 들고.
3. 푼 문항수, 점수가 상대적으로 굉장히 낮다고 생각한다.
알고리즘 문제를 풀수있는 실력을 우선으로 두어 점수랑 푼 문항수에 크게 집중하지 않았는데 알고보니까 프로그래머스 점수 기준으로 뽑는곳도 있더라. 이걸 무지성으로 채워나가야 하나?
사실 처음부터 욕심을 좀 내서 level2 부터 시작했는데, 초반에 알고리즘에 무지한 채 for문으로 억지로 풀어봤던 문제들, 점수 까먹어 가면서 다른 사람 답지를 봐야했던 것들 때문에 점수가 많이 깎였고, 내가 원하는 수준이 level2 - level 3문제들까지 어느정도 풀 수 있는 능력이였기에, 쉬운 문제를 풀기보다는 어려운 문제를 두번 세번 풀어봤던것 같다.
앞으로 어떤 방향으로 채워나가야 할까?
억지로, 지저분하게, 또는 질문하기 등의 남의 코드를 참고하여 문제를 해결했던 것들 다시 풀어보는게 나을까 아니면 쉬운 문제들을 차근차근 풀어보면서 숏코딩, 깔끔한 코딩 위주로 더 연습하는게 나을까. 아니면 그냥 다른거?
globals => 전역변수 (def 안에서 정의하더라도 밖에서 쓸 수 있는 변수)
def main() -> None : 이때 -> None 의 역할은 주석으로 return값이 없음을 의미, 실제로 return값을 넣더라도 에러는 없음
> 1월 25일
level1 - 크기가 작은 부분문자열 (2번 제출 실패, 실패)
- 시간복잡도가 크지 않음에도 시간복잡도 고려.
- 2중 for 문 반복시 반복순서를 제대로 고려하지 못했음, 인덱스 길이 실수
- 2중 for문 보다 슬라이싱이 더 빠른가? for문과 조건문 조합 -> 조건문에서 O(1) 로 조회 여러번 반복 * 최대 경우 슬라이싱 길이만큼 // 슬라이싱 -> 슬라이싱 길이만큼 시간복잡도 고정 O(k) -> 슬라이싱이 더 빠르다.
level2 - 점찍기 (2번 제출 실패, 시간초과)
- 시간복잡도를 이번엔 너무 고려하지 않음. 반복문을 끊는 것으로 해결 X
- 부동소수점을 고려하여 sqrt 나 **0.5 를 쓰면 안되는 줄 알았다. 그러나, 실수 + 실수 == 실수 인 경우 즉 0.1 + 0.2 == 0.3 (False) 인 경우 소숫점 부분의 근사처리 때문에 조심해야하는 거지 소숫점값과 실숫값 과의 비교에선 애초에 고려할 필요가 없었다.
> 1월 27일
level1 - 가장 가까운 글자 (테케 한번 실수)
level2 - 시소 짝궁 (접근법 확인)
- 시간복잡도를 짧게 할 방법을 고민하도록 하는 문제
- 문제를 자세히 읽고 경우의수를 줄여야 접근이 가능했음
- dict 에서 key 값에0 없는 key의 value를 호출한 경우 에러가 나지만 Counter 로 만들어진 dict에서는 0값을 뱉는다.
> 1월 30일
level2 - 유사 칸토어 배열 (매우 오래걸림, 히든테케 틀려가면서 맞춤)
- 대체로 이와 관련된 문제들에서 확실히 약하다고 느낌. 규칙성. 구현. 시간복잡도 내에서 해결
- 코딩을 스스로 짰음에도 코딩에 대한 이해가 떨어진다는 느낌. 주석을 많이 달아보자.
- 생각해 놓은 풀이법을 설명할 수가 없음. 명확화 단순화 하는 작업을 많이 해봐야될듯
> 1월 31일
level2 - 무인도 여행
- 델타함수를 통한 그래프탐색 알고리즘 코드 정리필요(델타함수, 재귀함수를 이용, 주어진 범위를 벗어나지 않도록 조건 필요)
- 방문지역을 곂치지 않게 어떻게 처리할 것인가
| ① visit을 tuple로 받아서 계속 꺼내보며 비교 -> 사용해 봤는데 오래걸림, stack이나 queue를 통해 visit를 비워가면서 재귀함수가 모든 경우의수(모든 좌표에서 상하좌우) 돌지 않도록 하는것이 좋아보임. |
| ② maps와 동일한 크기의 0으로 채워진 visit 행렬을 만들고 방문시 1로 변경 -> 단순 인덱스 조회다 보니 속도가 아무래도 빠를 것 |
| ③ maps을 직접 수정, 방문한 지역의 정보를 사용한 후 그 지역의 값을 더이상 방문할 수 없는 값으로 대체 -> 원본 maps를 수정하는 방법이므로 visit 을 짤 필요가 없다. 조회를 두번씩 하지 않으므로 제일 빠른방법 |
level2 - 뒤에있는 큰 수 찾기(못 푼 문제, 접근법을 기억하자)
- 단순하게 접근하면 시간복잡도 문제가 생기는, 내가 어려워 하는 유형. 실제로 풀었으나 시간초과
- value값 비교와 index 를 동시에 고려하고, 원본을 건드리지 않으면서 원본을 계속 참고하며 answer 업데이트 시켜야함. 한번 업데이트 된 값은 더이상 answer을 건드릴 필요가 없으나, 그렇다고 원본에서 바로 삭제해서도 안됨.(삭제하면 다른 위치의 값들은 index 도 바뀌고, 빼도 조건을 만족하는지 알수가 없음)
- 리스트 원본을 따로 저장해두고 똑같은 사본을 건드리고 싶을때는 deep copy를 이용해야 하고, 이를 copy 라이브러리 copy.deepcopy 를 사용해도 되나 list, dict 인자에 .copy() 메서드를 통해 동일한 기능을 지원하고 있음.
- 2번을 해결을 위해 분명 하나의 코드로 동시에 고려할 수 있다고 생각했으나, 구현자체를 하지 못했음.
- 발상 자체가 어려웠던 문제. 우선순위 큐를 이용한 문제.
from heapq import *
def solution(numbers):
n = len(numbers)
answer = [-1] * n
h = []
for i in range(n):
value = numbers[i]
# heap에 남은 최솟값이 지금들어온 값(이 값이 큰 값이면 가장 가까운 큰값(조건)) 이면 업데이트.
# 이는 지금까지 힙으로 쌓아왔던 모든 heap에 대해 작은순으로 전부 비교하고 조건만족하면 빼버림.
while h and h[0][0] < value: # 조건문 앞에 걸리면 뒤에 체크 안함, ex h 가 empty라서 h[0][0] 를 조회할 수 없음에도 앞 조건에서 이미 틀리기 때문에 에러를 뱉지 않음
_, idx = heappop(h)
answer[idx] = value
heappush(h, [value, i]) # 다음 값이 이전값보다 크지 않으면 계속 min heap에 쌓아버림
# 가장 먼저 나오는 (순서대로 들어오니까) 본인보다 큰 값에 대해 업데이트 되기 위해
# heap을 통해 작은값부터 차례차레 넣어둠
return answer
(유사문제) level2 - 주식가격
- input 길이가 10만개로, 2중 for 문으로도 충분히 가능해 보임(모든 원소 대조해보며 값이 줄었는지 확인) -> 최대 시간복잡도 50억
- <뒤에있는 큰수 찾기> 문제와 동일하게, 새로운 값이 들어왔을때 가장 큰값부터, 새로운값으로부터 값이 떨어졌는지 비교가능함. 즉 -value 로 heap 구성해서 max heap으로 구성가능.
level2 - 숫자 변환하기 (정답률 64%, 기존 풀이의 한계)
- 솔직하게..bfs dfs 문제인지 전혀 몰랐음 (경우의 수를 그림으로 그려봤으면 더 좋았을듯)
- 원래 발상에서의 한계를 파악할 필요가 있을듯, 더이상 단순히 모든 경우의 수 따지는건 한계가 있음, 조금 더 효율적인 방법. 경우의 수를 줄일수 있는 더 확실한 방법들을 찾아보자.
- 유사문제 : 백준 숨바꼭질 (풀어보기)
# 틀림. 확실히. y = x*2^x2*3^x3 + n*2^l*3^m , l <= x2 , m <= x3
# 수식을 확실히 정해놓고 경우의 수 최대한 줄여서 돌리려고 했으나, 그렇게 하면 조합까지 고려해야되고 코드가 복잡해짐
# 수식 경우의 수를 줄여야 하므로 더 좋은 방법을 찾아야함. (시간은 충분했으나 예외경우가 너무 복잡)
# 질문하기 코드 참조
# 스택, 큐 둘다 가능 즉 dfs, bfs 둘다 가능하나
# 큐 -> answer = a 라면 모든 경우의 수룰 a개씩 총 sigma_k (a^k) 개 연산
# 스택 -> 최솟값 찾을때 까지 모든연산 다 해보고 최솟값 answer = a 찾으면 그때부터 a개씩 계산
# x를 기준으로 y를 만드는것보다, y를 기준으로 x를 만드는게 더 효율적임
from collections import deque
def solution(x,y,n) :
outcome = deque([])
outcome.append([y,0])
checker = False
while not checker and len(outcome) != 0 :
# 최솟값을 찾았거나(x로 y를 만들었거나)(체커), 모든 경우의 수에서 다 불가능한 경우
y_conv , count = outcome.popleft()
if x == y_conv :
checker = True
break
if y_conv % 2 == 0 :
y_2 = y_conv / 2
if y_2 >= x :
outcome.append([y_2,count + 1])
if y_conv % 3 == 0 :
y_3 = y_conv / 3
if y_3 >= x :
outcome.append([y_3,count + 1])
y_n = y_conv - n
if y_n >= x :
outcome.append([y_n,count + 1])
return count if checker else -1
> 2월 9일
level 2 - 호텔대실
- 두 개의 힙을 두고 하나는 입실이 가장 빠른 순, 하나는 퇴실이 가장 빠른 순으로 두어 새로운 입실 시간이 주어질 때 퇴실했을 사람의 방을 빼고 총 방의 개수를 구하도록 함.
- 총 방의 값을 변수로 두고 시간대별로 입실을 +1 퇴실을 -1 로 두어 계산 ( O(n) 으로 속도 제일 빠름)
level 3 - 인사고과 (시간초과, 해결못함)
- 사원들끼리 비교(한 사람의 점수 두개가 다른 사람의 점수 두개보다 둘 다 낮은경우 순위 제외)에서 시간을 줄여야 할 것 같은데, 어떻게 줄일 것인가? - 나와 비슷한 방법으로 푼 사람들이 많은것같은데 그 사람들은 왜 시간초과가 안나는가
- 누적합으로 어떻게 구한거지?
> 2월 10일
level 3 - 표현 가능한 이진트리(kakao)
- 코테에 대한 자신감이 너무 떨어진다.(내가 못푸는 문제라고 생각하는 경향) 아마 알고리즘 공부가 덜된 채로 너무 어려운 문제들만 풀어와서 그런듯 하다. 충분히 풀어낼 수 있는 문제였음에도 너무 오래 끌렸다
- 이진트리에 대한 개념, 완전 이진트리, 포화 이진 트리 등의 개념을 잘 적립할 필요가 있겠다.
- "이진트리에서 리프 노드가 아닌 노드는 자신의 왼쪽 자식이 루트인 서브트리의 노드들보다 오른쪽에 있으며, 자신의 오른쪽 자식이 루트인 서브트리의 노드들보다 왼쪽에 있다고 가정합니다." 여기서 용어정리가 안되어 있다 보니 무슨의미인지 알아내는데 너무 힘들었다.
> 2월 11일
level 3 - 표 병합(kakao) (풀이 실패, 에러)
- 애초에 내가 어려워하는 유형. 자료구조를 짜는 문제방식에 대해 너무 많은 부담감이 들고 어려움. (네부캠 코테의 머리를 공유하는 큐를 짜는 문제에서도 손도 못댐)
- 풀이 방식에서 매우 배울점이 많은 문제라고 생각함.
> 2월 14일
level 3 - 표 병합 (재시도) (에러)
-> 왜 에러가 나는지 알 수가 없음, 원소 2개인 튜플(r_,c_)을 내뱉는 함수의 함숫값을 변수 두개로 받았는데 에러가 남
level 3 - 미로 탈출 명령어
- 풀이방식을 떠올리는데 오래걸렸던 문제, 이제는 기존에 사용했던 알고리즘을 자연스럽게 쓸 수 있도록 하는 게 필요할듯
- 그래프 알고리즘 다시 살펴보기.
- 문제에서 주어진 내용 파악 보다 철저히 하기
> 2월 17일
level3 - 억억단을 외자
- 초기에 실수가 나는부분 (테케 돌려보고 실수를 아는부분) 을 어떻게 고칠 수 있을까?
- 시간단축에 대한 고민이 항상 필요할 듯 하다.
> 2월 18-20일
level3 - 숫자 타자대회
level3 - 등대
사실 많이 어려운 문제같다, 특히 나에게 level3은 아직 풀기는 어려운 영역이라고 생각한다. 실제로 이 문제들을 푸는데 족히 하루씩은 넘게 고민하고 코드들을 보고 배우는것만 해도 머리가 너무 아팠다.
그러나 코드를 보면서 배우는 점도 많고, 안다고 생각했던 알고리즘들을 실제로 활용하는 과정에서 내가 제대로 알지 못해 실수도 많이 나온다는걸 깨달았다. level3 를 풀어보려는 과정에서 이런 부분들을 더 세심하게 살필 수 있었고, 무엇보다 어렵고 꺼려지는 문제들을 한번 부딛혀 보면서 문제에 대한 적응을 해나가고 있는 중이라 생각힌다.
> 2월 22-23일
기존까지 풀었던 level 2, level 3 문항 재풀이
'알고리즘 > 코딩테스트 준비' 카테고리의 다른 글
| 다익스트라 알고리즘 활용 문제 (프로그래머스 level 4 - 미로찾기) (0) | 2023.03.07 |
|---|