[백준 python] 1432번 그래프 수정 레벨: 플레티넘5 언어: 파이썬 📑풀이 과정 이 문제는 정글 ㅇㅎㅈ님의 설명을 듣고 이해한 문제이다. 감사합니다ㅎㅎ V1 → V2로 연결된 간선이 있을때, V2의 번호는 V1보다 커야한다. 위 조건으로 간선의 번호를 바꾸면 위상정렬 시 노드의 번호 순서(오른차순)으로 나와야한다는 말이다. 문제에 대한 이해 예시) 1번 그림 표현 위 예시를 위상정렬하면 1 2 4 5 3 이 나오고 위 예시를 위상 정렬시 1 2 3 4 5 로 출력하려면 아래와 같이 노드를 바꾸면 된다. 첫번째 그림의 노드위치가 아래로 바뀌면서 1 → 1 2 → 2 3 → 5 4 → 3 5 → 4 으로 바뀌게 되고 예시 답인 1 2 5 3 4 가 나오게 된다. 그리고 그래프에서 사이클이 발생하면 ..

[백준 python] 10000번 원 영역 레벨: 플레티넘5 언어: 파이썬 https://www.acmicpc.net/problem/10000 📑풀이 과정 일단 이 문제는 풀이과정을 다른 사람 블로그를 보고 아이디어를 얻어서 풀이했다. https://polohee81.tistory.com/51 초기 풀이 아이디어를 보고 싶은 사람은 위의 주소로 접소해서 읽어보길 바란다. 핵심 풀이 아이디어 x선에 접하는 원의 경계선을 괄호로 생각하고 풀이 위의 원을 괄호로 변환하면 (( )( )) 라고 볼 수 있다. 이 때 안의 원 두개가 사이 공간없이 이어져 있으면 밖의 원의 영역은 2개가 된다. 아래의 사진은 원과의 사이가 벌어져 있어 밖의 원의 영역이 1개이다. 괄호로 변환하면 (( ) ( ) ) 라고 볼 수 있다..

[백준 python] 10819번 차이를 최대로 -재귀, 순열 풀이 레벨: 실버 1 언어: python 문제풀러가기 📑풀이 과정 재귀와 순열 각 다른 방식으로 풀어 보았다. 1번 재귀 n = int(input()) in_list = list(map(int ,input().split())) visited = [False]*n answer = 0 def sol(li): global answer if len(li) == n: total = 0 for i in range(n-1): total += abs(li[i]- li[i+1]) answer = max(answer, total) return for i in range(n): if not visited[i]: visited[i] = True li.append(..

[백준 python] 18428번 감시 피하기 레벨: 실버 1 언어: python 문제풀러가기 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 📑풀이 과정 이 문제는 14502번 연구소 문제와 비슷하다고 생각하여 그러한 방식으로 풀이를 접근했다. 이 문제를 풀기 위해서는 크게 2가지가 필요하다. 장애물을 설치하는 함수 선생의 상하좌우 일직선으로 학생이 있는지 확인하는 함수 1번 함수(solution(count)) solution 함수는 벽을 설치할 수 있는 모든 경우를 찾는 함수이다. 1번의 함수는 재..

[백준 python] 18405번 경쟁적 전염 - DFS/BFS 레벨: 실버1 언어: python 문제풀러가기 📋풀이 코드 import sys from collections import deque input = sys.stdin.readline n, k = map(int, input().split(' ')) graph = [list(map(int, input().split(' '))) for _ in range(n)] t_s, t_x, t_y = map(int, input().split(' ')) virus = [] for i in range(n): for j in range(n): if graph[i][j] != 0: # 바이러스 번호, 시간, X 위치, Y 위치 virus.append((graph[i..

[백준 python] 18352번 특정 거리의 도시 찾기- DFS/BFS 레벨: 실버 2 언어: python 문제풀러가기 📑풀이 과정 이 문제에서 보면 모든 도로의 거리는 '1'이란 조건이 있다. 그래프에서 모든 간선(문제에서 도로)의 길이가 동일 할 때는 BFS를 이용하여 최단 거리를 찾을 수 있다. 일반적으로 DFS/BFS 알고리즘을 배울때 방문여부를 저장하는 배열을 사용하는데 이 문제에서는 방문여부를 저장하는 배열에 거리 정보를 담아서 탐색하면된다. distance라는 거리 정보를 답은 배열을 -1로 초기화 한다. 탐색시 -1의 값은 아직 방문하지 않은 노드(도시)이다. 그리고 문제 설명에서 출발 도시 X에서 X로 가는 최단거리는 항상 0이니 distance[x] = 0으로 초기화 해..

[백준 python] 1339번 단어 수학 - 그리디 레벨: 골드 4 언어: python 문제풀러가기 📑풀이 과정 초반에 상당히 헤매다가 질문 검색에서 힌트를 얻어서 구현하였다. 처음 아이디어는 자리수가 높은 알파벳부터 낮은 알파벳 순으로 숫자를 부여했다. 이때 문제는 아래와 같은 케이스가 들어오면 A를 9로 바꾸고 B를 8로 바꿔서 오답이 난다. 10 ABB BB BB BB BB BB BB BB BB BB 이제 제대로 된 풀이를 설명하겠다. 자리수를 사용하면 되지만 단순히 순서만을 가지고는 풀 수 없다. 알파벳의 자리수 만큼 곱한 값을 기준으로 순서를 정해야 한다. 2 GCF ACDEB 위의 예시는 A 는 만자리 10000 C 는 천자리 하나와 십의 자리 하나 1000 + 10 D 는 백자리 하나 10..

[백준 python] 19941번 햄버거 분배 - 그리디 레벨: 실버3 언어: python 문제풀러가기 📑풀이 과정 생각한 아이디어를 코드로 구현할 수 있다면 누구나 쉽게 풀 수 있는 문제이다. 햄버거를 먹을 수 있는 최대 사람의 수는 사람의 위치 P에서 -k ~ +k안에 햄버거가 있는지 탐색하면 된다. 그리고 찾은 햄버거 'H'를 다른 값으로 바꿔주어 다시 카운팅 하지 않게 한다. 0 1 2 3 4 -> 위치 H P P P H 이고 k = 1 일 때 처음 p에서 0 ~ 2까지 탐색하여 H(햄버거)를 다른 값(필자는 o로 바꿈)으로 바꿔서 o P P P H 가 되고 최종적으로 o P P P o가 되며 최대 인원은 1번과 3번이 햄버거를 먹어서 2명이 된다. ! 단 탐색 시 주의할 점은 테이블 배열의 시작..