Python

2023년 8월 3일 알고리즘 문제풀이 백준 1991 문제 링크 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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 import sys arr = [] n = int(sys.stdin.readline()) for _ in range(n): p, l, r = sys.stdin.readline().rstrip().split() arr.append([p, l, r]) front = ['A'] mid = [] back = [] def search_front(node, arr, ans): for x in arr: if x[0] == node[0]: if x[1] != '.': ans.append(x[1]) search_front(x, arr, ans) if x[2] != '.': ans.append(x[2]) search_front(x, arr, ans) def search_mid(node, arr, ans): for x in arr: if x[0] == node[0]: if x[1] != '.': search_mid(x, arr, ans) else: ans.append(x[0]) if x[2] != '.': search_mid(x, arr, ans) break def search_back(node, arr, ans): for x in arr: if x[0] == node[0]: if x[1] != '.': search_back(x, arr, ans) else: ans.append(node) if x[2] != '.': search_back(x, arr, ans) ans.append(x) ans.append(node[0]) search_front(arr[0], arr, front) search_mid(arr[0], arr, mid) search_back(arr[0], arr, back) print(front) print(mid) print(back) 2차 시도 나의 생각 정답을 위한 배열에는 항상 부모만 넣는다는 기준을 세웠다. 또 왼쪽자식과 오른쪽 자식의 탐색을 if-else 조건문을 사용하였는데 별개로 하였다. 즉 왼쪽 자식을 먼저 탐색해 존재하면 재귀를 통해 최대한 깊숙히 들어간 후 더이상 왼쪽자식이 존재하지 않을 때 그 때의 부모노드를 배열에 추가하면 전체 트리에서 가장 왼쪽에 있는 노드를 배열에 추가한 것으로 구현된다는 것을 깨달았다. 순회의 방식에 따라 왼쪽 자식 탐색, 부모노드 삽입, 오른쪽 자식 탐색의 순서만 변경해주었다. ...

2023년 8월 2일 알고리즘 문제풀이 백준 11000 문제 링크 1차 시도 나의 생각 각 수업을 시작하는 시간을 기준으로 정렬하되, 끝나는 시간을 heap에 넣는다. 반복문으로 순회하며 지금 시작할 수업의 시간이 배열에 들어있는 수업 중 끝나는 시간이 가장 빠른 수업의 종료 시간과 비교하였다. 종료 한 후 시작되면 추가적인 강의실이 필요 없다. 하지만 수업이 끝나지 않은 채 다음 수업이 시작된다면 새로운 강의실이 필요하다. 결과 정답 코드 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 import sys from heapq import heappush, heappop, heappushpop n = int(sys.stdin.readline()) classes = [] for _ in range(n): s,t = map(int,sys.stdin.readline().split()) classes.append([s,t]) classes.sort() heap = [] cnt = 1 for i in range(n): now_class = classes[i] if not heap: heappush(heap,now_class[1]) else: while heap: end_time = heap[0] if now_class[0] >= end_time: heappop(heap) else: break heappush(heap,now_class[1]) cnt = max(cnt,len(heap)) print(cnt)

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월 29일 알고리즘 문제풀이 백준 13334번 문제 링크 1차 시도 나의 생각 사람들의 사무실 과 집 둘 중 좌표가 작은 것을 먼저 오게 한 후, 그것을 오름차순으로 배열에 정리하였다. 각 지점을 철로의 시작점으로 삼아 모든 case를 검사하며 최댓값을 업데이트했다. 다 검사해버리니 당연히 시간초과… 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import sys from heapq import heappop, heappush n = int(sys.stdin.readline()) people = [] for _ in range(n): h,o = map(int,sys.stdin.readline().split()) if h <= o: heappush(people,[h,o]) else: heappush(people,[o,h]) d = int(sys.stdin.readline()) ans = 0 while people: cnt = 0 x = people[0][0] for person in people: if person[0] >= x and person[1] <= x+d: cnt += 1 ans = max(ans,cnt) heappop(people) print(ans) 2차 시도 나의 생각 어떤 사람의 집과 사무실의 거리는 철로의 길이인 d보다 멀 수도있다. 이 사람은 철로를 어디에 설정하든 이용할 수 없다. 따라서 입력을 받을 때 이런 케이스를 지우려고 했다. 또한 정렬을 해버린 만큼 굳이 필요하지 않은 조건들도 제거하였다. 하지만 예외케이스가 있는지 오답처리되었다. ...

2023년 7월 28일 알고리즘 문제풀이 백준 1655번 문제 링크 1차 시도 나의 생각 양 끝과 중간이라는 생각에 deque을 사용하면 어떨까 생각하고 코드를 작성했다. 생각해보니 중간과 끝 사이에 새로운 숫자를 집어넣어야 하는데… 다행히 우선순위 큐, 최소 heap이 생각났지만 너무 늦게 생각나서 코드 작성을 못했다. 다음 시도에선 해봐야지. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import sys from heapq import heappop, heappush, heappushpop n = int(sys.stdin.readline()) big = [] mid = [] small = [] for _ in range(n): num = int(sys.stdin.readline()) if not mid: mid.append(num) print(num) continue if num >= mid: tmp = heappushpop(big,num) mid.append(tmp) print(mid[0]) else: tmp = heappushpop(small,-num) mid.append(-tmp) mid.sort() print(mid[0]) 2차 시도 나의 생각 heap을 사용하였다. 가운데 값을 기준으로 크냐 작냐에 따라 경우가 나눠질거라고 생각해서 가운뎃값보다 작은 heap, 가운뎃값을 담은 heap, 더 큰 heap 세개로 나누어서 생각했다. 하지만 문제에서 나왔듯 가운데 값이 전체 숫자의 갯수에 따라 2개일 수도 한 개 일수도 있어서 가운데를 담는 배열을 1로 유지해야할지, 혹은 큰 배열과 작은 배열의 수를 갖게 유지해야할 지 여러모로 헷갈렸다. 차라리 하나를 우직하게 했으면 정답은 나왔으려나.. 여러 생각에 헤메다가 시간만 허비하고 코드를 완성하지 못했다. ...

