본문 바로가기

백준

 (88)
백준 16938 캠프 준비(파이썬) https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 풀이 주어지는 입력은 N, L, R, X와 문제의 난이도인 A이다. 이때 문제에서 주어진 조건은 두 개이다. 1. 문제 난이도의 합은 L이상 R이하이다. 2. 문제 난이도의 가장 큰 편자는 X이하이다. 위의 조건을 그대로 파이썬에서 구현하기 위해 itertools.combinations를 사용하면 된다. 문제를 풀기위한 로직은 다음과 같다. 문제들의 난이도를 모아놓은 A리스트에서 itertools.combinations를 사용해서 2부터 N개만큼 원소를 뽑아 a라는 리스트에 담는다. a에 속한 원소들의 합이 ..
백준 15486 이진수 덧셈(파이썬) https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 모든 경우를 고려했을때 최댓값을 구하라는 것 문제의 요구사항에 따라서 DP문제임을 알 수 있다. 나는 특정일에 얻을 수 있는 최대 이익을 구하는데 집중을 하였다. 먼저 특정일에 주어진 일을 기간안에 완수할수 있는지 없는지를 확인하여야 한다. 그렇기에 특정 일에 주어진 일을 마무리 할 수 있는 날을 구한다. fin_date = idx + T[idx] - 1 이후 ..
백준 2812 크게 만들기 (파이썬) https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 숫자를 지웠을때 만들수있는 수 가운데 가장 큰 수를 만들어야 하는 문제이다. 이 문제는 그리디 문제로 일종의 규칙을 발견하는 것이 중요하다. 입력 예제로 주어진 값들을 직접 지우다 보면 다음과 같은 규칙들을 발견할 수 있다. 순서 예제 입력1 예제 입력2 예제 입력3 1 1924 1231234 4177252841 2 924 231234 477252841 3 94 31234 77252841 3234 7752841 775841 값을 지우다 보면 idx의 값과 idx+1의 ..
백준 1212 8진수 2진수 (파이썬) https://www.acmicpc.net/problem/1212 1212번: 8진수 2진수 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. www.acmicpc.net 문제 풀이 이 문제는 파이썬의 bin, int함수에 대해서 알고 있으면 쉽게 해결되는 문제이다. bin(문자열)을 넣으면 2진수로 반환해주고 int는 첫번째 인자에는 문자열을 넣어주고 두번째 인자에는 첫번째 인자의 진수를 적어준다. (기본값은 10진수) 코드 def solution(x): ans = int(x, 8) print(bin(ans)[2:]) solution(input())
백준 20053 최소, 최대 2 (파이썬) https://www.acmicpc.net/problem/20053 20053번: 최소, 최대 2 N개의 정수가 주어진다. 이때, 최솟값과 최댓값을 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 문제에서 요구하는대로 각 테스트 케이스 별로 코드를 작성하면된다. 먼저 테스트 케이스의 수를 받고 그 다음 해당 테스트케이스에서 값의 수만큼 반복을 해서 리스트를 만들고 해당 리스트의 최대 최소 값을 출력 하면 된다. 코드 def solution(): T = int(input()) answer = [[] for _ in range(T)] for t in range(T): N = int(input()) ary = list(map(int, input().split(' '))) answer[t].ap..
백준 5597 과제 안 내신 분..? (파이썬) https://www.acmicpc.net/problem/5597 5597번: 과제 안 내신 분..? X대학 M교수님은 프로그래밍 수업을 맡고 있다. 교실엔 학생이 30명이 있는데, 학생 명부엔 각 학생별로 1번부터 30번까지 출석번호가 붙어 있다. 교수님이 내준 특별과제를 28명이 제출했는데, www.acmicpc.net 풀이 list.remove()를 알면 바로 풀리는 문제이다. 나는 미리 입력에 대해서 함수를 통해서 받고 문제를 해결하는 로직을 나누어서 풀었다. 코드 def pre(): x = [] for i in range(28): x.append(int(input())) return x def solution(x): ans = [_ for _ in range(1, 31)] for element ..
[백준] 2753 윤년 (파이썬) https://www.acmicpc.net/problem/2753 2753번: 윤년 연도가 주어졌을 때, 윤년이면 1, 아니면 0을 출력하는 프로그램을 작성하시오. 윤년은 연도가 4의 배수이면서, 100의 배수가 아닐 때 또는 400의 배수일 때이다. 예를 들어, 2012년은 4의 배수이면서 www.acmicpc.net 풀이 파이썬의 기초적인 문법을 물어보는 문제이다. 나는 프로그래머스의 문제를 풀듯이 함수를 만들어서 해결하였다 코드 def solution(year): # 4의 배수이면서, 100의 배수가 아닐 때 또는 400의 배수일 때이다. if ((year%4 == 0) and (year%100 != 0)) or (year%400==0) : return 1 return 0 year = int(inp..
[백준] 바이러스 2606 파이썬 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 설명 해당 문제는 단순히 그래프탐색을 해서 방문 가능한 노드가 총 몇개인지 확인하는 문제였다. 나는 이전에 DFS, BFS문제를 n x n으로 취급해서 문제를 풀었으나 그렇게 하면 시간복잡도가 상당히 높아지기에 인접리스트꼴로 문제를 풀었다. from collections import deque def bfs(graph, visit): q = deque() q.append(1) visit[1] = ..
[백준] 1260 DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 설명 문제는 기본적인 DFS와 BFS를 물어보는 문제이다. 이미 이전에도 풀어본 적이 있지만 코딩테스트용 언어를 변경했기에 처음부터 시작한다는 마음으로 시도하고 있다. 문제 자체의 난이도는 크게 높지 않다. 코드에 주석을 달아놓았기에 재귀함수나 큐에 대한 지식이 있다면 크게 문제되지 않을 것이다. 코드 from collections import deque..
백준 17128 소가 정보섬에 올라온 이유(JAVA) 문제 https://www.acmicpc.net/problem/17128 17128번: 소가 정보섬에 올라온 이유 첫째 줄에 소의 수를 나타내는 N과 욱제가 장난칠 횟수 Q가 주어진다. (4 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000) 둘째 줄에 N마리 소들의 품질 점수 Ai가 순서대로 주어진다. (1 ≤ |Ai| ≤ 10) 셋째 줄에 www.acmicpc.net 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static v..

티스토리툴바