2024년 4월 26일 알고리즘 문제풀이 문제 기능개발 난이도 Lv. 2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def solution(progresses, speeds): answer = [] idx = 0 while idx < len(progresses): cnt = 0 for i in range(len(progresses)): progresses[i] += speeds[i] while idx < len(progresses): if progresses[idx] >= 100: idx += 1 cnt += 1 else: break if cnt: answer.append(cnt) return answer 가장 앞에 있는 기능이 100이 될때까지 모든 값들의 크기를 늘렸다. 이후 첫번 째 기능 개발이 완료되었을 때 100이 넘는 것들을 같이 처리해주고 갯수를 세주었다. ...
2024년 4월 23일 알고리즘 문제풀이 문제 주식가격 난이도 Lv. 2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def solution(prices): answer = [0 for _ in range(len(prices))] stk = [] for i in range(len(prices)): price = prices[i] if not stk: stk.append([price,i]) continue while stk: now_price, now_time = stk[-1] if price < now_price: answer[now_time] = (i-now_time) stk.pop() else: break stk.append([price,i]) if stk: while stk: p,t = stk.pop() answer[t] = len(prices)-1-t return answer
2024년 3월 18일 알고리즘 문제풀이 문제 다리를 지나는 트럭 난이도 Lv.2 코드 1차 42.9점 / 100점 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 from collections import deque def solution(bridge_length, weight, truck_weights): answer = 0 # 다리를 표현하기 위한 덱 in_bridge = deque() # 다리의 길이와 트럭의 위치를 표현하기 위해 트럭이 없는 곳은 0인 원소로 채운다. for _ in range(bridge_length): in_bridge.append(0) for truck in truck_weights: # 현재 다리에 지금 주목하는 트럭이 올라가면 무게 제한을 초과할 경우 # 가장 끝에 있는 원소를 빼낸다. 트럭일 수도, 빈 값(0)일 수도 있다. # 0번 인덱스가 빠지고 하나가 추가되기 때문에 모든 원소들의 index는 1씩 줄어든다. # 따라서 다리 위의 모든 트럭이 1칸 움직이는 것을 의미한다. while sum(in_bridge)+truck > weight: outgoing_truck = in_bridge.popleft() in_bridge.append(0) answer += 1 # 만약 실제로 트럭이 빠졌다면, 이와 동시에 새로운 트럭이 올라올 수 있다. # 새로운 트럭이 올라오는 행위는 동시에 일어나므로 시간이 흐르지 않은것으로 치기 위해 뺸다. if outgoing_truck: answer -= 1 # 다리에 새로운 트럭이 올라올 수 있다면 올려준다. if sum(in_bridge)+truck <= weight: # 잘못된 부분: 위에서 동시에 올라온다고 해놓고 여기서 또 하나의 트럭을 빼주었다. 여기서 오답이 발생 in_bridge.popleft() in_bridge.append(truck) answer += 1 # 모든 트럭을 다리 위에 올렸더라도, 도착까지 계산해야 한다. # 가장 도착지에서 먼 트럭이 도착지까지 걸리는 시간을 더해준다. for i in range(len(in_bridge)-1,-1,-1): if in_bridge[i]: answer += (i+1) break return answer 덱을 이용해야겠다는 생각은 보자마자 들었다. 배열에서 한 쪽으론 트럭을 빼내야 하고 한 쪽으론 집어 넣어야 해서 입구와 출구가 정해져있는 덱이 유리하겠다고 생각했다. 덱의 길이를 항상 bridge_length 만큼으로 유지하기 위해 항상 빈 곳은 0의 값을 채워 넣어 주었다. 다리의 길이가 1이 아니기 때문에, 다리 위에서 트럭이 움직일 떄도 시간이 흐르기 때문이다. 시간이 흐를 때마다 0번 index 값을 빼주고(popleft), 맨 뒤에 새로운 값을 삽입하면(append) 다리 위에 있는 모든 트럭의 index는 1씩 감소하게 된다. 따라서 1칸 씩 전진한 셈이 된다. 현재 트럭의 위치를 index로 설정하기 위해선 트럭이 있지 않은 공간을 0으로 설정하는 것은 내가 생각해도 잘한 것 같다. 특히나, 이렇게 하면 다리 길이보다 더 많은 트럭이 올라올 일은 걱정하지 않아도 된다. ...
2024년 2월 26일 알고리즘 문제풀이 문제 크레인 인형뽑기 게임 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 def solution(board, moves): n = len(board) stk = [] answer = 0 # 열에서 가장 위에 있는 인형을 찾는 함수 # 찾으면 board에서 0으로 바꾸고 반환 def first_target(row): for i in range(n): if board[i][row]: result = board[i][row] board[i][row] = 0 break else: result = False return result # 인형이 있을 때, 이미 들어있는 인형과 동일하면 2개 제거, 아니면 추가 for x in moves: row = x-1 tmp = first_target(row) if tmp: if stk: if stk[-1] == tmp: stk.pop() answer += 2 continue stk.append(tmp) return answer
2024년 2월 23일 알고리즘 문제풀이 문제 짝지어 제거하기 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def solution(s): arr = list(s) stk = [] for i in range(len(s)): if not stk: stk.append(arr[i]) continue else: if stk[-1] == arr[i]: stk.pop() else: stk.append(arr[i]) if not stk: answer = 1 else: answer = 0 return answer
2024년 1월 12일 알고리즘 문제풀이 문제 햄버거 만들기 난이도 Lv. 1 코드 배열을 순회하면서 순서대로 필요한 재료가 나오면 만들 수 있는 갯수를 하나 추가해주고, 해당 재료들을 제거해주었다. 이 방법은 틀렸는데, 재료가 연속해서 나와야 하기 떄문이다. 연속이라고 써놓지 좀… 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def solution(ingredient): answer = 0 arr = [1,2,3,1] while True: idx = 0 for x in range(len(ingredient)): if idx ==4: answer += 1 break if ingredient[x] == arr[idx]: idx += 1 ingredient[x] = 10 else: if idx == 4: answer += 1 else: return answer 그래서 하나씩 배열로 옮기면서, 최근 옮긴 4개로 햄버거를 만들 수 있다면 만들고 제거하도록 로직을 바꾸었다. ...
2023년 7월 30일 알고리즘 문제풀이 백준 5904번 문제 링크 1차 시도 나의 생각 재귀 함수를 통해 각 문자열을 구할 수 있었다. 또한 그 문자열의 길이도 규칙적이므로 몇번째 재귀에서 n번째 문자열이 등장하는지를 알아내어 그 문자열의 index를 통해 구하였다. 하지만 메모리 초과와 시간 초과로 인하여 오답처리 되었다. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys sys.setrecursionlimit(10**6) n = int(sys.stdin.readline()) def moo(k): if k == 0: return 'moo' return moo(k-1)+'m'+'o'*(k+2)+moo(k-1) i = -1 while True: i += 1 tmp = moo(i) if len(tmp) >= n: print(tmp[n-1]) break 2차 시도 나의 생각 문자열을 구하면 안된다고 생각하였다. 다음 문자열이 이전 차례의 문자열 두개에 하나의 규칙적인 문자가 껴있는 형태라는 사실에 집중하였다. 예를 들어 S(10)의 몇번째 문자열인지는 S(9)의 문자열을 통해 알 수 있다. 원리는 다음과 같다. ...
2023년 7월 26일 알고리즘 문제 풀이 백준 6549 문제 링크 시도1 나의 생각 왼쪽부터 반복문을 통해 조건에 따라 스택에 사각형의 넓이를 넣고 수정하는 방법을 사용하였다. 스택에는 사각형의 높이와 너비가 원소인 배열을 집어넣었다. 예를 들어, 이번 사각형의 높이가 4라면 [4,1]을 넣어주는 방법이다. 맨 처음을 위해 스택이 비어있을 땐 조건과 무관하게 스택에 삽입하였다. 이후는 최근 스택에 들어간 사각형의 높이(이전 사각형)와 현재 반복문에서 주목하는 사각형(현재 사각형)의 높이를 비교하였다. 만약 현재 사각형의 높이가 더 크거나 같다면, 스택에 들어 있는 사각형은 너비를 1 늘렸다. 이후는 현재 사각형과 더 이전에 들어갔던 사각형들의 높이를 비교하였다. 그래서 너비를 1 늘려주거나 만약 현재 사각형의 높이가 작으면 너비를 늘리지 않고 스택에 들어 있는 사각형의 높이와 너비를 곱하여 넓이를 구한 후 최댓값과 비교하여 저장하는 방법을 사용하였다. 로직을 정리해보자면 다음과 같다. 문제에서는 각 케이스별로 출력해야 하지만, 편의를 위해 하나의 케이스에서 발생하는 로직만 표시하였다. ...
1.개발 진행 및 완료상황 2주차 python algorithm 우선순위 큐 문제풀이중 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 priority queue 문제를 풀때 heapq를 사용해야 하는지, 기본적인 in-built함수로 구현할 줄 알아야 하는지 궁금했다. 코치님께 질문하였는데, 그 이유를 스스로 생각해보고 찾길 원하셨는지 여러가지 질문들을 하셨다. 시간복잡도, 자료구조, list, stack, queue등을 물어보셨는데 답변을 못하였다. 기초적인 개념들에 대한 이해가 부족하다는 것을 뼈저리게 느꼈다. 이와 관련된 공부들은 3번에 후술하였다. 새로 배운 내용 array 와list, tuple, dictionary, set의 개념과 차이 : ...
1.개발 진행 및 완료상황 2주차 파이썬 알고리즘 공부 스택 문제 1회독 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 문제 2493번을 파이썬으로 풀었다. 스택과 관련된 문제로 스택(파이썬에선 list지만)을 정방향으로 볼지(왼쪽부터), 반대방향으로 볼지(오른쪽)에 관련된 문제였다. 주목한 원소가 다음 원소와의 크기 비교를 통해 스택에서 pop을 할지 push를 할지 관련된 문제였는데, 경우에 따른 분류가 힘들었다. 위와 같이 정렬한 자료구조를 역순으로 바라보는 문제가 많았는데 정렬을 뒤바꾸는 것과 읽는 방향을 바꾸는 방법이 있었다. 때에 따라 사용하기 위해 둘 다 알아놓아야겠다. 밑의 첫번째는 오름차순 정렬, 두번째는 내림차순 정렬이다. list.sort() list.sort(reverse=True) ...