분류 전체보기
백준 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..
Mac - Git is not installed No such file: git.exe 문제 뜰 때 해결 법
Mac - Git is not installed No such file: git.exe 문제 뜰 때 해결 법
2022.06.011. 이런 문제가 뜨면 저 Downoload and install을 누르면 다운로드가 되지 않고 밑 사진과 같은 에러가 뜬다. 2. 그럼 Configure 버튼을 누르거나 intellJ IDEA- Preferences - Version Control - Git을 눌러 아래와 같은 페이지가 보이면 된다. 3. 그 후에는 깃 공식 홈페이지( https://git-scm.com )에 접속하여서 Download for Mac 버튼을 클릭 4. 나같은 경우에는 brew를 이미 설치하였기 때문에 터미널에 brew install git을 치면 다운이 받아진다. 5. 그럼 다운을 받고 난 후에 brew가 어디에 git을 저장했는지 알기 위해서 brew info git(찾고 싶은 appname)을 넣으면 된다. 6. 저..
백준 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에 "( "..
백준 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..