algorithm

[python] 프로그래머스 - 피로도(위클리챌린지)

🤔문제 해결 💫 던전의 길이가 최대 8개 이므로 permutation으로 탐험하는 순서의 모든 경우의 수를 구했다. 💫 탐험 순서대로 던전을 탐험하며 피로도 조건에 맞는 동굴만 탐험하며 갯수를 세어준다. 💫 각각의 사이클마다 탐험가능한 동굴의 갯수를 최대값으로 업데이트 해준다. 💻소스 코드 from itertools import permutations def solution(k, dungeons): answer = -1 for perm in (permutations(dungeons, len(dungeons))): cur_k = k expol_cnt = 0 for dungeon in perm: if cur_k >= dungeon[0]: expol_cnt += 1 cur_k -= dungeon[1] answ..

[python] 프로그래머스 - 음양 더하기

🤔문제 해결 signs 가 True 이면 더하고, False 이면 빼준다. 💻소스 코드 def solution(absolutes, signs): answer = 0 for i in range(len(absolutes)): if signs[i] is True: answer += int(absolutes[i]) else: answer -= int(absolutes[i]) return answer 📕문제 확인 출처: 프로그래머스 링크: https://programmers.co.kr/learn/courses/30/lessons/76501?language=python3 코딩테스트 연습 - 음양 더하기 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차..

[python] 백준 - 7569. 토마토

🤔문제 해결 1. BFS | silver1 2. 익은토마토(값이 1)를 찾아서 리스트에 담는다. 3. 3번의 리스트를 BFS를 실행한다. 4. 4번을 다 하고 나면 아직 익지 않은 토마토(0)가 있는 확인하고 있으면 -1을 답으로 출력 5. 없으면 가장 큰 값에서 -1한 값을 답으로 출력 💨 3차원 배열이라서 헷갈릴 수 있는 문제. 하지만 단순히 BFS로 풀면 된다. 💻소스 코드 from _collections import deque dx, dy, dz = [-1, 1, 0, 0, 0, 0], [0, 0, -1, 1, 0, 0], [0, 0, 0, 0, -1, 1] # 아래층 윗층 앞 뒤 좌 우 # BFS로 주변 토마토 익히기 def ripen(): while q: x, y, z = q.popleft()..

[python] SWEA - 1251. [S/W 문제해결 응용] 4일차 - 하나로

🤔문제 해결 1. D4 | MST - prim 2. 간선의 가중치를 값으로 하는 인접 행렬을 만든다 3. 최소 값을 갱신해줄 가중치 리스트, MST에 포함되지 체크하는 리스트, 부모노드 선택리스트를 만든다. (여기서는 모든 노드가 연결될 수 있기 때문에 부모노드는 필요하지 않을 수 있음) 4. 시작점을 선택(여기서는 0)하고 간선을 돌며 탐색한다 (1) 아직 MST에 포함되어 있지 않고, 가중치가 최소인 정점 u를 찾는다. (2) u를 MST에 포함시키고, 그 가중치를 결과값에 더해준다. (3) 가중치를 최솟값으로 갱신하기 위해 u에 인접하고 아직 mst가 아닌 정점(w) 중에서 key[w] > u-w 이면 갱신한다 5. 모든 노드를 선택할 때까지 4번을 반복한다. 💨 최소신장트리 알고리즘, 크루스칼과 ..

[python] SWEA - 1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기

🤔문제 해결 1. D4 | 스택? 2. 괄호를 처음부터 하나씩 검사한다. 3. 왼쪽 괄호일 경우 스택에 넣는다. 4. 오른쪽 괄호일 경우 스택의 마지막에 있는 괄호와 비교하여 짝이 맞는지 검사한다. 5. 짝이 맞으면 통과 6. 아니라면 이 괄호들은 맞지 않는 괄호이다. 종료 💨 가볍게 스택을 연습하는 문제 💻소스 코드 def isRight(parenthesis): stack = [] for paren in parenthesis: # 왼쪽 괄호 if paren in parenthesis_list[0]: stack.append(paren) # 오른쪽 괄호 else: if stack: k = stack[-1] for i in range(4): # 괄호 네가지중 짝이 맞다면 통과 if k == parenthes..

[python] SWEA - 1226. [S/W 문제해결 기본] 7일차 - 미로1

🤔문제 해결 1. D4 | DFS 2. 시작점을 찾는다. 3. 스택을 활용하고 상하좌우 4방향 탐색(인덱스 범위 이내)을 한다. (1) 길('0')을 만날 경우 스택에 추가하고, 나중에 다시 탐색하는 것을 방지하기 위해 그 지점의 값을 바꿔준다. (2) 끝('3')을 만날 경우 미로가 가능하다는 의미 이므로 답을 1로 하고 탐색을 종료한다. 💨 DFS 기본문제이다. 💻소스 코드 dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] for _ in range(10): answer = 0 n = int(input()) maps = [list(input()) for _ in range(16)] # 출발점 찾기 x, y = 0, 0 for i in range(16): for j in range(1..