Algorithm

2023년 11월 10일 알고리즘 문제풀이 문제 게임 맵 최단 거리 난이도 Lv.2 코드 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 from collections import deque def solution(maps): answer = -1 n = len(maps) m = len(maps[0]) da = [1,-1,0,0] db = [0,0,1,-1] maps[0][0] = 0 q = deque() q.append([0,0,0]) while q: a,b,cnt = q.popleft() if a == n-1 and b == m-1: answer = cnt+1 print(a,b) return answer for i in range(4): na = a + da[i] nb = b + db[i] if na < 0 or na >= n or nb < 0 or nb >= m or not maps[na][nb]: continue q.append([na,nb,cnt+1]) maps[na][nb] = 0 return answer BFS를 이용해서 특정 조건(맵 상 벽이라던가, 맵 범위 밖이라던가, 방문한 곳이라던가)을 제외하여 최단 거리를 구하는 문제는 이제 충분히 적응됐다. ...

2023년 11월 9일 알고리즘 문제풀이 문제 링크 난이도 Lv.1 코드 1 2 3 def solution(arr): answer = sum(arr)/len(arr) return answer

2023년 10월 13일 알고리즘 문제풀이 문제 1 삼각달팽이 문제 링크 1차 시도 나의 생각 처음에는 각 삼각형의 높이마다 배열을 만들어주고 해당 높이에 append로 추가해주면 되겠다 생각했다. 하지만 정답을 출력할 때 순서대로 출력해야하다보니 각 배열 안에서의 순서가 지켜지지 않게 되는 것을 깨달았다. 따라서 각 행의 길이를 직접 정해주었다. i번째 행은 길이가 i가 되도록 배열을 만들었다. 삼각형 한 바퀴를 도는 것을 기준으로 함수를 만들었다. 함수의 인수 cnt는 넣을 숫자, l은 이번에 돌 삼각형의 한 변의 길이, idx는 출발이 몇번째 행인지를 나타내고, depth는 함수가 실행된 횟수이자 지금 도는 삼각형이 내부에서 얼마나 깊이 있는지를 의미한다. ...

2023년 10월 12일 알고리즘 문제풀이 문제 1 주차 요금 계산 문제 링크 1차 시도 나의 생각 차를 배열에 넣고 관리하려고 했는데, 그러기 위해선 index를 알고 있어야 했다. 그렇지 않으면 매번 차량 번호로 검색을 해야해서 너무 비효율적인 알고리즘이 될 것 같았다. 나는 생각을 바꿔서 차량 번호는 4자리 숫자기 때문에 1만개 짜리 배열을 만들어서 차량 번호를 index로 해주었다. 각 값은 길이가 2인 배열이였는데 입차 시간과 총 주차 시간을 넣어주었다. 총 주차 시간은 해당 차량이 여러번 나오고 들어올 수 있기 떄문에 설정했다. ...

2023년 10월 11일 알고리즘 문제풀이 문제 1 프로세스 문제 링크 1차 시도 나의 생각 프로세스가 담긴 배열에서 첫번째가 우리가 알고싶은 프로세스 인지 아닌지, 또 가장 높은 우선순위를 지녀 실행될 차례인지, 아닌지로 구분하였다. location은 현재 우리가 알고싶은 프로세스의 index이고, answer는 몇번째로 실행되었는지를 의미한다. 알고 싶은 프로세스 관심 없는 프로세스 최우선순위 answer 출력 popleft() 한다. 실행되었기 떄문에 answer 1 증가 차우선순위 popleft()하여 맨 뒤로 보낸다. location도 맨 뒤로 설정한다. popleft()후 맨 뒤로 보낸다. locaion 1 감소 결과 정답 ...

2023년 9월 18일 알고리즘 문제풀이 문제 1 백준 1946 문제 링크 1차 시도 나의 생각 서류에서 1등을 한 사람의 면접 성적을 기준으로 삼았다. 이 기준보다 면접 성적이 높은 사람만 합격할 수 있다. 기준보다 면접 성적이 낮은 사람은 서류 성적도 당연히 낮다. 서류 1등의 성적을 기준으로 하였으니까.. 문제는 이 기준에서 설정한 사람들 내에서도 문제의 조건으로 탈락하는 사람이 생길 수 있다. 리스트를 2번 순회하였더니 시간초과가 나서 큐를 이용해 최소 힙을 구현하여 수행 시간을 줄였지만 오답처리 되었다. ...

