[백준] Python,Java로 풀기📖
백준 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 #오..
백준 2667(단지번호 붙이기) - Python(파이썬) - BFS
백준 2667(단지번호 붙이기) - Python(파이썬) - BFS
2022.06.142667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 예제 설명 이렇게 생긴 지도가 있다고 할 때 선분 하나를 공유하고 있는 경우에는 같은 단지이다. 출력으로 단지의 개수를 구하고 단지 안에 속하는 집의 수를 오름차순으로 정렬하여 출력하도록 한다. 문제 풀이 1) dfs 방식으로 풀기 1️⃣ dfs 함수 만들기 ① 재귀함수를 이용해서 풀기 때문에 함수를 실행 전에 지도안에 포함되는지를 확인 -> 아닐 경우 , return False ② 지도안에 포함될 경우 지도 안에 1로 표시된 집인지 확인 -> 아닐 경우, ret..
백준 2178(미로 탐색) - Python(파이썬) - BFS
백준 2178(미로 탐색) - Python(파이썬) - BFS
2022.06.142178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 예제 설명 이런식으로 문제에서 주어진 배열에 1이 적혀있고 인접한 칸으로만 이동이 가능하다. 따라서 BFS 문제로 문제는 이동할때마다 이동한 곳(array[y][x])의 값보다 +1시켜서 마지막 array[4-1][6-1]의 값을 구하면 된다. ( https://coooco.tistory.com/32 ) 💻 Python 처음 한 풀이 import sys from collections import deque n,m = map(int,sys.stdin.readline().split()) array..
백준 1504(특정한 최단 경로) - Python(파이썬) - 최단 경로
백준 1504(특정한 최단 경로) - Python(파이썬) - 최단 경로
2022.06.12참고자료 : 다익스트라 알고리즘 참고 자료 [이코테] CHAPTER 09 최단 경로 알고리즘 - 다익스트라 최단 경로 알고리즘 최단 경로 알고리즘(Shortest Path) : 가장 짧은 경로를 찾는 알고리즘 1) 최단 경로 문제- 지점( 노드 ), 지점 간 연결된 도로( 간선 ) - 한 지점에서 다른 한 지점까지의 최단 경로를 구해야 하는 경우 coooco.tistory.com 예제 설명 1번 노드에서 시작할 경우 도착 노드 1번 2번 3번 4번 최소 비용 0 3 5 4 2번 노드에서 시작할 경우 도착 노드 1번 2번 3번 4번 최소 비용 3 0 3 4 3번 노드에서 시작할 경우 도착 노드 1번 2번 3번 4번 최소 비용 5 3 0 1 1번 노드 -> 2번 노드 -> 3번 노드 -> 4번노드 인경우 최..
백준 10819(차이를 최대로)- Python(파이썬),Java(자바) - 구현,브루트포스(Permutations,Combinations,백트래킹,Java- 스택 사용 )
백준 10819(차이를 최대로)- Python(파이썬),Java(자바) - 구현,브루트포스(Permutations,Combinations,백트래킹,Java- 스택 사용 )
2022.06.0910819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 예제 설명 일단 배열 A를 오름차순으로 정렬한다. 인덱스 0 1 2 3 4 5 배열 1 4 8 10 15 20 인덱스의 차이가 최대이기 위해서는 고른 인덱스와 선택하지 않은 배열 중 제일 먼 인덱스를 골라야한다. ex ] 0고르기 -> 5고르기 -> 1고르기 -> 4고르기 -> 2고르기 -> 3고르기 하지만 마지막에 2를 고르고 3을 고르는 것보다 인덱스 3을 제일 앞에 두는 것이 더 차이의 합이 커진다 ex ] 3고르기 -> 0고르기 -> 5고르기 -> 1고르기 -> 4고르기..
백준 2252(줄 세우기) - Python(파이썬) - 위상정렬
백준 2252(줄 세우기) - Python(파이썬) - 위상정렬
2022.06.082252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상 정렬 설명 CHAPTER 6 -번외 정렬 - 위상 정렬(Topology Sort) - Python(파이썬) 참고 자료 : https://m.blog.naver.com/ndb796/221236874984 위상 정렬 : 순서가 정해져 있는 작업을 수행해야 할 때 그 순서를 정해주기 위해서 사용하는 알고리즘 ex ] 0번 -> 1번 ->3번 -> 5번 순으로 이어진.. coooco.tistory.com 💻 Python(..
백준 11000(강의실 배정) - Python(파이썬) - 그리디,정렬(heap, lambda,Comparator)
백준 11000(강의실 배정) - Python(파이썬) - 그리디,정렬(heap, lambda,Comparator)
2022.06.0811000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si 1번 ->3번 -> 5번 순으로 이어진.. coooco.tistory.com 1 2 3 4 5 1-3 2-4 3-5 일단 1-3 ,2-4 ,3-5 을 처음 시작하는 시간으로 오..
백준 5430(AC) -Python(파이썬) - 자료구조
백준 5430(AC) -Python(파이썬) - 자료구조
2022.06.085430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 풀이 1. 일단 수행할 함수, 배열에 들었는 수의 개수, 배열에 들어있는 정수를 받아들인다. 2. 배열에 들어있는 정수는 항상 "["+배열에 들어 있는 정수+"]" 구조로 이루어졌다. "[]"을 제외한 값을 리스트로 받아들이기 위해서 인덱스 1부터 -1까지의 인덱스르 리스트로 받아들인다.[1:-1] 배열 "R" "D" "D" 4 1 3 2 1 2 3 2 1 1 4 3 2 이런 느낌으로 RDD 함수가 진행되면 [ 2,1 ]이 남는다. 📌 문제 풀면서 주의할점 1. 파이썬에서는 deque 라이브러리를 사용 2. re..
백준 10828(스택) - Python(파이썬),Java(자바) -자료구조,스택
백준 10828(스택) - Python(파이썬),Java(자바) -자료구조,스택
2022.06.0710828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 예제 설명 push 1 stack = [ 1 ] push 2 stack = [ 1,2 ] top stack = [ 1,2 ] 이므로 stack top = 2 출력 size stack = [ 1,2 ]이므로 size = 2 출력 empty stack = [ 1,2 ]이므로 empty가 아니므로 0 출력 pop stack = [ 1,2 ]이므로 pop이므로 2 출력 pop stack = [ 1 ]이므로 pop이므로 1 출력 pop stack = [ ..
백준 1158(요세푸스 문제) - Python(파이썬),Java(자바) - 자료구조(큐)
백준 1158(요세푸스 문제) - Python(파이썬),Java(자바) - 자료구조(큐)
2022.06.071158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 예제 설명 이걸 좀 해석하면 ① 제일 앞에 있는 값을 pop하고 뒤에다가 append한다 ② 그 과정을 두번 하고나서 ③ 세번째에는 pop하면서 나오는 값을 따로 큐에 저장한다. 이렇게 세 개의 과정을 한번 할때마다 하고서 큐에 사람 수만큼 채워지면 그만둔다. 풀이과정 ① 사람 수만큼 1번부터 사람수까지 번호를 부여한다. ② 제일 앞에 있는 값을 pop하고 다시 append에서 뒤로 붙이는 과정을 두번을 하므로 range(2)만큼 for문을 실행한다. ③ 세번째 pop하는 것은 visted 리스트에 붙인다. ④ ②,③번의 과정을 모두 큐에 저장할 때까지..