[백준] Python,Java로 풀기📖
백준 1913(달팽이) - Python(파이썬) - 구현
백준 1913(달팽이) - Python(파이썬) - 구현
2022.06.061913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 예제 풀이 49 26 27 28 29 30 31 48 32 47 33 46 34 45 35 44 36 43 42 41 40 39 38 37 입력 받은 길이 7은 문자 n이라고 가정하고 이렇게 네부분으로 나눌 수 있다. ( i : x축( → ), j ( : y축( ↓ ) ) 1. 노란색 부분 : i 값은 일정 | j 값은 1씩 늘어남 | 49부터 시작해서 49 - 7(n) +1 = 43까지 줄어듬 2. 초록색 부분 : i 값은 1씩 늘어남 | j 값은 일정 | 43..
백준 20152(Game Addiction) - Python(파이썬) - 다이나믹
백준 20152(Game Addiction) - Python(파이썬) - 다이나믹
2022.06.0620152번: Game Addiction 첫째 줄에 집과 PC방의 좌표 (H, H), (N, N) 을 나타내는 두 정수 H, N (0 ≤ H, N ≤ 30) 이 차례로 주어진다. www.acmicpc.net 예제 설명 (8,8) -> (4,4) 를 가는 방법의 수는 (4,4) -> (8,8) 로 가는 방법의 수랑 동일하다. 이 방법의 수는 y>x인 곳은 침수되어서 갈 수 없다고 하였으므로 (4,5),(4,6),,, 이 모든 값은 0이라고 볼 수 있다. (4,4)의 점을 (0,0)이라고 가정하고, (8,8)의 점을 (4,4)라고 가정하고나서 표를 작성하면 다음과 같다 점화식 | if j>=i : dp[j][i] = dp[j-1][i] + dp[j][i-1] j \ i 4=0 5=1 6=2 7=3 8=4 4..
백준 1991(트리 순회) - Python(파이썬) - 트리,재귀
백준 1991(트리 순회) - Python(파이썬) - 트리,재귀
2022.06.031991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 설명 전위 순회의 경우 , 루트 -> 왼쪽 -> 오른쪽 중위 순회의 경우, 왼쪽 -> 루트 -> 오른쪽 후회 순회의 경우, 왼쪽 -> 오른쪽 -> 루트 tree[루트] = [ 왼쪽, 오른쪽 ] tree[A] = [ B,C ] tree[B] = [ D ] tree[C] = [ E,F ] tree[E] = [ . , . ] tree[F] = [ . , G ] tree[D] = [ . , . ] tree[G] = [ . , . ] Python에서는 t..
백준 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번째에 사자..
백준 9012(괄호) - Python(파이썬) - 문자열
백준 9012(괄호) - Python(파이썬) - 문자열
2022.05.279012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net Stack을 사용하지 않은 풀이 접근 방법 1) " ( " 의 개수와 " ) "의 개수가 같기 2) 위 조건에 예외의 경우로 (()(()가 있는데 이 경우는 개수는 같지만 )(이런식으로 남아서 NO가 된다. 즉, 방향도 참고 풀이방법 ① " ) " 인 경우 cnt값을 +1 ② " ( " 인 경우 앞에 )이 없는 경우만 사라질 수 있기 때문에 cnt값이 양수인 경우에는 셀 필요가 없다 -> " ( " 이고 cnt stack에 "( "..