분류 전체보기

🗂️ 문제링크: https://www.acmicpc.net/problem/1699 💡 접근법제곱 수는 1, 4, 9, 16 … 등이 있다.항의 최소 개수를 구하기 위해서는 제곱 수를 이용해야 한다. 한 가지 예시로 12의 경우, dp[12] = min(dp[1] + dp[11], dp[4] + d[8], dp[9] + dp[3])이다.즉, 제곱 수를 기준으로 모든 경우의 수를 계산해서 최소가 되는 값을 저장해야 한다. 😎 내 코드import sysimport mathN = int(sys.stdin.readline())dp = [100000] * (N+1)dp[0] = 0dp[1] = 1for i in range(1, N+1): for j in range(1, int(math.sqrt(i))+1..

🗂️ 문제링크: https://www.acmicpc.net/problem/11727 💡 접근법N=1일 때, 2x1 직사각형을 채우는 방법의 수는 2x1 크기의 타일 하나로 채우는 방법 1가지이다.N=2일 때, 2x2 직사각형을 채우는 방법의 수는 2x1 크기의 타일 2개를 이어붙이는 방법, 1x2 크기의 타일 2개를 이어붙이는 방법, 2x2 크기의 타일 하나로 채우는 방법, 총 3가지이다. N=3일 때, 2x3 직사각형을 채우는 방법은 다음과 같다.2x2 직사각형에 2x1 직사각형을 이어붙인다.2x1 직사각형에 1x2 크기의 타일 2개를 이어붙이거나, 2x2 크기의 타일 1개를 이어붙인다.이때, 2x1 크기의 타일 2개를 이어붙이는 경우의 수는 1번에 포함되기 때문에 카운트하지 않는다.이를 점화식으로..

🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42628# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 접근법처음에는 min heap과 max heap을 각각 생성하고 이를 통해 최댓값, 최솟값을 찾아주려고 했다. 하지만 이렇게 하면 일일히 min heap에서 삭제된 값을 max heap에서도 찾아 삭제해야 한다는 단점이 있다. 따라서 하나의 힙을 생성하여 문제를 해결한다. 최소 힙에서 최댓값을 구하는 방법은 다음과 같다.힙 자료구조 또한 리스트 기반이기 때문에 max(heap..

🗂️ 문제링크: https://www.acmicpc.net/problem/2468 💡 접근법BFS 알고리즘을 통해 기준 높이보다 지역의 높이가 높아 물에 잠기지 않는 영역의 개수를 구한다. 이를 구하기 위해선 BFS 알고리즘을 통해 인접한 지역(상하좌우)을 탐색할 때 방문하지 않았던 위치(not visited[nx][ny])이면서 기준 높이보다 해당 지역의 높이가 높아야 한다(maps[nx][ny] > h). 지도에서 최대 지역의 높이를 찾아 최대 높이만큼 반복하여 안전한 영역의 최대 개수를 구한다. 😎 내 코드import sysfrom collections import dequeN = int(sys.stdin.readline())maps = []max_height = 0for _ in range(..

🗂️ 문제링크: https://www.acmicpc.net/problem/7562 💡 접근법나이트가 이동할 수 있는 범위를 dx와 dy로 생성한다.이후 맵의 크기에 맞게 False로 maps를 초기화하고, deque를 통해 큐를 생성한다. 초기 시작 위치값인 a와 b를 입력받고, maps[a][b]=0으로 초기화한다.while()문을 통해 큐의 맨 왼쪽 값을 pop하면서 나이트가 이동할 수 있는 범위를 모두 탐색한다. 이때 맵을 벗어나지 않으면서 방문한 적 없는 위치일 경우 큐에 현재 위치를 추가하고 maps에 현재 값을 업데이트한다. 이때 업데이트되는 값은 처음부터 지금까지 이동한 횟수를 나타낸다. 만약 종료 위치에 도달했을 경우 큐를 비워 while문을 빠져나온다.최종적으로 이동하려는 위치에 해당..

🗂️ 문제링크: https://www.acmicpc.net/problem/1966 💡 접근법제일 왼쪽의 값을 쉽게 꺼내기 위해 deque를 사용한다. 문서가 몇 번째로 인쇄되는지 횟수를 세기 위해 인덱스를 저장해야 한다. 이를 위해 queue에 튜플 형식으로 (인덱스, 중요도)를 저장한다.while()문을 통해 큐에서 왼쪽에 위치한 값을 하나씩 꺼내고, 만약 그 다음 값들 중 현재 값보다 중요도가 높은 문서가 있다면 다시 큐에 현재 값을 삽입한다. 이때 인쇄가 될 경우 카운트 횟수를 증가시켜야 한다. 따라서 큐에서 현재 값을 꺼낼 때 카운트를 1 증가시키고, 만약 현재 값보다 중요도가 큰 문서를 발견하여 현재 값을 다시 큐에 삽입하게 되면 카운트를 1 감소시킨다. target에 궁금한 문서를 저장해 ..

🗂️ 문제링크: https://www.acmicpc.net/problem/2667 💡 접근법DFS를 사용하여 연결된 집의 개수를 구한다. 이때 dx와 dy 리스트를 통해 현재 위치에서 상하좌우로 이동할 수 있게 하고, 이동한 좌표가 1) 지도 밖을 벗어나지 않는지, 2) 집이 존재하는지, 3) 방문한 적이 없는지를 확인한다. 모든 조건을 만족할 경우 재귀로 DFS를 수행하고, 수행한 횟수를 cnt로 계산한다.해당 값이 단지에 속하는 집의 개수가 된다. 😎 내 코드import sysN = int(sys.stdin.readline())house_num = []visited = [[False] * N for _ in range(N)]maps = []for _ in range(N): maps.appe..

🗂️ 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 접근법딕셔너리를 생성하여 입력값 clothes의 의상의 종류를 Key로, 의상의 종류에 해당하는 의상의 이름을 value로 추가한다. 옷을 조합하는 경우의 수는 다음과 같다.각각의 의상의 종류에서 의상을 0개 선택할 수도 있다. 따라서 의상의 개수 + 1을 종류 별로 계산하여 곱해주고, 적어도 하나의 의상은 입어야 하므로 곱한 값에서 1을 빼야 한다. 😎 내 코드def sol..