[백준] Python,Java로 풀기📖
백준 19941(햄버거 분배 ) - Python(파이썬) - 그리디
백준 19941(햄버거 분배 ) - Python(파이썬) - 그리디
2022.06.0319941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 예제 설명 20 1 HHPHPPHHPPHPPPHPHPHP 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 H H P H P P H H P P H P P P H P H P H P 1. 2번의 사람 -> 1번 or 3번의 햄버거를 먹을 수 있지만 무조건 앞에 남은 햄버거 먹기 -> visted[1] =T visted ( 먹었는지 안 먹었는지 알려주는 배열 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..
백준 2448(별 찍기) - Python(파이썬) - 재귀
백준 2448(별 찍기) - Python(파이썬) - 재귀
2022.06.032448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 문제 설명 내가 처음 생각한 풀이는 이와 같다 위와 같이 삼각혁의 꼭짓점의 좌표를 (startX,startY,높이) 라고 가정해본다. N=12 일 때의 삼각형은 연두색과 같이 세개로 나누어진다. ( 0, 0 6 ) , ( -6, 6, 6 ) ,( 6, 6, 6 )으로 이렇게 세개가 나누어진다. 이걸 처음 시작점 ( 0, 0, 12) 점이랑 연관되어서 생각해보면 ( 0, 0, 6 ), ( 0-6, 0+6, 6 ), ( 0+6, 0+6, 6) 이라고 할 수 있다. 또 N = 6일 때의 값을 각각 세개의 삼각형으로 나눌..
백준 14494(다이나믹이 뭐에요?) - Python(파이썬) - 다이나믹
백준 14494(다이나믹이 뭐에요?) - Python(파이썬) - 다이나믹
2022.06.02문제 설명 이런 원리로 (2,1)의 점 1, (3,1)의 점 1, (2,2)의 점 3이 세점을 더해서 5가 만들어지는 것이다. 즉 , 5 (3,2) = 1(2,1) + 1(3,1) + 3(2,2) 이걸 dp 그래프안에 넣었다고 가정해서 점화식으로 풀면 dp[m][n] = dp[m-1][n-1]+dp[m-1][n] + dp[m][n-1] 풀이 방법 ① m=1, n = 1인 지점은 모두 1이다. 갈 수 있는 방법은 무조건 일이다 1 1 1 1 1 1 1 ② 따라서 m의 값이 증가에 따라 for문 해서 1부터 n까지 루프문 돌린다. ③ 단, 수가 커지기 때문에 array값을 구할 때 마다 1,000,000,007 나눈 나머지 값을 구한다. Python(파이썬) import sys n,m = map(int,sy..
백준 1927(최소 힙) - Python(파이썬) - 자료구조
백준 1927(최소 힙) - Python(파이썬) - 자료구조
2022.06.01예제 설명 왼쪽 그림은 0,12645678,1,2 이 입력 | 오른쪽 그림은 0,0,0,0,32 이 입력되었을 때 힙안 숫자와 출력 되는 구조 Python(파이썬) import sys import heapq #연산의 개수 n = int(sys.stdin.readline()) heap=[] for i in range(n): #자연수 x 입력 받기 x=int(sys.stdin.readline()) #x가 0이 아닌 경우 if x!=0: #힙에 x를 입력 넣기 heapq.heappush(heap,x) #x가 0인 경우 else: #힙에 아무것도 없는 경우 if len(heap)!=0: #힙에서 가장 작은 값 출력 print(heapq.heappop(heap)) #힙에 값이 있는 경우 else: print(0)..
백준 24479(깊이 우선 탐색 1) - Python(파이썬),Java(자바) - DFS
백준 24479(깊이 우선 탐색 1) - Python(파이썬),Java(자바) - DFS
2022.06.01예제 문제 설명 1. 1번 노드를 처음 시작하므로 첫번째 방문으로 visted 되었다고 표현하기 위해서 visted[1] 1로 바꿈 2. 1번 노드와 연결된 2번, 4번 중에 2번 노드가 더 작으므로 2번 노드 방문 -> 2번 노드 2번째로 방문하였으므로 visted[2] 2로 변경 3. 2번 노드와 연결된 1번,3번,4번 중 방문하지 않은 노드 중에 작은 값인 3번 노드 방문 -> 3번 노드 3번째로 방문하였으므로 visted[3] 3으로 변경 4. 4번 노드와 연결된 1번,3번,4번 노드 중 방문하지 않은 노드들이 없다.끝 그러면 5번 노드는 시작 노드 1번으로부터 방문하지 못하는 노드이므로 0으로 그냥 명시 ( 조건에서 방문 못하는 노드는 0이라고 명시하라고 하였으므로) 결론: 출력은 visted에..
백준 1296(팀 이름 정하기 ) - Python(파이썬) - 문자열
백준 1296(팀 이름 정하기 ) - Python(파이썬) - 문자열
2022.06.011296번: 팀 이름 정하기 연두는 프로그래밍 대회에 나갈 팀 이름을 정하려고 한다. 미신을 믿는 연두는 이환이에게 공식을 하나 받아왔고, 이 공식을 이용해 우승할 확률이 가장 높은 팀 이름을 찾으려고 한다. 이환 www.acmicpc.net 문제 이해 예제 1번 LOVE = 연두의 영어 이름 ( L :1개, O:1개, V:1개, E:1개 ) 팀 이름 JACOB =( L: 0개, O:1개, V:0개, E:0개) => L : 1, O: 2, V:1, E:1 => 우승 확률 : (3 x 2 x 2 x 3 x 3 x 2)%100 =216%100 = 16 FRANK = ( L:0개, O: 0개, V:0개, E:0개) => L: 1, O:1, V: 1, E:1 => 우승 확률 : (2 x 2 x 2 x 2 x 2..
백준 11279(최대 힙) - Python(파이썬) - 자료구조
백준 11279(최대 힙) - Python(파이썬) - 자료구조
2022.05.3111279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 파이썬 : 최소 힙 구조, 자바 : 최소 힙 구조, C++: 최대 힙 구조를 이용 파이썬 힙 구조에 대한 설명 참고) 최단 경로 알고리즘 - 다익스트라 최단 경로 알고리즘 최단 경로 알고리즘(Shortest Path) : 가장 짧은 경로를 찾는 알고리즘 1) 최단 경로 문제- 지점( 노드 ), 지점 간 연결된 도로( 간선 ) - 한 지점에서 다른 한 지점까지의 최단 경로를 구해야 하는 경우 coooco.tistory.com import sys ..
백준 2343(기타 레슨) - Python(파이썬) - 이분탐색
백준 2343(기타 레슨) - Python(파이썬) - 이분탐색
2022.05.312343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 접근 조건 : 블루레이를 묶을 때는 같은 블루레이 사이에 다른 블루레이가 들어올 수 없으므로 연속되게 묶어야한다. ex ] 1번, 3번 같은 블루레이 -> 2번 같은 블루레이 ① 블루레이의 크기가 15라고 할 경우 강의의 합이 15보다 작거나 같게 묶여야하므로 1번 블루레이에는 (1,2,3,4,5), 2번 블루레이에는 ( 6,7 ) 3번 블루레이에는 (8) 4번 블루레이에는 (9) 이런식으로 묶이게 된다. 그렇게 되면 블루레이의 개수가 4개이므로 조건 3개보다 크..
백준 2096(내려가기) - Python(파이썬) - 다이나믹 프로그래밍,메모리 초과
백준 2096(내려가기) - Python(파이썬) - 다이나믹 프로그래밍,메모리 초과
2022.05.302096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net ※ 이 문제의 경우 메모리 초과를 조심해야한다. 배열을 막 선언할 경우 메모리 초과가 날 수 있다 ※ 또, 파이썬의 경우 =으로 복사할 경우 같은 곳을 참조하여서 문제가 될 수 있다. 따라서 copy()를 이용하여서 복사한다. 풀이방법 ① dp_max,dp_min을 선언하는데 이때 첫째줄 한줄만 입력 받는다. ② for문으로 그 담줄부터 입력받으므로 1부터 N전까지 입력받아서 a,b,c로 입력받는다. ③ 앞에 있었던 dp_max의 0번째 항에는 dp_max의 0번째항과 1번째..
백준 2502(떡 먹는 호랑이) - Python(파이썬) - 다이나믹프로그래밍
백준 2502(떡 먹는 호랑이) - Python(파이썬) - 다이나믹프로그래밍
2022.05.302502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 접근방법 일단 1, 2, 3, 5 이런식으로 증가하기 때문에 피보나치 수열인 것을 안다. 이걸 문자로 표현하여서 첫째와 둘째를 A와 B라고 가정하면 밑의 표와 같이 증가한다. 1 2 3 4 5 6 7 A B A+B A+2B 2A+3B 3A+5B 5A+8B 이걸 A의 계수 관점, B의 계수 관점으로 분리하면 A의 계수 관점(dpA) 1 2 3 4 5 6 7 1 0 1 1 2 3 5 B의 계수 관점(dpB) 1 2 3 4 5 6 7 0 1 1 2 3 5 8..
백준 2293(동전 1) - Python(파이썬) - 다이나믹
백준 2293(동전 1) - Python(파이썬) - 다이나믹
2022.05.292293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이방법 ① dp[i] : i를 만들 수 있는 경우의 수라고 가정 ② 처음부터 n가지 종류의 동전을 하는 것이 아니라 한개부터 n가지의 종류의 동전으로 늘려간다. ③ 동전의 종류를 늘려갈 때 0원부터 시작해서 k원까지 만들 수 있는 경우의 수를 구한다. 점화식 : dp[j ] = dp[j] +dp[j-i] ex ] [ 1 ]로 만들 수 있는 경우의 수는 0원부터 k원까지 1가지 일 것이다. [ 1,2 ]로 만들 수 있는 경우의 수를 구할 때 6원일 때의 값을 구한..
백준 1309(동물원) - Python(파이썬),Java(자바) - 다이나믹
백준 1309(동물원) - Python(파이썬),Java(자바) - 다이나믹
2022.05.281309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net dp[ i ] : i번째에 사자가 있는 경우의 가지 수 array[ i ] : 2*i 배열에서 사자의 경우의 수 ex ] i= 4인 경우 -> 4번째에 사자가 있는 경우의 가지 수를 의미 ① 3( 4-1 ) 번째에 사자가 있는 경우 ( dp[3] ) -> 밑에 그림고 같이 4번째에 사자의 자리는 무조건 정해질 수 밖에 없다 => 경우의 수 : dp[3] * 1 ( 사자 자리 지정 되므로 ) i=1 i=2 i=3 i=4 O O i=1 i=2 i=3 i=4 O O ② 3번째에 사자가 없는 경우의 수 ( array[ 2] : 2*2 배열에서 사자의 경우의 수를 의미 ) -> 이 경우에는 3번째에 사자..