본문 바로가기

전체 글132

1789번, 3085번 - 브루트포스 실버 저티어 문제로 두문제를 풀었다. 1789 - 수들의 합서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 즉, 자연수 N보다 같거나 커질때까지 1부터 더해가는 문제이다.쉬운 문제이기에 두가지 방법으로 풀어보았다.1. 단순 반복문import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long S = sc.nextLong(); int count = 0; int num = 1; while (S > 0) { S -= .. 2024. 7. 16.
2252번 - 줄세우기(bfs) 줄 세우기라는 골드 2티어 문제를 풀었다.한번에 풀진 않았지만 어려운 문제는 아니였고, bfs를 사용하는 문제이다.다음과 같은 입력값이 주어진다.3 21 32 3첫줄의 첫 숫자(N)는 학생이 몇 명인지, 두번째 숫자(M)는 몇개의 줄에 대한 정보가 주어질 것인지 나타낸다.다음 M 개의 줄동안 입력이 주어지는데, 이는 학생의 위치를 의미한다.즉 위의 보기에서는 1번 학생 뒤에 3번 학생, 2번 학생 뒤에 3번 학생이 온다는 의미이다. 처음에는 너무 복잡하게 생각한 나머지 틀리고 말았다.누구 앞에 누가있는지, 누구 뒤에 누가 있는지 둘다 고려를 해버렸다.결국 틀린 코드를 오래동안 작성했고, 아래는 틀린 보기이다.더보기더보기public class 줄세우기_2252번_오답 { static int N, M;.. 2024. 7. 11.
16916번 - 부분문자열(KMP 알고리즘, 실패함수) 16916번: 부분 문자열 (acmicpc.net)골드 4티어 문제이며, 문자열 P 가 문자열 S의 부분문자열인지 알아보는 문제이다.처음에는 일단 직관대로 문제를 풀어보았으나 시간 초과가 되었다..Java에서 지원하는 contains를 이용한 풀이이다.더보기더보기public class 부분문자열_16916번_시간초과 { static String S, P; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); S = br.readLine(); P = br.readLine();.. 2024. 7. 10.
1197번 - 최소 스패닝 트리(Prim 알고리즘) 1197번: 최소 스패닝 트리 (acmicpc.net) 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 예제입력3 31 2 12 3 21 3 3 처음에는 트리라는 것을 생각하지 않고, 하나의 경로라는 생각을 했다.시작점이 다를때 다른 결과가 나올거라는 잘못된 생각을 하게되어 아래처럼 시간복잡도가 큰 코드가 짜여지게 되었다.더보기import jav.. 2024. 7. 8.

티스토리툴바