분류 전체보기
-
[백준 1041] 주사위 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 30. 02:02
www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 문제풀이 N, arr : 입력값 ans : 보이는 5면 합의 최소값 min_lists : 1, 2, 3 면의 주사위의 최소값 개인적으로 굉장히 어려운 문제였다 ㅠㅠ.. 주사위와 같은 기하적인 문제 생각하는 것이 너무 어렵다... 만들어지는 완성체는 큐브 모양인데, 큐브에서 각각의 블록이 보일 수 있는 면은 1, 2, 3 개 중 하나이다. 면이 1개 보이는 블록 개수 : 4 * (N - 2..
-
[백준 15686] 치킨 배달 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 1. 30. 00:44
www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제풀이 N, M, board : 입력값 chicken : 치킨집 좌표 리스트 tmp_board : 치킨집이 없는 board (집과 빈 공간만 있는 2차원 리스트) dist : 치킨집을 기준으로 최단 이동 거리 Combination(조합) 으로 치킨집을 M개 선택하여 BFS를 통해 각 집까지의 거리를 탐색하는 방식으로 해결할 수 있다. 1. Combination을 통해 M개의 치킨집 선택하..
-
[백준 1263] 시간 관리 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 30. 00:37
www.acmicpc.net/problem/1263 1263번: 시간 관리 첫째 줄에 일의 수 N이 입력되고 다음 N(1≤N≤1,000)개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 Ti(1≤Ti≤1,000)와 Si(1≤Si≤1,000,000)가 입력된다. www.acmicpc.net 문제풀이 N : 입력값 arr : i번째 작업의 (완료시간, 작업이 걸리는 시간) 작업의 완료 시간을 기준으로 가장 늦게 완료해도 되는 작업부터 시작해서 다른 일들의 작업 시간을 탐색하면서 시작 시간을 갱신하는 그리디 알고리즘으로 해결할 수 있다. 1. 작업의 완료 시간을 기준으로 역순으로 정렬하기 2. 첫 번째 작업의 최대 시작 시간을 시작으로 나머지 작업들 확인하기 - i번째 일을 끝마쳐야 하는 시간이 현재 시간보..
-
[백준 1715] 카드 정렬하기 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 28. 00:36
www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제풀이 N : 입력값 hq : 우선순위 큐 우선순위 큐를 이용해 가장 적은 두 수를 빼가면서 정답(ans)에 더해주면 된다. 어렵지 않은 그리디 알고리즘 문제이다. 1. 우선순위 큐에 입력하기 2. hq의 크기가 1이 될때까지 hq 안의 가장 작은 두 수를 빼면서 ans에 더해준다. - 더한 수를 다시 hq에 넣어준다. 코드 import sys import heapq if __name__ == ..
-
[백준 3190] 뱀 (Python)Algorithm & Problem Solving/구현(Implementation) 2021. 1. 27. 22:44
www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제풀이 N, K, L : 입력값 command : 명령 d : 방향 time : 현재 시간 cmd_idx : command 리스트의 원소 탐색을 위한 인덱스 특별한 알고리즘 필요없이 단순히 주어진 조건대로 잘 구현(?) 하기만 하면 해결할 수 있는 문제이다. 한 가지 주의할 것이, 사과가 없는 빈 공간으로 뱀의 머리가 이동할때, 몸 길이가 변하지 않는 것이다. 이 부분만 주의하면 문제없이 해결할 수 있다. board..
-
[백준 1939] 중량제한 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 1. 27. 19:31
www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 문제풀이 N, M : 입력값 adj_list : 섬간 인접리스트 start, end : 공장이 위치한 섬의 번호 mx, mn : 이분 탐색 범위 BFS와 이분 탐색을 활용한 문제였다. 처음 접해보는 유형이었고, 새로운 방식의 아이디어 및 풀이를 얻을 수 있는 문제였다. 1. 이분 탐색을 통해 가능한 중량을 찾는다. - BFS 탐색을 통해 start 섬에서 end ..
-
[백준 2589] 보물섬 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 1. 25. 11:48
www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제풀이 N, M, board : 입력값 check : 특정 노드 방문 여부 dist : 특정 노드까지의 거리 q : BFS를 위한 deque 모든 육지에 대해서 BFS를 통해 갈 수 있는 최대 거리를 구해주면 쉽게 해결할 수 있다. 1. 특정 좌표가 육지라면 BFS 시작한다 - 해당 위치에서 상하좌우 중 육지이면서 아직 방문하지 않았다면 방문 2. 모든 육지에 대해 1의 과정을 반복한다 코드 import sys ..
-
[백준 1744] 수 묶기 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 1. 22. 23:08
www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제풀이 N, arr : 입력값 minus_cnt, plus_cnt, zero_cnt : 음수, 양수, 0 개수 그리디 알고리즘 문제인데, 극강의 하드코딩으로 해결하였다... 분명히 더 효율적인 방법이 많이 존재할 것이다. 예외 테스트케이스를 생각하면서 짜다보니 코드가 길어졌고, 결국 하드코딩이 되어버렸다...ㅠㅠ 1. 음수, 양수, 0 개수 세주기 2. 음수 계산하기 - 음수 개수가 짝수일 경우 짝지어서 곱..