본문 바로가기

전체 글

 (48)
python 백준1010 다리 놓기(BOJ1010) 문제링크 : https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 이문제는 조합 공식을 사용하면 바로 풀수있다 이런 문제들은 식만 뽑아낸다면 참 쉬운데 문제는 점화식을 못뽑아내면 손도 못대겠다는것.. 쨌든 이 문제는 처음에 math라이브러리를 써서 풀었었는데 그랬더니 메모리를 좀 잡아먹는것같아서 팩토리얼을 따로 정의해서 풀었다 import sys input = sys.stdin.readline #팩토리얼 def factorial(num): resul..
python 백준2748 피보나치 수 2(BOJ2748) 문제링크 : https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net for문에 별찍기가 있다면 dp에는 피보나치가 있다!@! 정말 가장 기본적인 구조인데 이 구조를 다른문제에도 적용하는게 어렵다.. 점화식을 구하고 어디까지 초기값으로 잡고 어느구간에서부터 반복문으로 돌릴지를 파악하는게 핵심인것같다 알면 뭐하나.. 잘 안되는걸ㅜㅜ import sys input = sys.stdin.readline #메모이제이션dp테이..
python 백준2775 부녀회장이 될테야(BOJ2775) 문제링크 : https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 간단한 dp문제인데 시간제한 1초에 층수 호수도 14층뿐이라 O(n^3)= 14세제곱 이어도 충분하길래 그냥 인원수 싹 다 구하고나서 결과값 출력했다. 인원수를 구하면서 한방에 리턴하는 방법으로도 할수있을것이다 내가 제출 한 코드 import sys input = sys.stdin.readline #테스트 케이스 t = int(input()) #층수 리스트 k_list = [] #호수 리스트 n_list = [] #입력 fo..
python 백준11000 강의실 배정(BOJ11000) 문제링크 : https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 이해하는건 쉬운데 오히려 이런 문제들이 풀기가 더 어려운것같다.. 처음엔 재귀방법으로, 그리고 2중for문 방법으로 풀었는데 전부 시간초과가 나왔다 문제를 다시 보면 건수는 200,000건인데 이걸 시간제한 1초만에 풀려면 최소 O(NlogN) 시간복잡도로 풀어야된다. 그래서 2중for문으로 풀면 당연히 시간초과.. 전에 정렬 글에서 썼듯이 연산속도는 초당 1억건 정도이기때문에 2중for문은 200000^2 = 400억이라서 ..
python 백준15686 치킨 배달(BOJ15686) 문제링크 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 처음에 문제읽다가 이게 뭐말이래..했는데 생각보다 할만했다 한방에 통과! from itertools import combinations import sys input = sys.stdin.readline #도시사이즈n , 고를 치킨집 개수m n, m = map(int, input().split()) input_map = [] zip = [] chicken = []..
python 백준9095 1, 2, 3 더하기(BOJ9095 ) 문제링크 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이건 내가 알고리즘 유형에서 DP눌러서 나온 문제라서 DP로 풀었다 문제에서 점화식을 도출한다음 리스트에 초기값을 저장해둔다 그리고 반복문을 통해서 점화식을 통해 리스트 값을 불러와서 새롭게 추가하는 형태로풀었다(메모이제이션) 이렇게 하면 재귀로 호출할때와 달리 한번 계산한 값을 또 다시 계산하지 않아도 되기때문에 좋타 아직 DP문제를 많이 풀어보질못해서 메모이제이션기법 말고는 해본게 읎다.. 이거 보는 사람은 아마 풀다가 막혀서 보는사람일텐데 여기까지만 읽고 다시한번 고민해보는거 ..
python 백준14502 연구소(BOJ14502) 문제링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 이문제는 아이디어 떠올리는 데만 2시간이 걸린것같다..아이디어를 떠올리는게 정말 어려웠다 혹시나 아이디어만 얻기위한 사람이 있을수 있어서 내가 풀었던 아이디어만 먼저 공유한다 문제해결 아이디어 1) 연구소 지도에서 벽 3개를 세운다 2) 벽을 세운 지도로 바이러스 확산 시뮬레이션을 해본다 3) 시뮬레이션 후 빈공간 갯수를 비교해본다 4) 1~3번 과정을 모든 경우의 수 만큼 반복 아래 코드도 처음..
python 백준2667 단지번호붙이기(BOJ2667) 문제링크 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net dfs를 공부하면서 나왔던 예시문제와 비슷하다 상하좌우를 dx, dy로 해서 풀면 쪼금 더 짧게도 가능할것같다 #지도크기 n = int(input()) #단지 집 수가 담길 리스트 house_count = [] #입력으로 받는 지도 리스트 input_map = [] for _ in range(n): #지도에 추가 input_map.append(list(map(int, input())))..

티스토리툴바