알고리즘/백준
-
[백준 / Python] 2309번 일곱 난쟁이 | 초코더알고리즘/백준 2020. 8. 23. 18:50
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제 9명의 난쟁이 키를 입력받아 합이 100이되는 7명의 난쟁이 출력하기 풀이 combination(조합)을 이용해서 쉽게 풀었습니다. 전체코드 from itertools import combinations high=[] for i in range(9): high.append(int(input().strip())) high=sorted(high) for i in combinations(high,7): i..
-
[백준 / Python] 3055번 탈출 | 초코더알고리즘/백준 2020. 8. 22. 01:10
https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치�� www.acmicpc.net 문제 .(빈곳) *(물) X(돌) D(비버굴) S(고슴도치) 가 주어지고 고슴도치가 비버굴로 이동하기까지 걸리는 최소시간을 구하는것. 단, 물에 잠기면 이동할 수 없고, 돌이 있는 곳으로도 이동할 수 없다. 풀이 1. 물, 고슴도치가 있는 위치를 queue에 담는다. - 여기서 주의해야할점은 물은 append(), 고슴도치는 appendleft()를 해주어야합니다! 예시로 2 2 가 들어오면 답은 '1'이..
-
[백준 / Python] 16956번 늑대와 양 | 초코더알고리즘/백준 2020. 8. 18. 20:48
https://www.acmicpc.net/problem/16956 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 � www.acmicpc.net 문제 rxc크기의 목장이 주어지고, 칸은 비어있거나 양(S)또는 늑대(W)가 있다. 늑대는 상하좌우로 움직일 수 있고 늑대가 양이 있는 칸으로 이동하지 못하게 울타리를 설치하라. 접근법 1. 모든 좌표를 탐색 1-1. 늑대(W)일경우, 상하좌우를 탐색하여 인접한곳에 양이 있으면 flag 변수를 True로 변경 1-2. 양(S)인경우, 넘어감 1-3. .(빈칸)인경우, 모두 울타리로 채워줌 ..
-
[백준 / Python] 16929번 Two Dots | 초코더알고리즘/백준 2020. 2. 12. 22:04
https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다. www.acmicpc.net 접근법 DFS로 탐색하면서 사이클이 있는지 확인했습니다. 사이클의 여부는 선분의 길이가 최소선분 길이인 4이상이면서 시작좌표와 끝좌표가 같으면 사이클이 있다고 하였습니다. DFS함수를 살펴보겠습니다. dfs(x,y,cnt,color,sx,sy) x,y는 현재좌표, cnt는 선분의길이, color는 점의색, sx,sy는 첫시작좌표입니다. 1. 범위가 넘어가는지 확인해줌 2...
-
[백준 / Python] 3019번 테트리스 | 초코더알고리즘/백준 2020. 2. 12. 14:32
https://www.acmicpc.net/problem/3019 3019번: 테트리스 문제 테트리스는 C열 필드위에서 플레이하는 유명한 게임이다. 필드의 행의 수는 무한하다. 한 번 움직일 때, 아래와 같은 일곱가지 블록 중 하나를 필드에 떨어뜨릴 수 있다. 블록을 떨어뜨리기 전에, 플레이어는 블록을 90, 180, 270도 회전시키거나 좌우로 움직일 수 있다. 이때, 블록이 필드를 벗어나지 않으면 된다. 블록을 필드의 바닥이나 이미 채워져있는 칸의 위에 놓여지게 된다. 창영이가 하고있는 테트리스는 일반적인 테트리스와 약간 규칙이 다르다. www.acmicpc.net 접근법 1. 각 블록마다 회전하여 필드에 떨어트렸을때, 딱 맞게 떨어지는 필드의 높이를 숫자로 표현해 보겠습니다 1번블록 ㅣ-> 한칸 넓..
-
[백준 / Python] 13913번 숨바꼭질 4 | 초코더알고리즘/백준 2020. 2. 6. 13:41
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net 접근법 숨바꼭질을 참고해주세요. 앞의 문제와 다른부분은 움직이는 경로를 저장해주어야 한다는 점입니다. path리스트에 이전의 좌표..
-
[백준 / Python] 1697번 숨바꼭질 | 초코더알고리즘/백준 2020. 2. 6. 13:37
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 접근법 기존의 bfs방식에서 이동할 수 있는 방법인 (x+1,x-1,x*2)에서 고려해주는것이 포인트입니다. 그리고 옮긴 좌표에 해당하는 ..
-
[백준 / Python] 10973번 이전 순열 | 초코더알고리즘/백준 2020. 2. 6. 13:32
https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 나의 풀이 n = int(input()) a = list(map(int, input().split())) def next_permutation(a): n=len(a)-1 i = n while i>0 and a[i-1]