[백준] Python,Java로 풀기📖
백준 1463(1로 만들기) - Python(파이썬) - 다이나믹
백준 1463(1로 만들기) - Python(파이썬) - 다이나믹
2022.06.291463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 예제 풀이 2-> dp[1]+1,dp[2//2]+1 -> min(1,1)=1 10 -> 3이 나오게 된다. dp[0] dp[1] dp[2] dp[3] dp[4] dp[5] dp[6] dp[7] dp[8] dp[9] dp[10] 0 0 (dp[1]+1,dp[2//2]+1) = (1,1) = 1 (dp[2]+1,dp[3//3]+1) = (2,1) = 1 (dp[3]+1,dp[4//2]+1) = (2,2) = 2 (dp[4]+1) = 2 (dp[5]+1,dp[6//2]+1,dp[6//3]+1) = (3,2,2) = 2 dp[6]+1 = 3 (dp[7)+1,dp[8//2]+1) = ..
백준 13565(침투) - Python(파이썬) - DFS
백준 13565(침투) - Python(파이썬) - DFS
2022.06.2713565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 예제 풀이 outer side 0⬇️ 1 0⬇️ 1 0⬇️ 1 0⬇️ 1 0➡️ 0➡️ 0⬇️ 0 0❌ 1 1 1 0❌ 1 1 0 0 0 1 1 0 0 1 0 1 1 inner side 이렇게 outer side에서 시작해서 inner side로 나가야하지만 중간에 전류가 통하지 않는 물질땜에 멈추게 된다. outer side 1 1 0 0 0⬇️ 1 1 1 0 1 1 0 0➡️ 0⬇️ 0 0 0 0 0 1 1 0⬇️ 0 1 1..
백준 10159(저울) - Python(파이썬),Java(자바) - 플로이드 워셜
백준 10159(저울) - Python(파이썬),Java(자바) - 플로이드 워셜
2022.06.2610159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 예제 풀이 그림으로 표현하면 이런식으로 표현 된다. 그럼 연결된 노드들을 표로 표현하면 이렇게 된다 이제 차례대로 1번노드부터 6번노드까지 경로노드로 거쳐서 간다고 할 때 표를 작성하면 1️⃣ 1번 노드가 경로노드인 경우 -> 없음 2️⃣ 2번 노드가 경로노드인 경우 -> 1번 노드에서 3번 노드로 가는 경우 D13 = (D12 + D23) =2로 변경 3️⃣ 3번 노드가 경로노드인 경우 -> 1번 노드에서 4번 노드로 가는 경우 D14 ..
백준 17451(평행 우주) - Python(파이썬) - 그리디 알고리즘
백준 17451(평행 우주) - Python(파이썬) - 그리디 알고리즘
2022.06.2617451번: 평행 우주 행성 1에 가기 위해 필요한 것보다 세 배의 속도로, 행성 2의 경우 두 배의 속도로 이동하면, 지구에서는 900의 속도만 쌓으면 된다. www.acmicpc.net 예제 풀이 연산은 마지막 행성부터 시작한다. - ( 속도의 최솟값을 구할 때 마지막 지구에 도착할 땐느 그 행성의 속도와 동일한 값이면 되기 때문 ) 마지막 행성부터 시작해서 1️⃣ 현재 속도( result )가 행성 이동시 필요한 최소 속도( vi )보다 작거나 같은 경우 ( result vi ) : (행성 이동시 필요한 최소 속도를 현재 속도로..
백준 1743(음식물 피하기) - Python(파이썬) - 수학
백준 1743(음식물 피하기) - Python(파이썬) - 수학
2022.06.241743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 예제 풀이 # : 음식물 위치 행\열 0 1 2 3 4 0 . . . . . 1 . # . . . 2 . . #(2) #(1) . 3 . #(4) #(3) . => 음식물의 크기는 인접하여 붙어서 있는 경우 크게 된다고 했으므로 가장 큰 음식물의 크기는 4 문제 풀이 ① for문으로 #(음식물이 있을 경우 ) bfs 함수 실행 ② 인접한 음식물이 있을 경우 && count하지 않았을 경우 -> cnt+1 ③ count 리..
백준 1495(기타리스트) - Python(파이썬),Java(자바) - 다이나믹 프로그래밍
백준 1495(기타리스트) - Python(파이썬),Java(자바) - 다이나믹 프로그래밍
2022.06.231495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 예제 풀이 1) 시작 볼륨(S)= 5일 바꿀 수 있는 볼륨 -> 0 , 10 => 5-v[0] = 0 or 5+v[0] = 10 0 1 2 3 4 5 6 7 8 9 10 1 1 2) 현재 볼륨이 0과 10인 경우 바꿀 수 있는 볼륨 -> 3 , 7 => 0-v[1] = -3(0보다 작으므로 X) or 0+v[1] = 3 or 10-v[1] = 7 or 10+v[1] = 13(최댓값 10보다 크므로 X) 0 1 2 3 4 5 ..
백준 1543(문서 검색) - Python(파이썬) - 문자열
백준 1543(문서 검색) - Python(파이썬) - 문자열
2022.06.231543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 예제 풀이 내가 생각한 풀이 1️⃣ for 루프로 ababababa 를 돌기 2️⃣ i = 0 -> aba 가 있음 -> num= 0+3 =3 대입 -> cnt값에 +1 하기 3️⃣ i = 2 -> aba가 있음 -> 3보다 작음 -> cnt값에 +1을 하지 않는다. 4️⃣ i = 4 -> aba가 있음 -> 3보다 큼 -> num = 4+3 = 7대입 -> cnt값에 +1 하기 5️⃣ i = 6 -> aba가 있음 -> 7보다 작음 -> cnt값에 +1을 하지 않는..
백준 1140(플로이드) -Python(파이썬) - 플로이드워셜 알고리즘
백준 1140(플로이드) -Python(파이썬) - 플로이드워셜 알고리즘
2022.06.2011404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 예제 풀이 시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있으므로 또 입력 받을 경우 최단 거리로 입력 받게 만든다. 그렇게 입력 받은 노드들을 출발 노드를 세로, 도착 노드를 가로로 표를 작성한다. 1 ) 1번 노드를 거처셔 표 작성 2) 2번 노드를 거쳐서 표 작성 3) 3번 노드를 거쳐서 표 작성 이런식으로 노드마다 경로노드라고 할 경우 표를 갱신해서 표현한다. 그렇게 되면 결국 밑의 표와 같이 표가 나오게 된다. 출발 \ 도착 1 2 3 4 5 ..
백준 2110(공유기 설치) - Python(파이썬) - 이분탐색
백준 2110(공유기 설치) - Python(파이썬) - 이분탐색
2022.06.202110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 예제 설명 최소 거리는 1 , 최대 거리는 9(arr[-1])-1(arr[0]) = 8 1) 최소 거리가 4인 경우(mid) 공유기 설치 집과 집 사이의 거리 start mid =(1+8)//2=4 end 1 2 3 4 5 6 7 8 공유기 설치 1 2 4 8 9 최소 거리가 4가 되는 경우에는 1부터 시작해서 1+4=5 이상의 좌표에 공유기를 설치해야한다. 그렇기 때문에 1에 설치 후에 5이상의 좌표인 8에 ..
백준 1890(점프) - Python(파이썬) - 다이나믹
백준 1890(점프) - Python(파이썬) - 다이나믹
2022.06.201890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 처음 생각한 풀이는 다이나믹 프로그래밍이아니라 DFS를 생각해서 풀었다. 근데 시간제한에 걸리는걸로봐서 다이나믹 프로그래밍으로 다시 풀었다. 예제 설명 ① dp 테이블로 모두 다 0을 만들기 첫번째 줄 ( i=0 ) ② dp 테이블 가장 왼쪽 위 칸(dp[0][0]) =1 ③ array 테이블에서 array[0][0]의 값이 2이므로 오른쪽 +2 -> dp[0][0+2] = dp[0][0]+dp[0][2] 아래쪽 +2 -> dp[0+2][0] = dp..
백준 2309(일곱 난쟁이) - Python(파이썬) - Combinations 사용,브루트포스
백준 2309(일곱 난쟁이) - Python(파이썬) - Combinations 사용,브루트포스
2022.06.172309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 💬 처음 생각한 풀이(Python(파이썬)) 단순하게 python으로 풀 때 ① combinations 함수를 사용하여 일곱명 뽑기 ② 합이 100인 경우를 찾아 출력 *여기서 주의할점은 sort는 원본을 변경하지만, sorted는 원본을 변경하지 않는다. * tuple: sort()함수를 사용하지 못하므로 -> sorted를 사용하여 정렬 후 출력 💻파이썬(Python) import sys from itertools import combinations arr=[] #난..
백준 6603(로또) - Python(파이썬),Java(자바)- 백트래킹
백준 6603(로또) - Python(파이썬),Java(자바)- 백트래킹
2022.06.166603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 파이썬 Permutation: https://coooco.tistory.com/72 📌 파이썬 Combination 사용 import sys from itertools import combinations #0이 입력되기 전까지 계속 입력받기 while True: s = list(map(int,sys.stdin.readline().split())) #로또 종류 개수 k = s.pop(0) #로또 개수 0이면 그만 입력받기 if k==0: break #오..