전체 글

🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42898# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 🚀 시행착오def solution(m, n, puddles): # m: 열, n: 행 answer = 0 dict = {} # key: 경로, value: 경로 개수 visited = [[False] * (m+1) for _ in range(n+1)] dx = [0, 1] # 아래쪽, 오른쪽 dy = [1, 0] def DFS(y, x, cnt): visi..

🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42746# 💡 접근법주어진 숫자 리스트를 이어붙여 만들 수 있는 모든 경우의 수를 탐색하면 시간 초과가 발생한다. 따라서 문자열 정렬을 활용해 가장 큰 수를 만들어야 한다. 문자열 정렬의 특성- 문자열 정렬은 숫자의 크기나 자릿수와 상관없이 문자 순서대로 사전식 정렬된다.- 문자열의 길이가 다를 때, 더 짧은 문자열은 사전식 정렬에서 먼저 온다.    ex) "1"과 "10"을 비교하면, "1"이 "10"의 부분 문자열이므로 "1"이 "10"보다 앞에 정렬된다. 올바른 정렬을 수행하기 위해 자릿수를 맞춰서 비교해야 한다.문자열 정렬은 사전식 정렬로 수행되므로, 이는 [1, 10] ..

🗂️ 문제링크: https://www.acmicpc.net/problem/2606 💡 접근법1번 컴퓨터가 웜 바이러스에 걸렸고, 이와 네트워크 상에 연결된 모든 컴퓨터가 바이러스에 걸리게 된다. 따라서 1번과 연결된 노드의 개수를 구하면 되는 문제이다. DFS, BFS 두 가지 방식으로 모두 해결 가능하며, 아래는 DFS를 통해 푼 코드이다.연결된 노드에 대해 방문처리를 해주므로, 최종적으로는 방문처리가 된 노드의 개수에서 1번 노드를 빼주면 된다. 😎 내 코드import sysN = int(sys.stdin.readline())K = int(sys.stdin.readline())graph = [[] for _ in range(N+1)]visited = [False] * (N+1)for _ in r..

🗂️ 문제링크: https://www.acmicpc.net/problem/15903  💡 접근법m번의 합체 이후에 카드의 합이 가장 작은 경우를 찾아야 한다.카드 합체의 경우 두 카드의 합을 다시 두 카드에 덮어씌우는 방식이므로, n장의 카드 중 가장 작은 두 값의 합을 덮어씌워야 최종적으로 모든 카드의 합이 가장 작아질 수 있다. 따라서 항상 제일 작은 두 값을 뽑아야 한다.이때 정렬을 이용할 수도 있겠지만, 제일 작은 값이 필요하므로 최소 힙을 통해 가장 작은 값을 두 번 꺼낸다. 또한 두 값의 합을 아까 뽑은 카드에 업데이트해주어야 하는데, 초기 입력된 카드의 인덱스가 필요하지 않으므로 꼭 뽑은 카드에 값을 업데이트할 필요 없이 힙에 새로운 값을 두 번 추가함으로써 이를 구현할 수 있다. 😎 ..

🗂️ 문제링크: https://www.acmicpc.net/problem/1715  💡 접근법10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.즉, 카드 묶음의 개수가 적은 것끼리 먼저 비교하는 방법이 가장 효율적이다. 이를 구현하기 위해 최소 힙을 사용한다. 만약 최소힙을 사용하지 않고 일반 정렬로 구현한다면, 매번 새로운 카드 묶음이 추가될 때매대 새로 정렬을 수행해야 한다.하지만, python에서 sor..

🗂️ 문제링크: https://www.acmicpc.net/problem/1697  💡 접근법maps라는 1차원 리스트를 선언하고, BFS를 통해 현재 위치에서 +1, -1, *2칸을 더한 위치를 탐색한다. 이때 방문 처리를 위한 visited라는 리스트는 따로 생성하지 않고, maps가 0인 경우 방문하지 않은 것으로 간주하여 처리한다. 또한, 위치의 범위(0 ≤ N ≤ 100,000)가 정해졌으므로, 이를 기준으로 리스트의 길이와 위치 범위를 벗어났을 때의 처리 조건을 미리 선언해 둔다. 만약 현재 위치가 수빈이의 위치(K)일 경우 조건문을 통해 탈출하고, 현재 위치의 값을 반환한다. 😎 (틀린) 내 코드import sysfrom collections import dequeN, K = map(i..

🗂️ 문제링크: https://www.acmicpc.net/problem/11723  💡 접근법입력값이 ‘add 1’과 같이 2개로 분리하여 사용하는 경우와 ‘all’과 같이 1개로 사용해야하는 경우가 있다. 이는 “ “로 split한 뒤 리스트의 길이를 확인함으로써 두 가지의 경우를 다르게 처리한다. 😎 내 코드import sysM = int(sys.stdin.readline())S = set()for _ in range(M): a = sys.stdin.readline().split() if len(a) == 2: a, x = a[0], int(a[1]) else: a = a[0] if a == "add": S.add(x) elif ..

🗂️ 문제링크: https://www.acmicpc.net/problem/1012  💡 접근법상하좌우로 인접해 있는 배추 무리의 개수를 구하는 문제이다. 따라서 너비 우선 탐색인 BFS를 사용하여 이를 계산하면 된다.maps 리스트를 생성하고, 입력값으로 들어오는 배추의 위치에 값을 1로 둔다.visited[] 리스트를 생성하여 방문한 위치에 대해서는 방문 처리를 해준다.모든 좌표를 순회하면서 1. 배추가 존재하면서 2. 방문하지 않은 조건에 해당하는 경우를 찾는다.만약 조건에 해당한다면, BFS()를 통해 인근 배추에 방문 처리를 한다. 이때 BFS()가 실행되는 수가 우리가 찾고자 하는 배추흰지렁이의 개수이다.BFS()에서는 미리 선언해 둔 dx, dy 리스트를 통해 현재 위치에서 상하좌우에 대해..