본문 바로가기

백준 문제풀이 코드저장소

(87)
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(..
Baekjoon 2473. 세 용액 / Python 알고리즘 설명문제 설명서로 다른 세 개의 용액의 값의 합이 0에 가장 가까운 경우를 찾는다.코드 설명용액들을 정렬한다.중간 포인터를 모든 인덱스를 순회하면서, 첫 번째 인덱스와 마지막 인덱스를 이동시키면서 투 포인터 방식으로 값을 찾는다.시간복잡도 : 정렬 O(n log n) + 투포인터 O(n ^ 2)import sysinput = sys.stdin.readlinen = int(input())arr = sorted(list(map(int, input().split())))# 초기값을 무한대로 설정min_sum = float('inf')result = []# i는 첫 번째 용액을 선택하는 인덱스for i in range(n - 2): s, e = i + 1, n - 1 while s ..
Baekjoon 2533. 사회망 서비스 (SNS) / Python 알고리즘 설명문제 설명모든 사람은 얼리 어답터이거나 얼이 어답터와 연결되어 있어야 한다.이 때, 얼리 어답터의 최소 수를 구하는 문제코드 설명dp배열을 활용한다2차원 배열을 사용하며 dp[a][0]은 노드 a 가 얼리어답터가 아닐 때의 얼리 어답터 수, dp[a][1]은 노드 a 가 얼리어답터일 때의 얼리 어답터 수를 나타낸다.시간 복잡도 : O(n ^ 2)from collections import deque as dqimport sysinput = sys.stdin.readlinen = int(input())edges = [tuple(map(int, input().split())) for _ in range(n - 1)]# 인접 리스트 초기화arr = [[] for _ in range(n + 1)]fo..