본문 바로가기

분류 전체보기

 (116)
[BOJ][Python] 백준 17403번 - 가장 높고 넓은 성 문제 링크: https://www.acmicpc.net/problem/17403 17403번: 가장 높고 넓은 성 첫 번째 줄에 n개의 정수 x1, x2, ..., xn을 공백으로 구분하여 출력한다. xi는 i 번째 표지판이 사용되었을 경우 사용된 층수이며, 사용되지 않았으면 0이다. www.acmicpc.net 문제 풀이 볼록 껍질 문제이고, 감옥 건설(2254번) 문제에서 볼록 껍질을 계속 만들고 점 없애는 로직은 같다. 단지, 그 볼록 껍질이 몇 층인지 표기해야 하는데 점을 입력받을 때 인덱스도 같이 받으면 문제없이 해결 가능하다. 볼록 껍질을 계속 만들 때 반복문이 끝나는 경우는 2가지가 있다. 1. 볼록 껍질을 만들기 위한 점이 2개 이하이다. 2. 볼록 껍질을 만드는 과정이 끝났는데 볼록 껍질..
[BOJ][Text] 백준 20095번 - Sudoku 2 문제 링크: https://www.acmicpc.net/problem/20095 20095번: Sudoku 2 Fereydun, the legendary Persian hero whose prophecy was to overcome Zahhak, believes that he needs a powerful mind together with a powerful body. He has just learned a new brain teaser, called Sudoku, from a Japanese trader. Sudoku is played on a board t www.acmicpc.net 문제 풀이 이번에는 3*3 스도쿠이다. 이 역시 자필로 풀었으며, 코딩으로 답을 찾으려면 백트래킹으로 풀 수 있고, ..
[BOJ][Text] 백준 20094번 - Sudoku 1 문제 링크: https://www.acmicpc.net/problem/20094 20094번: Sudoku 1 Fereydun, the legendary Persian hero whose prophecy was to overcome Zahhak, believes that he needs a powerful mind together with a powerful body. He has just learned a new brain teaser, called Sudoku, from a Japanese trader. Sudoku is played on a board t www.acmicpc.net 문제 풀이 스도쿠를 푸는 문제. 2*2 스도쿠라 어렵진 않다. 입력으로는 밑의 사진 딱 1개만 나온다. 빈칸은 정확히..
[BOJ][Python] 백준 2623번 - 음악프로그램 문제 링크: https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 풀이 위상 정렬 기본 문제이다. 위상 정렬로 처리해서 결과 리스트의 길이가 n보다 작은 경우 0을 출력하고 n인 경우 하나씩 출력하면 된다. 코드
[BOJ][Python] 백준 1987번 - 알파벳 문제 링크: https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 풀이 처음에 BFS로 풀려다가 안되겠다 싶어서 DFS로 변경했다. 어짜피 BFS로 풀진 못한다. 원래는 DFS를 재귀로 돌려서 풀려했지만 시간 초과가 나서 재귀를 최대한 적게 하는 방향으로 갔다. 먼저 4방향으로 갈 x, y의 좌표를 만들어주고, 알파벳이 중복되는지 알기 위해 set()을 썼다. in을 써도 O(1)이라서 시간 단축에 도움이 된다. 반복문을 돌려서 4방향으..
[BOJ][Python] 백준 15965번 - K번째 소수 문제 링크: https://www.acmicpc.net/problem/15965 15965번: K번째 소수 자연수 K가 주어진다.(1 ≤ K ≤ 500,000) www.acmicpc.net 문제 풀이 에라토스테네스의 체를 이용하여 문제를 풀었다. 500,000번째 소수까지 구해야해서 한 4백만 쯤 잡았는데도, 런타임 에러가 떴다(indexError). 혹여나 8백만까지 올려봤는데 답은 맞았지만 시간이 너무 오바긴하다. 딱히 질 좋은 문제는 아닌거 같다. 에라토스테네스의 체를 이용하여 소수를 찾아주고 반복문을 이용하여 K번째 소수가 나올때 까지 반복문을 돌려준다. 코드
[BOJ][Python] 백준 2056번 - 작업 문제 링크: https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 문제 풀이 위상 정렬에 다이나믹 프로그래밍을 이용하는 문제이다. 사실상 웰노운 문제인 1005번의 아이디어를 가져왔다. 상관 관계가 있는 작업의 시간을 가져와 max()로 최댓값을 갱신해줘야 한다. 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 하기 때문이다. dp 테이블을 만들어서 가장 시간이 오래 걸린 것을 출력하면 된다. 이 역시도 max()를 이용하면 된다. 물론 ..
[BOJ][Python] 백준 1766번 - 문제집 문제 링크: https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 풀이 위상 정렬을 이용하는 문제에 우선순위 큐가 들어가는 문제이다. 기본적인 위상 정렬에 큐가 아닌 우선순위 큐를 써야하는 거 빼고는 차이점이 없다. 코드

티스토리툴바