본문 바로가기

분류 전체보기84

[백준 13305번] 주유소 - 파이썬 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 💡문제 분석 요약 N개의 도시가 있고, 도시 사이에는 거리가 있다. 각 도시에는 주유소마다 기름의 가격이 다른데, 가장 싸게 기름을 충전하여 첫 도시에서 마지막 도시까지 갔을 때의 기름 값을 구하여라. 💡알고리즘 설계 1. 첫 도시에서 다음 도시까지 가기 위한 기름을 구매한다. 2. 첫 도시의 기름값을 가장 싼 기름값으로 저장한다. 3. 다음 도시의 기름 값과 이전에 저장된 가장 싼.. 2024. 3. 2.
[백준 7568번] 덩치 - 파이썬 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 💡문제 분석 요약 몸무게와 키를 입력받고, 덩치 등수를 출력한다. 몸무게는 더 무거운데 키는 작거나, 몸무게는 가벼운데 키는 큰 경우는 덩치를 가릴 수 없으므로, 같은 등수로 출력한다. 💡알고리즘 설계 1. 사람들의 몸무게와 키 정보를 입력받는다. 2. 한 사람씩, 이 사람보다 키와 몸무게가 둘 다 큰 사람이 몇명인지 구하여 rank 리스트에 추가한다. 💡코드 import sys in.. 2024. 3. 2.
[백준 2594번] 놀이공원 - 파이썬 https://www.acmicpc.net/problem/2594 2594번: 놀이공원 첫째 줄에 놀이기구의 개수 N이 주어진다. 이어 N줄에 걸쳐 각 놀이기구의 운행시작 시각과 종료 시각이 빈 칸을 사이에 두고 주어진다. 시각은 시간단위 두 자리, 분 단위 두 자리로 구성되며 오 www.acmicpc.net 💡문제 분석 요약 놀이공원의 오픈 시간, 놀이기구 운행 시간, 마감 시간 사이 가장 쉬는 시간이 큰 시간을 구하라. 놀이기구의 운행 10분 전, 운행 10분 후까지는 쉴 수 없으며, 놀이기구의 운행 시간이 겹치는 경우에도 쉴 수 없다. 💡알고리즘 설계 1. 타임 리스트에 놀이공원의 오픈 시간과 놀이기구 운행 시작 시간, 종료 시간, 놀이공원 마감 시간을 타임스탬프 형식으로 변환하여 저장한다. 2. .. 2024. 2. 23.
[백준 1012번] 유기농 배추 - 파이썬 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 💡문제 분석 요약 배추 밭에 배추가 심어진 부분과 심어지지 않은 부분이 있다. 배추가 심어진 부분은 연결되어 있으면 배추흰지렁이가 한마리만 있어도 된다. 배추흰지렁이는 총 몇마리가 필요한가? 💡알고리즘 설계 DFS를 이용하여 배추밭을 탐색하고, 더이상 배추가 없으면 배추흰지렁이의 개수를 추가한다. 1. 테스트 케이스의 개수를 입력받는다 2. 테스트 케이스만큼 배추밭의 크기와 배추의 개수를 입력받는다. 3. 배.. 2024. 2. 23.
[백준 6603번] 로또 - 파이썬 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 💡문제 분석 요약 집합 S가 주어졌을 때, 숫자를 사전순으로 k개를 만들 수 있는 모든 경우를 출력한다. 💡알고리즘 설계 DFS 문제이다. 1. 입력받은 값이 0일 때 까지 계속 입력받고 dfs를 실행한다 2. 실행 횟수(재귀의 깊이, 현재 숫자의 개수)가 6을 넘어가면 숫자를 출력하고 리턴한다 3. 현재 숫자에서 마지막 숫자까지, 숫자를 추가하고 dfs를 한 후 값이 리턴되면 추가했던.. 2024. 2. 17.
[백준 1541번] 잃어버린 괄호 - 파이썬 https://www.acmicpc.net/problem/1541 💡문제 분석 요약 식에서 괄호를 적절히 쳐서 식의 값을 최소로 구하라. 55-50+40은 55-(50+40)으로 만들어 -45가 된다. 💡알고리즘 설계 1. 식을 입력받는다 -> 55-50+40 2. '-'를 기준으로 식을 분할한다. -> 55-(50+40) 2. 나누어진 식을 '+'을 기준으로 나누고, + 연산을 한다. -> 55-(90) 3. + 연산이 끝난 숫자를 sum에서 뺀다. -> -45 처음 나오는 숫자는 음수가 아니라 양수이므로 덧셈을 한다. 💡코드 import sys input = sys.stdin.readline expression=input().rstrip() numbers=expression.split('-') res.. 2024. 2. 17.
[백준 16967] 배열 복원하기 - 파이썬 https://www.acmicpc.net/problem/16967💡문제 분석 요약X칸, Y칸 씩 밀려 겹쳐진 배열을 보고 원래 배열을 구한다.💡알고리즘 설계1. 원래 배열 A를 0으로 초기화한다 2. A를 B에서 같은 위치에서 복사한다 3. X칸, Y칸씩 슬라이딩 된 위치에 B에서 A의 값을 뺀 값을 저장한다 💡코드import sys input = sys.stdin.readline H, W, X, Y = map(int, input().split()) B=[] for i in range(0,H + X): B_row = list(map(int, input().split())) B.append(B_row) #1. A를 0으로 초기화 A= [[0 for j in range(W)] for i in range(H.. 2024. 2. 10.
[백준 11724] 연결 요소의 개수 - 파이썬 https://www.acmicpc.net/problem/11724 💡문제 분석 요약 방향없는 그래프가 주어졌을 때, 연결 요소의 개수를 구하라 💡알고리즘 설계 1. 그래프를 연결리스트로 저장한다. 2. 그래프에 저장된 노드를 하나씩 방문한다. 2-1. 하나의 노드에 연결된 노드들을 연결 리스트로 저장하여, 해당 노드에 연결된 노드들 중 방문하지 않은 노드를 차례로 방문한다. 2-2. dfs 함수가 더이상 호출되지 않고 끝나면 연결 요소를 모두 찾은 것이므로, 함수 호출이 끝나 연결되지 않은 다음 노드를 방문하게 되면 카운트를 하나 더하고 새 연결 요소 방문을 시작한다. 💡코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) N, M.. 2024. 2. 10.
[백준 11478번] 서로 다른 부분 문자열의 개수 - 파이썬 https://www.acmicpc.net/problem/11478💡문제 분석 요약문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오. 부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다. 💡알고리즘 설계for문을 이용해 첫번째 문자로 시작하는 문자열, 두번째 문자로 시작하는 문자열 등을 순서대로 구하여 set에 추가한다. 중복처리를 위해 set을 이용하고, set의 크기에서 1을 뺀 값을 리턴한다. 💡코드S= input() len_S=len.. 2024. 2. 3.

티스토리툴바