반응형 알고리즘80 [Python] Baekjoon - 1525. 퍼즐 퍼즐 문제는 1에서 8까지의 숫자로 채워진 3x3 퍼즐을 맞추는 문제이다. 퍼즐을 움직이는 최소 횟수를 구하기 위해 그래프 탐색 알고리즘 중 너비 우선 탐색을 사용하여 풀 수 있다. 난이도는 골드 2이다. 메모리가 초과되지 않도록 방문 확인 배열을 선언하는 것이 중요하다. 백준 1525번 퍼즐 문제 정보 알고리즘 분류 - 그래프 탐색 (BFS) 난이도 - 골드 2 퍼즐 문제 요약 1~8로 채워진 3x3 퍼즐이 있는데 나머지 한 칸은 빈칸이다. 빈칸의 상하좌우 칸만 빈칸으로 이동할 수 있을 때, 왼쪽 위에서부터 1 2 3 4 5 6 7 8 (빈칸) 상태가 되도록 움직이는 최소 횟수를 구하는 문제다. 문제 풀이 과정 최소 횟수를 구하는 문제이므로 BFS를 이용한다. 무한루프에 빠지지 않기 위해(답이 없는 경.. 2021. 7. 17. [Python] Baekjoon - 2751. 수 정렬하기 2 백준 2751번 수 정렬하기 2 문제는 N개의 중복되지 않은 숫자들을 정렬하는 문제이다. N의 범위가 넓기 때문에 시간 초과를 염두하고 풀어야 한다. 퀵 정렬을 이용하면 최악의 경우로 시간이 초과될 수 있으므로 항상 시간 복잡도가 일정한 병합 정렬을 사용하는 것이 좋다. 백준 2751번 수 정렬하기 2 문제 정보 알고리즘 분류 - 정렬 난이도 - 실버 5 수 정렬하기 문제 요약 N개의 중복되지 않은 숫자들이 주어졌을 때, 이를 정렬하여 출력하는 문제다. 여기서 N의 범위는 1 이상 1,000,000이하이다. 문제 풀이 과정 처음에는 퀵 소트를 짜서 제출했으나 시간이 초과되었다. 최악의 경우에 시간 복잡도가 커지기 때문인 것 같다. 따라서 시간 복잡도가 항상 일정한 병합 정렬을 이용하였다. merge 과정.. 2021. 7. 17. [Python] Baekjoon - 15654. N과 M (5) 백준의 N과 M 시리즈는 N개의 숫자가 포함된 수열에서 M개를 고르는 문제이다. 매번 조건이나 규칙이 변경되어 총 12개의 문제가 있다. 이번 문제는 사전 순으로 증가하는 순서로 출력하는 문제이며 백트래킹을 이용하여 풀 수 있다. 난이도는 실버 3이다. 백준 15654번 N과 M (5) 문제 정보 알고리즘 분류 - 백트래킹 난이도 - 실버 3 N과 M (5) 문제 요약 중복 없는 N개의 숫자 중 M개를 선택하여 사전 순으로 증가하는 순서로 출력하는 문제다. 문제 풀이 과정 DFS를 이용하여 현재까지 방문하지 않은 숫자를 방문하고, M개의 숫자가 선택되면 출력한다. 사전 순으로 출력하기 위해 초기에 입력받은 수열을 정렬 후 수행한다. 코드 import sys def dfs(cnt): global N, M,.. 2021. 7. 15. [Python] Baekjoon - 10026. 적록색약 빨간색과 초록색의 차이를 거의 느끼지 못하는 것을 적록색약이라고 한다. 백준 10026번 적록색약 문제는 RGB로 구성된 그림에 대해 적록색약인 사람과 아닌 사람이 봤을 때 보이는 구역의 수를 구하는 문제이다. 그래프 탐색 알고리즘을 이용하여 해결할 수 있으며 난이도는 골드 5이다. 백준 10026번 적록색약 문제 정보 알고리즘 분류 - 그래프 탐색 난이도 - 골드 5 적록색약 문제 요약 NxN 크기의 그리드의 각 칸이 R, G, B 중 하나의 색으로 칠해져 있다. 하나의 색으로 이어진 칸들을 하나의 구역이라고 하는데, 적록색약인 사람은 R과 G가 거의 구분이 가지 않아 하나의 색으로 보인다고 한다. 적록색약이 아닌 사람에게 보이는 구역의 개수와, 적록색약인 사람에게 보이는 구역의 개수 구하여라. 문제 .. 2021. 7. 14. 이전 1 ··· 15 16 17 18 19 20 다음 반응형
