티스토리

코딩탐사선

검색하기

블로그 홈

코딩탐사선

codingexplore.tistory.com/m

leecrossun 님의 블로그입니다.

구독자: 3

방명록 방문하기

주요 글 목록

[ Baekjoon : python ] 백준 11404번 플로이드 - 플로이드 워셜 알고리즘 (Floyd WarshAlgorithm) [ BAEKJOON ONLINE JUDGE ] 11404 플로이드 _ Python 파이썬 1. 문제 입력 예시 출력 예시 5 14 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 3 5 10 3 1 8 1 4 2 5 1 7 3 4 2 5 2 4 0 2 3 1 4 12 0 15 2 5 8 5 0 1 1 10 7 13 0 3 7 4 10 6 0 www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2. 아이디어 이 문제는 플로이.. 공감수 0 댓글수 0 2021. 5. 12.
[ Baekjoon : python ] 백준 18406번 럭키 스트레이트 - 구현 (시뮬레이션) [ BAEKJOON ONLINE JUDGE ] 18406 럭키 스트레이트 _ Python 파이썬 " 문제 " 어떤 게임의 아웃복서 캐릭터에게는 럭키 스트레이트라는 기술이 존재한다. 이 기술은 매우 강력한 대신에 항상 사용할 수는 없으며, 현재 게임 내에서 점수가 특정 조건을 만족할 때만 사용할 수 있다. 특정 조건이란 현재 캐릭터의 점수를 N이라고 할 때 점수 N을 자릿수를 기준으로 반으로 나누어 왼쪽 부분의 각 자릿수의 합과 오른쪽 부분의 각 자릿수의 합을 더한 값이 동일한 상황을 의미한다. 예를 들어 현재 점수가 123,402라면 왼쪽 부분의 각 자릿수의 합은 1+2+3, 오른쪽 부분의 각 자릿수의 합은 4+0+2이므로 두 합이 6으로 동일하여 럭키 스트레이트를 사용할 수 있다. 현재 점수 N이 주어.. 공감수 0 댓글수 0 2021. 4. 3.
[ Baekjoon : python ] 백준 1439번 뒤집기 - 그리디 알고리즘 [ BAEKJOON ONLINE JUDGE ] 1439번 뒤집기 _ Python 파이썬 " 문제 " www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net " 아이디어 " 0과 1이 끊어지는 구간을 세어서 더 적은 구간의 개수를 출력하면 된다. 예를 들어 0001100 의 경우 000 / 11 / 00 으로 나눌 수 있고, 11 부분만 뒤집으면 되기 때문에 답은 '1' 이다. 또다른 예로 0100011010 의 경우 0 / 1 / 000 / 11 / 0 / 1 / .. 공감수 0 댓글수 0 2021. 3. 27.
[ Baekjoon : python ] 백준 15990번 1, 2, 3 더하기 5 - 다이나믹프로그래밍 [ BAEKJOON ONLINE JUDGE ] 15990 1, 2, 3 더하기 5 _ Python 파이썬 " 문제 " www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net " 아이디어 " 이 문제의 기본 뼈대는 [ 백준 9095번 1, 2, 3 더하기 ] 와 동일하다. [ Baekjoon : python ] 백준 9095번 1, 2, 3 더하기 - 다이나믹프로그래밍 [ BAEKJOON ONLINE JUDGE ] 9095번 1, 2, 3 더하기 _ Python 파이썬 " 문제 " www.acmicpc.net/prob.. 공감수 0 댓글수 0 2021. 2. 23.
[ Baekjoon : python ] 백준 11052번 카드 구매하기 - 다이나믹프로그래밍 [ BAEKJOON ONLINE JUDGE ] 11052 카드 구매하기 _ Python 파이썬 " 문제 " 제목 :www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net " 아이디어 " D[i] = 카드 i개를 구매하는 최대 비용 P[j] = j번째 카드팩의 비용 i-j개의 카드 + j번째 카드팩(마지막에 구매) = i개의 카드 (최종) -> D[i] = max ( D[i-j] + P[j] ) ( j>=1, j 공감수 0 댓글수 0 2021. 2. 21.
[ Baekjoon : python ] 백준 9095번 1, 2, 3 더하기 - 다이나믹프로그래밍 [ BAEKJOON ONLINE JUDGE ] 9095번 1, 2, 3 더하기 _ Python 파이썬 " 문제 " www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net " 아이디어 " D[n] = n을 1,2,3의 합으로 나타내는 방법의 수 D[n] = D[n-1] + D[n-2] + D[n-3] (n>=3) D[n] = 1 (n=0, n=1) D[n] = 2 (n=2) " 코드 " 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import sys sys.setrecursionlimit(10000000) def cal.. 공감수 0 댓글수 0 2021. 2. 20.
[ Baekjoon : python ] 백준 11727 2×n 타일링 2 - 다이나믹프로그래밍 [ BAEKJOON ONLINE JUDGE ] 11727 2×n 타일링 2_ Python 파이썬 " 문제 " www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net " 아이디어 " 기본 아이디어는 2xn 타일링 (1) 문제와 유사하다. ↓ 2xn 타일링 (1) 문제 풀이 [ Baekjoon : python ] 백준 11726 2xn 타일링 - 다이나믹프로그래밍 [ BAEKJOON ONLINE JUDGE ] 11726 2xn 타일링 _ Python 파이썬 " 문제 " www.acmicpc.net/.. 공감수 0 댓글수 0 2021. 2. 20.
[ Baekjoon : python ] 백준 11726 2xn 타일링 - 다이나믹프로그래밍 [ BAEKJOON ONLINE JUDGE ] 11726 2xn 타일링 _ Python 파이썬 " 문제 " www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net " 아이디어 " D[n] = 주어진 2 * n 직사각형을 채우는 경우의 수 맨 끝 타일을 1 * 2 타일로 채울 경우 -> D[n-2] 맨 끝 타일을 2 * 1 타일로 채울 경우 -> D[n-1] D[n] = D[n-1] + D[n-2] (n>=3) D[n] = 1 (n=1) D[n] = 2 (n=2) " 코드 " 1 2 3 .. 공감수 0 댓글수 0 2021. 2. 20.
[ Baekjoon : python ] 백준 2021 1로 만들기 - 다이나믹 프로그래밍 (재귀호출) [ BAEKJOON ONLINE JUDGE ] 2021 1로 만들기 _ Python 파이썬 " 문제 " www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net " 아이디어 " 이 문제는 큰 문제를 작은 문제로 쪼개어 푸는 다이나믹 프로그래밍 방식으로 해결할 수 있다. 따라서, 점화식을 D(n) 을 정의하고 문제를 작게 쪼개어 보자. D(n) = n을 1로 만드는 최소 횟수 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. -> D(n) = 1 + D(n/3) 2. X가 2로 나누어 떨어지면, 2로 나눈다. -> D(n) = 1 + D(n/2) 3. 1을 뺀다. -> D(n) =.. 공감수 0 댓글수 0 2021. 2. 20.
[ Baekjoon : python ] 백준 3085 사탕게임 - 브루트포스 [ BAEKJOON ONLINE JUDGE ] 3085 사탕게임 _ Python 파이썬 " 문제 " www.acmicpc.net/problem/3085 3085번: 사탕 게임 첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다. www.acmicpc.net " 아이디어 " 2가지 과정을 거쳐서 문제를 풀 수 있다. 1. 인접한 두 사탕을 교환한다. (★연속부분 구한 후 원위치) - N^2 행과 열이 N개인 배열에서 임의의 원소 한개를 선택하고 그 원소의 오른쪽 원소, 그리고 아래쪽 원소와 교환한다. (시간복잡도 : N^2) (왼쪽과 위쪽은 중복이 발생하므로 교환하지 않는다.) 2. 가장 긴 연속부분 (행 또는 열) 을 구한다. 원래 모든 행, 열을 조사하는 것이 정석이지만, 중복을 조금 줄여보.. 공감수 0 댓글수 0 2021. 2. 20.
[ Baekjoon : python ] 백준 10866 덱 Deck - 파이썬으로 덱 구현하기 [ BAEKJOON ONLINE JUDGE ] 10866 덱 _ Python 파이썬 " 문제 " www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net " 아이디어 " 기본적인 아이디어는 10828 스택 문제와 비슷하다. 2021/01/03 - [알고리즘/Beakjoon] - [ Baekjoon : python ] 백준 10828번 스택 - 파이썬으로 스택 구현하기 [ Baekjoon : python ] 백준 10828번 스택 - 파이썬으로 스택 구.. 공감수 0 댓글수 0 2021. 1. 3.
[ Baekjoon : python ] 백준 10828번 스택 - 파이썬으로 스택 구현하기 [ BAEKJOON ONLINE JUDGE ] 10828 스택 _ Python 파이썬 " 문제 " www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net " 아이디어 " 사용자 입력을 위와 같이 "push 1" 과 같은 방식으로 명령문 + 데이터 형태로 전달하기 때문에 sys.stdin.readline().split() 을 사용하여 각각 배열의 원소로 집어넣는다. (코드의 command 리스트) command[0] 으로 명령을 구분하고 comman.. 공감수 1 댓글수 0 2021. 1. 3.
[ Baekjoon : python ] 백준 15552번 빠른 A+B ( input() vs sys.stdin.readline()) [ BAEKJOON ONLINE JUDGE ] 15552 빠른 A+B _ Python 파이썬 " 문제 : 백준 15552 빠른 A+B " www.acmicpc.net/problem/15552 15552번: 빠른 A+B 첫 줄에 테스트케이스의 개수 T가 주어진다. T는 최대 1,000,000이다. 다음 T줄에는 각각 두 정수 A와 B가 주어진다. A와 B는 1 이상, 1,000 이하이다. www.acmicpc.net " 아이디어 " ' 본격적으로 for문 문제를 풀기 전에 주의해야 할 점이 있다. 입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다는 점이다. ---중략 --- Python을 사용하고 있다면, input 대신 sys.stdin.readline을 사용할 수 있다. 단,.. 공감수 0 댓글수 0 2021. 1. 3.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.