본문 바로가기

개발/algorithm

[백준 1005번] ACM Craft - python 문제 링크 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 - 위상 정렬과 dp 사용해서 풀이 - data[] : 인덱스 별 건설하는데 걸리는 시간으로 초기화하고 건설까지 소요되는 최소 시간 저장 - indegree[] : 인덱스 별 진입 차수 저장 - graph[] : 건물 짓는 순서 규칙 저장 - max_t[] : 해당 건물로 들어오는 바로 이전 건물들의 최대 건설 소요 시간 from collections import deque .. 더보기
[백준 9470번] Strahler 순서 - python 문제 링크 https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 풀이 위상 정렬 응용 오랜만에 위상정렬.. 다 까먹었구나 위상 정렬 이란 ? 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 순서가 정해져 있는 일련의 작업을 차례대로 수행햐아 할 때 사용할 수 있는 알고리즘 from collections import deque def topology_sort(): q = deque() # 들어오는 최대 레벨, 최대 레벨의 .. 더보기
[백준 16197번] 두 동전 - python 문제 링크 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 풀이 - bfs로 풀이 동전 두 개의 각 방문 표시 배열을 만들어서 표시해주면서 풀었는데 42% 에서 자꾸 틀렸다고. .. from collections import deque import sys input= sys.stdin.readline dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] def bfs(x1,y1, x2, y2): q = deque() q.appe.. 더보기
[프로그래머스][level3] 기둥과 보 설치 - python 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr 풀이 - 구현 문제 - 문제에 제시된 조건대로 구현해주면 된다. - 문제.. 더보기
[프로그래머스][level3] 길 찾기 게임 - python 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 풀이 - 다른 블로그 참고 1. nodes 배열에 노드의 위치, 노드 번호 저장 2. nodes를 y 좌표는 내림차순, x 좌표는 오름차순 정렬 - y 좌표가 가장 큰 것이 루트 노드, 그리고 차례대로 y좌표따라 내려가면서 왼쪽부터 x 좌표 기준으로 이진 노드로 채우면 됨 3. preorder 실행 - 중심이 될 루트 노드 기준으로 x 좌표 값 비교해서.. 더보기
[백준 12015번] 가장 긴 증가하는 부분 수열2 - python 문제 링크 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 - 최장 증가 수열(LIS) 문제 : 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열 https://zzion2.tistory.com/81 [백준 11053번] 가장 긴 증가하는 부분 수열 - python 문제 링크 https://www.acmicpc.net/problem/11053 110.. 더보기
[프로그래머스][level3] 퍼즐 조각 채우기 - python 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 퍼즐 조각 채우기 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 풀이 1. 퍼즐 별 모양 구하기 - find_puzzle 함수 : bfs로 퍼즐 모양 구하기 - trans_puz 함수 .. 더보기
[백준 2294번] 동전2 - python 문제 링크 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 - 냅색 알고리즘과 비슷한 듯하다. - dp[i] : i 금액을 만들 때 필요한 최소 동전 개수 - 동전마다 동전 금액만큼 빼고 해당 동전을 하나 추가했을 때와 비교 - 냅색 알고리즘 참고 https://zzion2.tistory.com/97 [백준 12865번] 평범한 배낭 -python 문제 링크 https://www.acmicpc.net/prob.. 더보기

티스토리툴바