[백준] Python,Java로 풀기📖
백준 4485(녹색 옷 입은 애가 젤다지?) - 다익스트라알고리즘, 힙구조, 최단거리- python
백준 4485(녹색 옷 입은 애가 젤다지?) - 다익스트라알고리즘, 힙구조, 최단거리- python
2024.11.04https://www.acmicpc.net/problem/4485예제 풀이일단 첨에는 DFS로 이용해서 풀었지만 아니나 다를까,, 바로 시간초과..⭐️그래서 생각한건 다익스트라 알고리즘으로 최단 경로 알고리즘이었다..예제 하나를 이용해서 다익스트라 알고리즘을 풀이하면 다음 사진과 같다고 생각하면 이해하기 쉽다. 만약 다익스트라 알고리즘이 먼가,, 이것부터라면 밑에 링크로 들어가는것을 추천한다 (나름 이코테 책보면서 정리해둔 다익스트라알고리즘이다. ) [이코테] CHAPTER 09 최단 경로 알고리즘 - 다익스트라 최단 경로 알고리즘최단 경로 알고리즘(Shortest Path) : 가장 짧은 경로를 찾는 알고리즘 1) 최단 경로 문제- 지점( 노드 ), 지점 간 연결된 도로( 간선 ) - 한 지점에서 다른..
백준 2164번(카드2) - 큐, 자료구조
백준 2164번(카드2) - 큐, 자료구조
2024.10.21https://www.acmicpc.net/problem/2164 ❓ python 풀이 - 규칙 찾아서 풀었따...내가 생각한 규칙은1(2^0)12(2^1)232*(3-2) = 24(2^2)452*(5-4) = 262*(6-4) = 472*(7-4) = 68(2^3)892102*(10-8) = 2112*(11-8) = 2122*(12-8) = 2132*(13-8) = 2142*(14-8) = 2152*(15-8) = 216(2^4)162의 거듭제곱인 경우:2의 거듭제곱에 해당하는 수는 그대로 남습니다. 예를 들어, 1, 2, 4, 8, 16은 그대로 해당 값이 남습니다.즉, 2^n인 경우 마지막 남는 카드는 그 값 그대로입니다.2의 거듭제곱보다 큰 수인 경우:2의 거듭제곱을 기준으로 해당 수(N)에서 ..
백준 10733번 (제로) - 자료구조, 스택
백준 10733번 (제로) - 자료구조, 스택
2024.10.21https://www.acmicpc.net/problem/10773 ❓ python 풀이import sysinput = sys.stdin.readline i = int(input().strip()) # 입력받을 정수의 개수 Kstack = [] # 숫자를 저장할 스택을 초기화for _ in range(i): # K번 반복하며 정수를 입력받음 put = int(input().strip()) # 입력받은 숫자를 정수로 변환 if put != 0: # 0이 아닐 경우 스택에 해당 숫자를 추가 stack.append(put) else: stack.pop() # 0일 경우 가장 최근에 입력된 숫자를 스택에서 제거print(sum(stack)) # 스택에 남아..
백준 10828(스택) - 스택, 자료구조
백준 10828(스택) - 스택, 자료구조
2024.10.14https://www.acmicpc.net/problem/10828 ❓ python 풀이import sysinput = sys.stdin.readline n = int(input().strip()) # 명령의 수stack = []for _ in range(n): command = input().strip().split() if command[0] == "push": stack.append(int(command[1])) elif command[0] == "pop": print(stack.pop() if stack else -1) #stack이 들어있을 경우 pop,else -1 elif command[0] == "size": print(len(..
백준 9012(괄호) - 스택
백준 9012(괄호) - 스택
2024.10.14https://www.acmicpc.net/problem/9012 일단 내가 생각한 풀이 " (())()) "와 같은 문자열이 주어졌을 때, 여는 괄호 " ( "는 +1, 닫는 괄호 " ) "는 -1로 처리다만, 예외적으로 "))(("와 같이 닫는 괄호가 여는 괄호보다 먼저 나오는 경우에도 합이 0이 될 수 있으므로, 합계가 0보다 작아지는 순간 루프를 즉시 종료하고valid = False로 설정.루프가 끝난 후, valid가 True이면서 합계가 0이면 "YES"를 출력하고, 그렇지 않으면 "NO"를 출력합니다. ❓ python 풀이import sysT = int(sys.stdin.readline().strip()) # 테스트 케이스 수for i in range(T): l = sys.stdin..
백준 1932(정수 삼각형) - Python(파이썬) -DP
백준 1932(정수 삼각형) - Python(파이썬) -DP
2022.07.071932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 예제 풀이 j=0 j=1 j=2 j=3 j=4 dp[0] dp[0][0] = 7 dp[1] dp[0][0] +dp[1][0] = 7 + 3 = 10 dp[0][0] +dp[1][1] = 7 + 8 = 15 dp[2] dp[1][0] +dp[2][0] = 10 + 8 = 18 max( dp[1][0]+dp[2][1], dp[1][1]+dp[2][1] ) = max(11,16) =16 dp[1][1] +dp[2][2] = 15 + 0 = 15 dp[3] dp[2][0] +dp[3][0] = 18 + 2 = 20 max( dp[2][0]+..
백준 11054(가장 긴 바이토닉 부분 수열) - Python(파이썬),Java(자바) - DP
백준 11054(가장 긴 바이토닉 부분 수열) - Python(파이썬),Java(자바) - DP
2022.07.0611054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 예제 풀이 가장 긴 바이토닉 부분 수열이 되기 위해서는 1 2 3 4 5 2 1 이 경우가 가장 기므로 출력으로 7이 나오게된다. 이걸 dp로 해석하면 증가하는지 dp로 확인하기 1) dp[1] = 5 전 수열 증가하는지 확인 결과 1 5 2 1 4 3 4 5 2 1 1 2 1 1 1 1 1 1 1 1 2) dp[2] = 2 전 수열 증가하는 지 확인 1 5 2 1 4 3 4 5 2 1 1 2 2 1 1 1 1 1 1 1 2) dp[3] = 1 전 수열 증가하는 지 확인 1 5 2 ..
백준 10844(쉬운 계단 수) - Python(파이썬) - DP
백준 10844(쉬운 계단 수) - Python(파이썬) - DP
2022.07.0510844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 예제 풀이 일단 첨에 보고 이해가 안되었다. 문제 뜻은 이와 같다 계단 같은 경우에는 무조건 +1 , -1 차이가 난다는 것이다. 자릿수가 1인 수를 구하라고 하면 1 - 9 이렇게 9개가 존재한다라는 의미이다. 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 자릿수가 2인 수를 구하라고 하면 0 _ -> 1개(1) , 1 _ -> 2개(0,2) , 2 _ -> 2개(1,3) , 3 _ -> 2개(2,4) , 4 _ -> 2개(3,5) , 5 _ ->2개(4,6) , 6 _ -> 2개(5,7) , 7 _ -> 2개(6,8) , 8 _ -> 2개(7,9) ..
백준 1966(프린터 큐) - Python(파이썬) - 큐,자료구조
백준 1966(프린터 큐) - Python(파이썬) - 큐,자료구조
2022.07.031966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 예제 풀이 마지막 테스트케이스 : priority: (몇번째 숫자인지, 중요도) ( 0,1 ) ( 1,1 ) ( 2,9 ) ( 3,1 ) ( 4,1 ) ( 5,1 ) sort_priorty: 중요도를 정렬시킨 리스트 9 1 1 1 1 1 priority[0][1] 와 sort_priority[0] 을 비교한다. ① priority[0][1] = 1 이 sort_priority[0] =9와 다름 => priorirty[0][1]의 값을 popleft()하고 뒤에 ap..
백준 2579(계단 오르기) -Python(파이썬),Java(자바) - DP
백준 2579(계단 오르기) -Python(파이썬),Java(자바) - DP
2022.07.012579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 예제 풀이 마지막 계단(i=5)에서의 최댓값이 나오는 가지수는 다음과 같다 1️⃣ i=2(5-3)일때의 최댓값 + ( i=4 ) + ( i=5 ) 2️⃣ i=3(5-2)일때의 최댓값 + ( i=5 ) 이 두가지를 비교해서 최댓값을 구하면 된다. dp[i] 0 1 2 3 4 5 i번째일 때의 최댓값 10 10+20 =30 10+15,20+15 중 큰 값= 35 dp[3-3]+(i=2)+ (i=3), dp[3-2]+(i=3) 중 큰 값 = 55 dp[4-3]+(i=3)+ (i=..
백준 9095(1,2,3 더하기) - Python(파이썬)
백준 9095(1,2,3 더하기) - Python(파이썬)
2022.06.309095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net * 내가 생각한 풀이 * 예제 풀이 dp[1] dp[2] dp[3] dp[4] dp[5] dp[6] dp[7] dp[8] dp[9] dp[10] 1 dp[1] +dp[2] =2 dp[1] +dp[2] +dp[3] =4 dp[1] +dp[2] +dp[3] =7 dp[2] +dp[3] +dp[4] =13 dp[3] +dp[4] +dp[5] =24 dp[4] +dp[5] +dp[6] =44 dp[5] +dp[6] +dp[7] =81 dp[6] +dp[7] +dp[8] =149 dp[7] +dp[8] +dp[9] =274 💻 Python(파이썬) import sys ..
백준 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 리..