2023년 9월 16일 알고리즘 문제풀이 문제 1 백준 1030 문제 링크 1차 시도 나의 생각 분할정복으로 풀면 되겠다고 생각했다. 정사각형 한 변의 길이는 1초마다 n이 곱해져 결국 s초 후 n의 s제곱 형태가 된다. s는 최대 10, n은 최대 8이므로 한 변의 길이는 최대 2의 30제곱이나 된다. 전체 정사각형 배치를 그린 후 원하는 부분만 출력하기엔 너무 크다는 뜻이다. 문제에서 출력하라고 요구하는 부분만 출력해야 한다. 이 부분이 너무 어려워서 다른 사람들의 풀이를 보고 공부한 코드이다. l은 위에서 말했던 n의 s제곱이자 s초 후 정사각형의 한 변의 길이이다. main 함수는 평면의 한 변의 길이와 검은색인지 확인할 곳의 행렬을 x,y로 받는다. 중앙의 k x k 크기의 사각형에 포함된다면 검은색이므로 1을 반환한다. ...

2023년 9월 15일 알고리즘 문제풀이 문제 1 백준 11047 문제 링크 1차 시도 나의 생각 최소한의 동전을 사용하기 위해선 최대한 가치가 큰 동전을 많이 사용해야 한다. 이를 위해 입력받은 동전을 큐에 저장해 최대 힙을 사용하였다. 가장 큰 동전부터 가능한 갯수만큼 사용했다. 기존에는 이중 반복문을 사용해서 가장 큰 동전을 여러번 쓰도록 구현했지만 시간초과가 문제가 되었다. 따라서 몫과 나머지를 이용해서 한번만 실행되도록 바꾸었더니 통과되었다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import sys from heapq import heappush, heappop n, k = map(int, sys.stdin.readline().split()) coins = [] for _ in range(n): heappush(coins, -1*int(sys.stdin.readline())) cnt = 0 while k > 0 and coins: val = -1*coins[0] if k >= val: tmp = k//val cnt += tmp k %= val heappop(coins) print(cnt) 문제 2 백준 1541 문제 링크 ...

2023년 9월 9일 알고리즘 문제풀이 문제 1 백준 12865 문제 링크 1차 시도 나의 생각 입력값을 받을 때 무게 제한보다 무거운 물건은 아예 받지 않도록 조건을 추가한다. 큐를 이용한 최소힙을 통해 물건의 무게와 가치를 원소로 하는 배열에서 무게가 낮은 순서로 하나씩 pop한다. 배낭을 나타내는 배열에 [0,0]을 추가하여 아무것도 없는 상태를 만든다. pop할 때마다 기존 가방에 있는 것에 현재 물건을 더한 것을 추가해준다. 이 방식이면 원소갯수가 2배씩 늘어난다. 비어있는것 1개 => 첫번째 물건 더한것과 안더한것 2개 => 앞의 2개에 각각 두번째 물건을 더한것과 안더한 것 해서 총 4개 => 8개 => … ...

2023년 9월 8일 알고리즘 문제풀이 문제 1 백준 9273 문제 링크 1차 시도 나의 생각 결국 두 자연수 a,b에 대하여 1/n = 1/a + 1/b 가 성립해야 한다고 생각했다. 따라서 이 수식을 고쳐서 b = na/(a-n) 으로 만들었다. 이 함수를 a,b 에 대한 함수로 이해해보자. b-n = (n^2)/(a-n). 유리함수중에 분수 함수라고 할 수 있다. 점근선은 x =n, y = n이다. 아래와 같은 함수이다. 이 그래프에서 x,y가 모두 자연수인 함수 위 좌표를 찾았다. x가 0일 때 y가 n이다. x가 1이면 y는 자연수일 수 없다. 따라서 x가 2부터 1씩 증가하다가 y값이 음수면 멈췄다. ...