[백준] Python,Java로 풀기📖
백준 1057(토너먼트) - Python(파이썬) - 수학
백준 1057(토너먼트) - Python(파이썬) - 수학
2022.05.271057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 접근 방법 ex ] 16 8 9 인 경우 (김지민 임한수 ) 이런식으로 토너먼트가 진행되는데 김지민의 번호(8)과 임한수의 번호(9)를 2로 계속 나누어서 반올림하였을 때 값이 같은 경우 그만둔다. -> 서로 대결을 하지 않는 경우는 없다. 풀이방법 ① while 문으로 계속 2로 나누게 하기 -> 올림 ② 단 반올림(김지민의 번호)== 반올림(임한수의 번호) whil문 끝내기 Python import math import sys #사람수,김지민,임한수 n,kim,li..
백준 1120(문자열) - Python(파이썬)
백준 1120(문자열) - Python(파이썬)
2022.05.271120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 접근 방법 최소인 값은 A의 문자를 하나씩 비교하여서 남는 문자열이 있는 경우 B와 똑같은 값을 채우면 최소값이 된다. B a a b a b b c 첫번재 A a d a a b c c 채우기 두번째 A a 채우기 a d a a b c 풀이방법 ① for문으로 B의 시작점을 변경하여서 0부터 시작해서 len(B)-len(A)까지 루프문을 돌리기 ② 시작점으로부터 B와 A를 A의 길이까지 문자열을 비교해서 최솟값을 계속 비교하..
백준 18353(병사 배치하기) - Python(파이썬) - LIS,다이나믹
백준 18353(병사 배치하기) - Python(파이썬) - LIS,다이나믹
2022.05.2618353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이와 LSI에 대한 설명 & 비슷한 문제 백준 11053( 가장 긴 증가하는 수열 ) - Python(파이썬),Java(자바)- 다이나믹(LIS) 참고 링크 : https://www.youtube.com/watch?v=5Lu34WIx2Us 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1.. coooco.tistory.com 풀이방법 ① dp[i..
백준 11053( 가장 긴 증가하는 수열 ) - Python(파이썬),Java(자바)- 다이나믹(LIS)
백준 11053( 가장 긴 증가하는 수열 ) - Python(파이썬),Java(자바)- 다이나믹(LIS)
2022.05.26참고 링크 : https://www.youtube.com/watch?v=5Lu34WIx2Us 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net LIS(Longest Increasing Subsequence) D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 수열의 길이 -> 점화식 : 모든 0 4와 비교했을 때 8이 4보다 크므로 4의 값 1(D[0])+1= 2 가 최댓값으로 들어간다. 2 또한 8이 2보다 크므로 ..
백준 2156(포도주 시식) - 다이나믹 알고리즘
백준 2156(포도주 시식) - 다이나믹 알고리즘
2022.05.26① 풀이 방법 d[i] : i번째까지 최대로 먹을 수 있는 포도주의 양 i=0인 경우 : d[0] = grape[0] i=1인 경우 : d[1] = grape[0]+ grape[1] i=2인 경우 : grape[0]+grape[1](d[1])와 grape[0]+grape[2]와 grape[1]+grape[2] 의 최댓값을 구한다. ..... i=n인 경우 : ① 마지막 grape[i]을 먹었을 경우 -> grape[i-1]을 먹은 경우와 먹지 않은 경우가 있다 1) grape[i-1]을 먹은 경우: grape[i] + grape[i-1] + d[n-3]( n-3번째까지 최대로 먹을 수 있는 포도주의 양) 2) grape[i-1]을 먹은 경우: grape[i] + d[n-2] ② grape[i]를 먹지 않..
백준 13458(시험 감독) - Python(파이썬),Java(자바) - 수학
백준 13458(시험 감독) - Python(파이썬),Java(자바) - 수학
2022.05.2513458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 풀이 방법 ① 총감독은 무조건 들어가므로 시험장의 개수를 초기값으로 설정 ② 각 시험장의 응시자 수 - (총감독관의 응시자의 수) 를 (부감독관의 응시자의 수)로 나눈 수를 무조건 올림(math.ceil) 처리 ※ 주의 시험장의 응시자의 수 - (총감독관의 응시자의 수)의 값이 음수가 될 수 있으므로 max를 사용하여서 음수일 때는 0이 되도록 처리 Python( 파이썬) import sys import m..
백준 2232(지뢰) - 구현
백준 2232(지뢰) - 구현
2022.05.252232번: 지뢰 일직선상에 N개의 지뢰가 같은 간격으로 매설되어 있다. 각각의 지뢰는 충격 강도 Pi가 있어서, Pi를 초과하는 힘을 가하면 Pi만큼의 힘을 발휘하며 터지게 된다. 어떤 지뢰가 터지게 되면, 그 지 www.acmicpc.net 풀이 방법 ⓘ 하나씩 입력 받아서 graph 리스트 안에 입력 받기 ② for문을 돌려서 리스트[graph[i]]의 값이 현재 리스트 바로 앞의 값(graph[i-1])보다 크거나 같고 현재 리스트 바로 뒤의 값[graph[i+1])보다 작거나 같으면 출력된다고 보면 된다. ( graph[i] >= graph[i-1] && graph[i]>=graph[i+1] ) ③ 예외의 경우 1) 리스트의 개수가 1인 경우 앞과 뒤가 없으므로 자기 자신이 무조건 출력 된다. ..
백준 18352(특정 거리의 도시 찾기) - Python(파이썬) -BFS
백준 18352(특정 거리의 도시 찾기) - Python(파이썬) -BFS
2022.05.2518352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 방법 모든 도로의 거리가 1이므로 -> bfs 가능하다. ① graph(노드와 간선을 나타내는 그래프) (연결 여부 확인용)으로 사용한다 -> a와 b가 연결되었다고 가정하면 graph[a] = [b] 이렇게 있도록. ② 거리 테이블을 표현하는 테이블 하나 선언하기 (distance) , 이때, 초기값들은 모두 -1이도록 선언 ③ 시작노드부터 시작하여서 연결된 노드들의 값이 -1인경우(..
백준 16948(데스나이트) - Python(파이썬),자바(Java)
백준 16948(데스나이트) - Python(파이썬),자바(Java)
2022.05.2416948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net BFS - duque 메서드 - Python(파이썬),Java(자바) DFS 설명 스택, 큐, 재귀함수, DFS 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘으로 DFS, BFS , 이 두 알고리즘을 이해하기 위해서 스택, 큐, 재귀 함 coooco.tistory.com 풀이 방법 ① 이차원 배열로 nxn graph 생성 ( -> 이동..
백준 4936(섬의 개수) - BFS 풀기
백준 4936(섬의 개수) - BFS 풀기
2022.05.21BFS - duque 메서드 - Python(파이썬),Java(자바) DFS 설명 스택, 큐, 재귀함수, DFS 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘으로 DFS, BFS , 이 두 알고리즘을 이해하기 위해서 스택, 큐, 재귀 함 coooco.tistory.com import sys from collections import deque dw=[-1,-1,-1,0,0,1,1,1] dh=[-1,0,1,-1,1,-1,0,1] def bfs(graph,h,w): queue=deque() queue.append((h,w)) while queue: h,w = queue.popleft() for i in range(8): nw = w+dw[i] nh = h+..
백준 14716(현수막) - 파이썬(Python),자바(Java) - DFS(재귀함수),sys.setrecursionlimit(10**6),BFS
백준 14716(현수막) - 파이썬(Python),자바(Java) - DFS(재귀함수),sys.setrecursionlimit(10**6),BFS
2022.05.2014716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net * 재귀함수 문제 시에는 sys.setrecursionlimit(10**6)을 상단에 적어준다. 파이썬의 기본 재귀 깊이 제한이 1000으로 작은 편이기 때문에 런타임 에러 발생한다. graph=[] for i in range(m): graph.append(list(map(int,sys.stdin.readline().split()))) graph=[list(map(int,sys.stdin.readline().split())) for _ in range(m)] 둘은 동일하다. 1. DFS로 푼 경우 스택, 큐, 재귀함수, DFS 탐색(Search) : 많은 양의 데이..
백준 1260(DFS와 BFS) - DFS & BFS
백준 1260(DFS와 BFS) - DFS & BFS
2022.05.18DFS 설명 스택, 큐, 재귀함수, DFS 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘으로 DFS, BFS , 이 두 알고리즘을 이해하기 위해서 스택, 큐, 재귀 함수를 알아야한다. 참고자료. https: coooco.tistory.com BFS 설명 BFS - duque 메서드 - Python(파이썬),Java(자바) DFS 설명 스택, 큐, 재귀함수, DFS 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘으로 DFS, BFS , 이 두 알고리즘을 이해하기 위해서 스택, 큐, 재귀 함 coooco.tistory.com 내가 푼 풀이법 입력한 값들을 연결된 노드를 저정하도록 그래프를 만든다. graph..
백준 2864(5와 6의 차이) - Python(파이썬)
백준 2864(5와 6의 차이) - Python(파이썬)
2022.05.176이라고 표시된 값이 모두 5로 변경될 경우의 합이 가장 최솟값일 거고, 5라고 표시된 값이 모두 6으로 변경될 경우의 합이 가장 최댓값이다. 따라서 replace를 통해 변경해서 더해서 표현한다. import sys array = sys.stdin.readline().split() print(int(array[0].replace('6','5'))+int(array[1].replace('6','5')),int(array[0].replace('5','6'))+int(array[1].replace('5','6')))
백준 2752(세수정렬)- Python(파이썬)
백준 2752(세수정렬)- Python(파이썬)
2022.05.171) sort 로 배열 정리 import sys array = list(map(int,sys.stdin.readline().split())) array.sort() print(array[0],array[1],array[2]) 2) 삽입 정렬로 정리 삽입 정렬로 풀면 숫자가 세개밖에 없기 때문에 더 일찍 sort할수도 있다고 생각하였기 때문에 삽입 정렬로도 한번 풀어봤더니 더 짧게 풀리긴 했다. 백준 -2750 (수 정렬하기) - 선택정렬, 삽입정렬, 계수정렬 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.n coooco.t..
백준 1931(회의실 배정) - Python(파이썬)
백준 1931(회의실 배정) - Python(파이썬)
2022.05.17끝나는 순서대로 정렬 import sys N=int(sys.stdin.readline()) array=[] for i in range(N): array.append(list(map(int,sys.stdin.readline().split()))) array.sort(key=lambda x:(x[1],x[0])) count =end_time=0 for i in range(N): if end_time
백준 10989( 수 정렬하기3 ) - 파이썬(Python)
백준 10989( 수 정렬하기3 ) - 파이썬(Python)
2022.05.16계수 정렬로 풀기 정렬 - 계수 정렬 계수 정렬 (Count Sort) : 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 알고리즘( 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 coooco.tistory.com import sys N = int(sys.stdin.readline()) array = [0]*10001 for i in range(N): array[int(sys.stdin.readline())]+=1 for i in range(1,len(array),1): # if를 하지 않을 경우 시간 초과가 난다. if array[i]!=0: for j in range(array[i]): print(i) if를 선언하여 array..