본문 바로가기

백준 문제풀이 코드저장소

 (99)
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..
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):..
Baekjoon 17386. 선분 교차 1 / Python 알고리즘 설명문제 설명2-D 좌표평면 위에 두 선분이 교차하는지를 확인하는 문제코드 설명CCW 알고리즘을 이용하여 두 선분의 교차여부를 확인한다CCW 알고리즘세 점이 주어졌을 때, 점 A에서 B를 바라 보는 방향을 기준으로 점 C가 시계방향에 있는지, 반시계방향에 있는지를 확인하는 알고리즘CCW(A, B, C) = (Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)CCW함수의 값이양수이면 반시계방향음수이면 시계방향0이면 일직선 상에 있음을 나타냄두 선분의 교차여부 확인두 선분 L1(A1, A2), L2(B1, B2)가 있을 때두 선분이 일직선 상에 있어서 겹치는 경우CCW(A1, A2, B1) * CCW(A1, A2, B2) import sysinput = sys.stdin..
Baekjoon 7579. 앱 / Python https://www.acmicpc.net/problem/7579알고리즘 설명문제 설명앱을 비활성화하기 위한 최소 비용으로 메모리를 확보해야한다.DP를 활용하여 풀이했다.코드 설명dp[i][j] : i번째 앱까지 고려했을 때, j의 비용으로 확보할 수 있는 최대 메모리필요한 메모리를 확보했을 경우 최소 비용을 갱신import sysinput = sys.stdin.readline# 입력n, m = map(int, input().split())memories = [0] + list(map(int, input().split())) # 앱들이 사용하는 메모리costs = [0] + list(map(int, input().split())) # 앱들을 비활성화하는 비용# DP 테이블 초기화# dp[i][j]: ..
Baekjoon 9466. 텀 프로젝트 / Python https://www.acmicpc.net/problem/9466알고리즘 설명문제 설명학생들을 그룹으로 묶어야 한다.그룹의 학생들은 한명이거나, 싸이클을 생성해야한다.코드 설명임의의 학생을 기준으로 간선을 따라간다.처음의 학생을 기록하는 방법이 아니라, 간선을 따라간 다음 학생이 그룹 내부에 있는지를 확인하는 방법으로 사이클을 확인한다.import syssys.setrecursionlimit(10**6) input = sys.stdin.readline# 재귀 함수로 학생들을 방문하면서 팀을 구성할 수 있는지 확인def sol(x): global res visit[x] = 1 # 현재 학생을 방문 표시 tmp.append(x) # 현재 학생을 임시 리스트에 추가 if visit[a..
Baekjoon 4948. 베르트랑 공준 / Java 알고리즘 설명문제 설명임의의 자연수 n에 대하여 n보다 크고 2n보다 작은 소수가 적어도 하나 존재한다.n보다 크고 2n보다 작은 소수의 개수를 구하는 문제알고리즘 설명isPrime : n의 최댓값 * 2 까지 소수판별을 한다. 이 때, 에라토스테네스의 체를 사용한다. 시간복잡도 : O(n log n)countPrime배열에 소수 개수를 저장한다. 시간복잡도 O(n)import java.io.*;public class Main { public static int n; // 소수 판별 배열, true이면 소수가 아님 public static boolean[] isPrime = new boolean[123456 * 2 + 1]; // 소수 개수를 누적합으로 저장하는 배열 publi..
Baekjoon 1912. 연속합 / Java https://www.acmicpc.net/problem/1912알고리즘 설명문제 설명주어진 수열에서 연속된 부분 수열의 합 중 가장 큰 합을 찾는 문제코드 설명dp를 활용하여 수열의 최대 부분합을 저장한다.dp[x] 는 x 위치까지 최대 부분합을 저장한다.dp[x] 는 dp[x-1] + arr[x], arr[x] 중의 큰 값이 된다.dp를 활용하여 시간복잡도를 O(n) 으로 해결할 수 있다.import java.io.*;import java.util.StringTokenizer;public class Main { public static int n; public static int[] arr; // 각 위치에서의 최대 부분합을 저장할 배열 public static int[]..
Baekjoon 30804. 과일 탕후루 / Java, Python 알고리즘 설명문제 설명과일 길이의 최댓값을 구한다. 단, 과일 종류는 두 종류 이하여야 한다.과일은 앞, 뒤에서만 뺄 수 있다.코드 설명left, right를 증가시키며 최대 길이를 찾는 투포인터 알고리즘 방식을 적용했다.과일의 종류가 9개밖에 안되므로 kind 배열을 사용해서 과일마다 몇개가 들어있는지를 계산했다.최대 길이를 찾은 경우 -> 포인터 사이의 길이를 줄이면서 탐색하지 않는다, 즉 왼쪽을 한칸 당길 때, 오른쪽도 같이 당긴다.import java.io.*;public class Main { public static BufferedReader br; public static int n; // 과일의 수 public static int[] arr; // 과일의 배열상태 저장 ..
Baekjoon 4386. 별자리 만들기 / Python 알고리즘 설명문제 설명모든 별을 잇는 최소 비용 구하기코드 설명최소신장트리를 찾는 문제이다.간선의 가중치를 기준으로 정렬union-find 알고리즘을 사용해서 사이클이 없도록 간선을 추가시간 복잡도 : O(n ^ 2 log n)n의 최댓값이 100이므로, 충분히 효율적.import sysimport mathinput = sys.stdin.readline# Union-Find (Disjoint Set) 구조 정의def union_find(x): if parents[x] == x: return x parents[x] = union_find(parents[x]) return parents[x]def union_set(x, y): rootX, rootY = union_find(..

티스토리툴바