본문 바로가기

전체 글

 (147)
Baekjoon 1238. 파티 / Python https://www.acmicpc.net/problem/1238알고리즘 설명문제 설명단방향 그래프에서 최단경로를 찾는 문제최단 경로의 값을 모두 구하고 그 중에 최댓값을 찾는다.코드 설명사람 별로 파티장까지 갔다가 돌아오는 길의 최단경로를 찾는다.최단경로의 경로길이들의 최댓값을 갱신한다.import sysfrom heapq import heappop, heappushinput = sys.stdin.readlineinf = 1e10n, m, x = map(int, input().split())arr = [[] for _ in range(n + 1)]# 최단경로구하기def sol(start, end): dp = [inf for _ in range(n + 1)] dp[start] = 0 q ..
Baekjoon 23295. 스터디 시간 정하기 1 / Python https://www.acmicpc.net/problem/23295알고리즘 설명문제 설명주어진 스터디 시간에 사람들이 가장 많이 참여할 수 있는 시간 구간을 찾는 문제코드 설명슬라이딩 윈도우 알고리즘을 이용한 문제 풀이T 시간 간격으로 포인터를 이동시키면서 최대 만족도가 나온 경우 시작시간과 끝나는 시간을 갱신하는 방법import sysinput = sys.stdin.readlinen, t = map(int, input().split()) # 참가자 수 n 스터디 시간 tsummation = [0] * 100002 # 시간 범위를 저장할 배열end = 0 for i in range(n): k = int(input()) # 현재 참가자가 가능한 시간 구간의 수 k for j in ran..
Baekjoon 11779. 최소비용 구하기 2 / Python https://www.acmicpc.net/problem/11779알고리즘 설명문제 설명노드들이 주어지고 노드들 사이의 가중치가 주어졌을 때, 임의의 노드에서 다른 임의의 노드로 이동하는데 걸리는 최소 비용을 구하는 문제코드 설명다익스트라 알고리즘우선순위 큐를 사용하여 최단 경로를 탐색한다.주어진 시작점에서부터 시작하여 각 도시에 대한 최단 경로를 찾는다.각 도시 now에서 인접한 도시 next로 가는 비용 tmp를 더한 값이 현재 저장된 최소 비용보다 작으면 갱신하고 큐에 추가한다.dp[end][0] : 도착 도시까지의 최소 비용len(dp[end][1]) : 경로에 포함된 도시의 개수dp[end][1] : 최소 비용을 갖는 경로from heapq import heappop, heappush # 최소비..
Baekjoon 1069. 집으로 / Pyhton https://www.acmicpc.net/problem/1069알고리즘 설명문제 설명점프와 걷기를 이용해서 주어진 위치에서 원점으로 돌아가는데 필요한 최소 시간을 구하는 문제코드 설명걷기만 하는 경우점프를 한 후에 걷는 경우뒤로 조금 걸어간 후 점프를 하는 경우 -> 점프가 효율적이어서 점프 칸 수를 맞추기 위한 뒷걸음import math# 입력 받기x, y, d, t = map(int, input().split())# 유클리드 거리 계산dist = (x ** 2 + y ** 2) ** 0.5# 점프 횟수 계산jump = dist // d# 점프를 포함한 최단 시간 계산if dist >= d: tmp1 = t * jump + (dist - (d * jump)) tmp2 = t * (jump ..
Baekjoon 11478. 서로 다른 문자열의 개수 / Java https://www.acmicpc.net/problem/11478알고리즘 설명문제 설명문자열의 서로 다른 '부분 문자열'의 개수를 구하는 문제코드 설명모든 부분 문자열을 생성하고 집합자료구조에 부분문자열을 저장했다.집합은 중복을 허용하지 않으므로, 집합의 크기가 문제의 답이 된다.import java.io.*;import java.util.*;public class Main { public static String s; public static BufferedReader br; public static Set arr; public static int res; public static void main(String[] args) throws IOException { ..
Baekjoon 16951. 블록 놀이 / Java https://www.acmicpc.net/problem/16951알고리즘 설명문제 설명각기 다른 높이를 가진 배열을 높이 차를 k로 만드는 문제코드 설명한 번에 몇개를 옮기든 하나의 블록의 높이를 바꾸는 시간은 동일하기 때문에, 하나의 블록을 고정해 놓고 완전 탐색을 하면 된다.n ㄴimport java.io.*;import java.util.StringTokenizer;public class Main { public static int n; public static int k; public static int[] arr; public static int answer = Integer.MAX_VALUE; public static void main(String[] args) t..
Baekjoon 21966. (중략) / Java https://www.acmicpc.net/problem/21966알고리즘 설명문제 설명입력 길이가 25 이하인 경우:문자열 SSS를 그대로 출력합니다.입력 길이가 25 초과인 경우:SSS의 앞에서부터 11글자, 뒤에서부터 11글자를 제외한 나머지 부분이 모두 같은 문장에 속한다면, 생략한 부분을 '...'으로 바꿔서 출력합니다.그렇지 않다면, SSS를 앞에서부터 9글자, 뒤에서부터 10글자만 남기고 중간을 '......'으로 바꿔서 출력합니다.코드 설명메서드 활용해서 풀자.import java.io.*;public class Main { public static int N; public static String s; public static String res = ""; publi..
01. 01 파이썬이란???? 파이썬이란??파이썬은 인터프리터 프로그래밍 언어이다.인터프리터 언어는 컴파일러 언어와 달리 컴파일 과정 없이 바로 실행할 수 있다는 특징이 있다.직관적이고 쉬운 문법과 다양하고 풍부한 라이브러리들을 바탕으로, 프로그래밍 교육, 인공지능, 데이터분석 및 빅데이터, 백엔드, 프론트엔드 등 다양한 분야에서 사용되고 있다.파이썬의 사용성과 인기파이썬은 배우기 쉽고 간결한 문법 덕분에 입문자에게 적합한 언어이다. 또한, 다양한 분야에서 활용할 수 있는 라이브러리와 프레임워크가 풍부하여 전문가들도 많이 사용한다. 특히 데이터 과학, 인공지능, 웹 개발 등에서 높은 인기를 끌고 있다.TIOBE Index 기준 근 5년간 프로그래밍 언어 순위 1순위이다.파이썬의 특징 / 사용하는 이유파이썬의 주요 특징 중 하나는 가독..
Baekjoon 2252. 줄 세우기 / Python 알고리즘 설명문제 설명n명의 학생들을 키 순서대로 줄을 세우는 문제학생들의 키가 나와있지 않고, 키의 비교가 주어진다.코드 설명위상 정렬 알고리즘각 학생의 뒤에 있어야할 학생의 리스트와 각 학생의 앞에 있어야 할 학생 수 리스트를 만든다.학생의 앞에 있어야 할 학생 수가 0인 학생들을 큐에 넣고 위상정렬을 진행한다.반복import sysfrom collections import dequeinput = sys.stdin.readline# 입력 처리n, m = map(int, input().split())behind = [[] for _ in range(n + 1)]front = [0] * (n + 1)# 그래프 구성for _ in range(m): a, b = map(int, input().split..
Baekjoon 1644. 소수의 연속합 / Python 알고리즘 설명문제 설명자연수 n 이 주어질 때, n을 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제코드 설명n이하의 모든 소수를 찾는다. (에라토스테네스의 체를 이용)찾은 소수들을 투 포인터를 이용하여 연속된 소수의 합으로 n을 나타낼 수 있는 경우를 찾는다.import mathn = int(input())# n이 1인 경우 소수의 합으로 나타낼 수 없으므로 0 출력 후 종료if n == 1: print(0) exit(0)# 에라토스테네스의 체 초기화arr = [1] * (n + 1)arr[0] = arr[1] = 0 # 0과 1은 소수가 아니므로 0으로 설정# 에라토스테네스의 체를 사용하여 소수 판별for i in range(2, int(n**0.5) + 1):..

티스토리툴바