본문 바로가기

알고리즘135

[Python] 소프티어 : 징검다리 https://softeer.ai/practice/info.do?idx=1&eid=390 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💡 문제 풀이 기본적인 DP 문제이다. 이번 DP 리스트에서는 i번째 징검다리까지의 최댓값을 넣어주면 된다. 따라서, 이번 징검다리를 건널 때 현재 값과 이전 값에서 1 추가한 값과 비교해 주면 된다. ✔️ 느낀 점 기본적인 DP 문제이다! 문제 설명이 딱히 친절하지 않아서 어떻게 할까 고민하다가 쓱 풀었는데 맞았다. 💻 코드 import sys ; input = sys.stdin.readline n = int(input()) stones = list(map(int, input().split())) DP = [1] * n for i .. 2023. 3. 5.
[Python] 백준 1005번 : ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 💡 문제 풀이 동적 프로그래밍과 위상정렬을 합친 문제이다. 위상정렬을 통해서 해당 노드까지 가는 길을 파악하고 DP로 최적화한다. 이해를 위해서 문제에서 제공된 첫 예제로 이해해 보자. 1부터 4까지 가기 위해서는 1 → 2, 3 → 4로 가야 한다. DP[i]에서 저장되는 값은 정점 i까지 도달했을 때의 최댓값이다. 4로 가는 길은 2가지이지만, 각 경로에 대한 비용을 따져서 최댓값으로만 .. 2023. 3. 3.
TIL : 위상정렬 알고리즘 (21) 💻 알고리즘 📌 위상정렬 알고리즘 Cycle이 없는 방향 그래프에서 작업 순서를 구하는 알고리즘이다. 이전에 공부한 적 있으나 기록을 남겨두지 않아서 남겨두려고 한다. 💡 특징 순환하지 않는 방향 그래프에서만 가능하다. 진입 차수 (in-degree) 또는 진출 차수 (out-degree)를 이용한다. 여러 개의 답이 존재할 수 있다 O(V+E)의 시간 복잡도를 가진다. 💡 동작 원리 (진입차수 ver) 진입 차수가 0인 정점을 큐에 넣는다. 큐에서 원소를 꺼내 연결된 간선을 제거한다. 진입 차수가 0이라면 해당 정점을 큐에 삽입한다. 마지막에 Cycle의 존재 유무를 확인한다. 결과의 크기가 정점의 개수보다 작다면 Cycle이 존재하는 것이다. from collections import deque de.. 2023. 3. 3.
[Python] 백준 14499번 : 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 💡 문제 풀이 기본적인 구현 문제이다. 요구사항에 맞게만 구현하면 된다. ✔️ 느낀 점 최적의 코드를 짜고 싶었다. 하지만 알고리즘은 시간과의 싸움 아닐까..? 그냥 구현하는 게 맞는지 잘 모르겠단 고민이 들었다. 💻 코드 import sys ; input = sys.stdin.readline UP, DOWN, LEFT, RIGHT.. 2023. 3. 2.
[Python] 백준 25341번 : 인공 신경망 https://www.acmicpc.net/problem/25341 25341번: 인공 신경망 첫째 줄에 입력층의 입력 크기 $N$, 은닉층의 인공 신경 개수 $M$, 출력값을 계산해야 하는 횟수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq N,M,Q \leq 2\,000)$ 둘째 줄부터 $M$번째 줄에 걸쳐 은닉층의 www.acmicpc.net 💡 문제 풀이 수학 문제이다. 주어진 조건대로 구현하면 무조건 시간초과가 발생한다. 따라서 연산회수를 줄어야 할 필요가 있다. 결합법칙을 생각해서 구현하면 쉽게 풀 수 있다. ✔️ 느낀 점 그대로 구현하면 시간 초과가 발생해서 조금 손을 봐줘야한다. 이걸 보면서 약간의 DP의 느낌이 났다..! 💻 코드 import sys ; input = sys.std.. 2023. 3. 1.
[Python] 백준 15686번 : 치킨 배달 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 💡 문제 풀이 기본적인 구현, DFS 문제이다. ✔️ 느낀 점 💻 코드 import sys from itertools import combinations input = sys.stdin.readline N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] chick.. 2023. 2. 27.

티스토리툴바