[Python/파이썬] 백준 13305번 - 주유소

문제 설명 입출력 예제 풀이 코드 왼쪽에서 제일 오른쪽 도시로 이동하는 최소의 비용을 구하기 위해서는 가장 싼 주유소에서 기름을 넣는 것이 이득이다. 먼저 왼쪽에서 출발할 때는 기름이 없기 때문에 시작지점에서 먼저 기름을 넣고 시작하는데 가장 값이 싼 주유소를 찾기 위해 첫 번 째 주유소를 가장 값이 싼 주유소로 저장해 놓은 뒤 반복문을 통해 저장한 주유소와 현재 위치의 주유소의 기름 값을 비교해 가장 값이 싼 주유소를 갱신해서 기름을 넣으면 된다. 정답 코드 import sys input = sys.stdin.readline n = int(input()) distances = list(map(int, input().split())) oilCosts = list(map(int, input().split(..

• format_list_bulleted ◼ 코딩테스트/그리디 (Greedy)
• · 2023. 7. 8.
• textsms

[Python/파이썬] 백준 1600번 - 말이 되고픈 원숭이

문제 설명 입출력 예제 풀이 코드 이 문제는 2차원 배열이 아닌 3차원 배열 방식으로 풀어야 한다. 내가 3차원 배열로 표현한 방식은 visited[행][열][말처럼 움직일 수 있는 남은수(K)] 이다. 최소한의 동작으로 도착지점에 도착하기 위해서는 k번 말 처럼 움직인 다음 원숭이처럼 움직여야 최소한의 동작으로 도착 가능하다. 정답 코드 from collections import deque import sys input = sys.stdin.readline K = int(input()) W, H = map(int, input().split()) # 열, 행 board = [list(map(int, input().split())) for _ in range(H)] # 말처럼 이동하는 경우 dx_knigh..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 7. 7.
• textsms

[Python/파이썬] 백준 9663번 - N-Queen

문제 설명 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 코드 이 문제는 가능한 모든 경로를 탐색하되, 조건을 만족하지 않는 경로는 중간에 가지치기하여 더 이상 탐색하지 않는 백트래킹 알고리즘을 사용하여 풀 수 있었다. 문제에 대해 설명하자면, 체스에서 퀸은 상하좌우 대각선 모든 방향으로 원하는 만큼 이동할 수 있다. 그렇기 때문에 퀸을 서로 공격할 수 없도록 놓기 위해서는 체스판위의 행, 열 마다 하나의 퀸이 존재해야한다. 처음에는 2차원 배열로 푸는 방법이 더 이해가 쉬울것 같아서 2차원 배열로 문제를 풀고 제출해..

• format_list_bulleted ◼ 코딩테스트/완전탐색 (Bruteforce)
• · 2023. 7. 6.
• textsms

[Python/파이썬] 백준 2638번 - 치즈

문제 설명 입력과 출력 및 예제 풀이 코드 2차원 배열의 값들을 하나씩 탐색해 해당 부분이 외부 공기와 2번 이상 접촉했는지 확인해야 하므로 BFS를 이용해 문제를 풀 수 있다. 내 코드에서 주의할점으로는 치즈가 있는 부분은 visited 방문 처리 하지 않았다는 점인데 여러 면에서 공기와 접촉이 될 수 도 있기 때문에 이 부분을 방문 처리 해버리게 되면 해당 치즈는 무조건 한 면만 접촉되는 것이 되기 때문이다. 나머지 부분은 주석을 통해 이해할 수 있을 것으로 생각되어 자세한 설명은 생략한다. 정답 코드 from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) cheeze = [l..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 7. 4.
• textsms

[Python/파이썬] 백준 1541 - 잃어버린 괄호

문제 설명 입출력 예제 풀이 코드 그리디 알고리즘 문제로 괄호를 적절히 합쳐서 최소 값이 나올 수 있게 하는 방법만 알면 쉽게 해결할 수 있다. 해당 방법는 모든 + 식들만 먼저 더하고 나중에 구한 값들을 첫 번째 값에서 부터 빼는 방식이다. 이때, 첫 번째 값은 등호가 없으므로 따로 저장하여 처리한다. 만약 10 - 20 + 30 - 60 + 20 - 40 이 주어졌다고 가정해보자. 가장 최소 값이 나올 수 있도록 덧셈 식들만 괄호를 적용하면 다음과 같다. (10) - (20 + 30) - (60 + 20) - (40) 이 식대로 계산을 하면 정답은 10 - 50 - 80 - 40 = -160이 된다. 정답 코드 import sys input = sys.stdin.readline arr = input(..

• format_list_bulleted ◼ 코딩테스트/그리디 (Greedy)
• · 2023. 6. 29.
• textsms

[Python/파이썬] 백준 1931 - 회의실 배정

문제 설명 입출력 예제 풀이 코드 가장 많은 회의의 수를 알기 위해서는 빨리 끝나는 회의 순서대로 정렬을 해야 한다. 앞의 일이 종료되어야 뒤의 일도 진행할 수 있는 것과 마찬가지로 회의가 빨리 끝날수록 뒤에서 더 많은 회의가 가능하다. 정렬을 하는데 끝나는 시간이 오름차순으로 정렬되었을 경우 시작시간은 같지만 끝나는 시간이 같은 회의가 생길 수가 있다. 이 경우를 대비하여 첫 번째로 끝나는 시간 기준 오름차순, 두 번째로 시작하는 시간 기준 오름차순 으로 총 2번의 정렬이 필요하다. 위의 정렬을 해주기 위해서는 위 순서대로 sort를 하는것이 아니라 반대로 해야한다. 즉, 시작시간의 오름차순으로 정렬을 한 뒤, 정렬된 리스트를 다시 끝나는 시간으로 오름차순 정렬해주는 것이다. 이미 시작시간이 오름차순으..

• format_list_bulleted ◼ 코딩테스트/그리디 (Greedy)
• · 2023. 6. 28.
• textsms