2023년 7월 28일 알고리즘 문제풀 백준 11866번 문제 링크 1차 시도 나의 생각 처음엔 인덱스를 옮겨가면서 없어진 수를 표시하는 방법을 생각했다. 예를 들어 [[1,0].[2,0],[3,0],[4,0].[5,0]] 이런 식을 설정하고 빠지는 원소는 2번째 원소를 1로 바꿔주는 방법. 하지만 굳이 배열을 한번 더 복잡하게 만들어야 할 필요성이 없다고 생각했다. 따라서 덱으로 설정한 배열의 가장 앞 원소만 주목하되, 현재 뺄 차례인지 그냥 넘어갈 차례인지만 분류하면 되겠다고 판단하였다. 뺄 차례라면 popleft 한 후 따로 만들어둔 정답을 위한 배열에 append 하였다. 로직 자체는 어려움이 없었으나 예제에서 출력할 때 수열을 담는 괄호가 대괄호가 아니라 그냥 괄호 ‘<>‘였다. 이 부분이 신경쓰였지만 가장 먼저 ‘<‘를 배열의 앞에 넣어주고, 수열을 넣을 때 마다 숫자를 str로 바꾼 후 따옴표(,)와 공백( )을 붙여서 넣었다. 그 이후 *를 이용해 원소들만 출력했다. ...

2023년 7월 26일 알고리즘 문제 풀이 백준 6549 문제 링크 시도1 나의 생각 왼쪽부터 반복문을 통해 조건에 따라 스택에 사각형의 넓이를 넣고 수정하는 방법을 사용하였다. 스택에는 사각형의 높이와 너비가 원소인 배열을 집어넣었다. 예를 들어, 이번 사각형의 높이가 4라면 [4,1]을 넣어주는 방법이다. 맨 처음을 위해 스택이 비어있을 땐 조건과 무관하게 스택에 삽입하였다. 이후는 최근 스택에 들어간 사각형의 높이(이전 사각형)와 현재 반복문에서 주목하는 사각형(현재 사각형)의 높이를 비교하였다. 만약 현재 사각형의 높이가 더 크거나 같다면, 스택에 들어 있는 사각형은 너비를 1 늘렸다. 이후는 현재 사각형과 더 이전에 들어갔던 사각형들의 높이를 비교하였다. 그래서 너비를 1 늘려주거나 만약 현재 사각형의 높이가 작으면 너비를 늘리지 않고 스택에 들어 있는 사각형의 높이와 너비를 곱하여 넓이를 구한 후 최댓값과 비교하여 저장하는 방법을 사용하였다. 로직을 정리해보자면 다음과 같다. 문제에서는 각 케이스별로 출력해야 하지만, 편의를 위해 하나의 케이스에서 발생하는 로직만 표시하였다. ...

날짜 2023년 7월 12일 계획 알고리즘 3문제 공부하기 C 프로그래밍 Red-Black Tree 복습하기 애들코딩 프로젝트 보안하기 코드잇 배포하기 결과 스택과 관련된 알고리즘 3문제를 공부하고 이해하였음 Red-Black tree의 정의에 대하여 정리하였음 애들코딩 프로젝트는 우선 코드잇 배포를 위해 연기하였음 코드잇 배포는 배포 과정이 처음이라 공부하면서 진행중인 상태 Today I Learned 알고리즘 백준 2493번(링크) 문제 해석과 풀이 방식(X) 우선 타워의 번호와 index를 헷갈려선 안된다. 타워 번호는 1번부터 5번까지지만 리스트에 담을 때 index는 0부터 4이다. ...

개발 진행 및 완료 상황 3주차 python algorithm 난이도 중 이하 문제 풀이 완료 CSAPP 3.3 까지 공부 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 9084 동전(https://www.acmicpc.net/problem/9084) 풀이 과정 : j원을 만들 수 있는 경우의 수를 dp[j]라 한다면 동전의 한 종류인 i원을 더한 j+i원을 만드는 경우의 수도 dp[j+i]를 더함으로서 구할 수 있다. 정답코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys ans = [] t = int(sys.stdin.readline()) for _ in range(t): n = int(sys.stdin.readline()) coin = list(map(int,sys.stdin.readline().split())) m = int(sys.stdin.readline()) dp = [0] * 10001 dp[0] = 1 for i in coin: for j in range(1,m+1): if j-i >= 0: dp[j] += dp[j-i] ans.append(dp[m]) print(*ans, sep='\n') 출처 : ...

1.개발 진행 및 완료상황 2주차 python algorithm 문제풀이 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 2252 2252번: 줄 세우기 2252번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 줄 세우기 스페셜 저지 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 37709 21883 14481 56.278% 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, … ...