📁문제 풀이/🧩Baekjoon

[Python] 백준 11404 플로이드 | 플로이드 워셜

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 해결 포인트 - 플로이드 워셜 알고리즘 - graph : 2차원 배열로 노드 별 각 노드까의 최소 거리를 저장한다. graph[i][j] 는 i에서 j로 가기 위한 최소 이동 거리를 의미함 - 각 간선 정보를 따라 무한수(INF)로 초기화 한 graph를 수정한다. 동일한 노선의 길이가 다른 간선이 있음으로 주의 필요 - a -> b 노선에 대..

[Python] 백준 18352 특정 거리의 도시 찾기 | 다익스트라 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 해결 포인트 - 다익스트라(Dijkstra) 알고리즘 - distance : X로부터 각 노드의 가장 짧은 경로. 경로가 없다면 무한수(INF) - graph : 각 노드가 연결되어 있는 정보 (연결 리스트) - q : 지금까지 계산 된 거리 중 간선이 가장 짧은 것을 ..

[Python] 백준 1753 최단 경로 | 다익스트라 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 해결 포인트 - 대표적인 다익스트라(Dijkstra) 알고리즘 문제 - 시작노드부터 각 노드까지 최소 거리를 저장하는 배열(distance)을 무한수(INF)로 초기화 - 연결 리스트 graph를 선언하여 각 노드의 연결 여부와 무게를 튜블형태로 저장 : graph[i][0]은 i와 연결된 노드를 의미하고 ..

[Python] 백준 1463 1로 만들기 | DP

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해결 포인트 - 전형적인 다이나믹 프로그래밍 문제이다. - 각 인덱스 번호를 구하기 위해서 필요한 최소 연산을 저장할 리스트를 입력 받은 N 크기로 생성. - 다이나믹 프로그래밍 바텀업(BottomUp) : 반복문 탑다운(TopDown) : 재귀 바텀업 방식이 스택 크기 제한으로부터 자유로움으로, 처음 연산을 저장하여 이후 동일한 연산 발생시 이를 사용하여 중복 연산을 피할 수 있다. - 최종적으로 1을 만드는 프로그램이므로 2부터 구하려는 n까지 각 수를 ..

[Python] 백준 9663 N-Queen | 시간초과

정답은 알맞게 나오는데 자꾸 시간초과가 나오는 분들은 언어를 Python3가 아닌 Pypy3로 설정하고 실행해보시기 바랍니다 ~목차~ 문제 문제 해결 포인트 작성 코드 문제 전형적인 Backtracking 문제입니다! https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 포인트 1. row[i] : i번째 행에서 퀸의 열 값을 나타내는 1차원 배열 row를 사용함으로 메모리 낭비 방지 2. promising 함수 : 대각선에 위치하거나 같은 열에 위치하는..

[Python] 백준 10819 차이를 최대로 | 순열/조합 | Permutations/Combinations

~실버 2~ 백트래킹(Backtracking) 알고리즘을 학습하는 과정에서 만난 백준 문제! https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net [최종 코드] from itertools import permutations n = int(input()) alist = list(map(int, input().split())) maxN = 0 nPr = permutations(alist) for p in nPr: temp = 0 for i in range(n-1): ..

[Python] 백준 2089 -2진수

~실버 2~ [해결 포인트] 1. 2진수처럼 -2의 나머지를 저장하여 출력 2. 나머지가 0이 아닐 때 +1 [최종 코드] n = int(input()) result = [] if n == 0: # 입력 값이 0일 때 print(0) else: while n != 0: temp = n % -2 result.append(-temp) n //= -2 if temp: # 나머지가 0이 아니라면 n += 1 for r in reversed(result): print(r, end="") 예제 입력처럼 -13이 들어왔다고 생각해보자 REFERENCE https://suri78.tistory.com/119 [백준알고리즘] 2089번: -2진수 -Python [백준알고리즘] 2089번: -2진수 -Python http..

[Python] 백준 1107 리모컨 | EOFError | 브루트포스 알고리즘

~골드5~ EOFError가 떠서 해당 문제를 풀지 못했는데, 다음 댓글을 보고 해결할 수 있었다..! 같은 오류로 고생하시는 분은 참고 하셔요~ [최종 코드] target = int(input()) brokenButtonCount = int(input()) if brokenButtonCount == 0: # 고장난 버튼이 없는 경우 print(min(abs(100 - target), len(str(target)))) # 100에서 +/- vs target 버튼 누르기 else: brokenButton = list(map(int, input().split())) minN = abs(100 - target) # +/- 만 사용하여 이동한 경우 for num in range(1000001): # 채널 제한은..

[Python] 백준 16924 십자가 찾기 | 완전 탐색 | 브루트포스(Brute-force)

~실버 2~ https://www.acmicpc.net/problem/16924 16924번: 십자가 찾기 십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크 www.acmicpc.net [구현 포인트] 더보기 1. 제공된 입력 외 십자가 발견시 '*'을 '.'으로 변경할 공간 deepcopy 2. 완전탐색하며 '*' 발견시 인덱스를 넓혀 십자 모양 확인 3. 2를 십자 모양일 때까지 반복 - 반복마다 사이즈 += 1 - 리스트형 변수에 (i, j, size) 추가 - 십자 모양에 대해 '.' 처리 4. 완전탐색 후 십자모양으로 '.'처리한 공간에 '*'가 있..