개발바닥

문제 https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 문제 해결 방법 BFS 로 문제를 해결하면 된다. 10억이 되기 때문에 set을 활용해서 방문 여부를 판단해야 된다. 그리고 연산자마다 우선 순위가 있기 때문에 우선 순위 높은 연산자부터 계산해서 queue에 넣었다. 다음 값이 t보다 크다면 굳이 이동할 필요가 없다. 그 이유는 되돌아 가는 방법이 -, / 두개 연산자 뿐인데 -를 하게 되면 값이 0이 되서 더이상 진행할 수가 없고,..

문제 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 해결 방법 다이나믹 프로그래밍으로 문제를 해결해야 된다. 범위가 1000이기 때문에 2중 포문을 통해서 가장 긴 값을 갱신해주면 된다. DP[현재 인덱스] = Date[기존인덱스] DP[현재인덱스] 인 경우에는 DP[현재 인덱스] 값을 갱신해준다..

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 해결 방법 다이나믹 프로그래밍으로 문제를 해결해야 된다. 첫번째 물건부터 시작해서 현재 물건을 넣었을 때와 넣지 않았을 때 가치 중 큰 값을 갱신해주면 된다. 물건을 넣었을 때와 넣지 않았을 때를 어떤식으로 코드를 구현해야 될까요? 통과한 코드를 분석해보면 다음과 같다. for i in 물건개수 : for j in 1부터..

문제 https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 문제 해결 방법 DP를 활용해서 문제를 해결할 수 있다. 먼저 초기값으로 i번째 인덱스에는 A를 i번 누른 횟수로 초기화를 하고 버퍼에 있는 값을 복사하기 까지 총 3번에 커맨드 횟수가 필요하므로 컨트롤 v를 한번 두번 세번 누른 최대값을 비교 후 갱신해주면..

문제 https://www.acmicpc.net/problem/2864 2864번: 5와 6의 차이 문제 상근이는 2863번에서 표를 너무 열심히 돌린 나머지 5와 6을 헷갈리기 시작했다. 상근이가 숫자 5를 볼 때, 5로 볼 때도 있지만, 6으로 잘못 볼 수도 있고, 6을 볼 때는, 6으로 볼 때도 있지만, 5� www.acmicpc.net 문제 해결 방법 내장함수 replace를 사용해서 최소값을 구할때는 6을 5로 최대값을 구할때는 5를 6으로 변경 후 더해서 출력하면 된다. 소스 코드 보기 https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_2864.py jokerKwu/BOJ_Algorithm Contribute to jokerKw..

문제 https://www.acmicpc.net/problem/12761 12761번: 돌다리 동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 \(N\)번 돌 위에, 주미는 \(M\)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대�� www.acmicpc.net 문제 해결 방법 bfs로 문제 해결 방법을 접근했습니다. 총 이동 가능한 경우 8가지를 현재 위치에서 다음 위치를 계산해서 범위를 벗어나지 않았고 처음 방문했다면 큐에 넣으면 된다. 소스 코드 보기 https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_12761.py jokerKwu/BOJ_Algorithm ..

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해결 방법 top -bottom 방식으로 현재 숫자에서 3가지 연산을 했을 때 인덱스 값이 0 이라면 현재숫자까지 이동한 횟수 +1 을 해서 값을 갱신해준다. dp[연산 후 값] = dp[연산 전 값] +1 소스 코드 보기 https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_1463.py jokerKwu/BOJ_Algorithm Contribute to jokerKwu/BOJ_Algorithm development by creating ..

문제 https://www.acmicpc.net/problem/1371 1371번: 가장 많은 글자 첫째 줄부터 글의 문장이 주어진다. 글은 최대 5000글자로 구성되어 있고, 공백, 알파벳 소문자, 엔터로만 이루어져 있다. 그리고 적어도 하나의 알파벳이 있다. www.acmicpc.net 문제 해결 방법 문제에서 입력을 eof 날때까지 받기 위해서 파이썬에서는 두 가지 방법이 있다. # sys read를 이용하는 방법 import sys line = sys.stdin.read() #try except 이용하는 방법 line = '' while True: try: line = input() except EOFError: break 문장을 입력을 받고 한글자씩 꺼내서 알파벳에 해당되는 인덱스에 카운팅해서 ..