전체 글

[백준] 1958번 : LCS 3 Gold4(골드4) - JAVA[자바]

[Gold IV] LCS 3 - 1958문제 링크성능 요약메모리: 17568 KB, 시간: 132 ms분류다이나믹 프로그래밍, 문자열제출 일자2024년 6월 21일 15:47:06문제 설명문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다.이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라.입력첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100..

[백준] 18513번 : 샘터 Gold4(골드4) - JAVA[자바]

[Gold IV] 샘터 - 18513문제 링크성능 요약메모리: 57152 KB, 시간: 428 ms분류너비 우선 탐색, 자료 구조, 그래프 이론, 그래프 탐색제출 일자2024년 6월 19일 14:39:39문제 설명일직선 상의 공간에 N개의 샘터가 존재하며, K채의 집을 짓고자 한다. 모든 샘터 및 집이 존재하는 위치는 항상 정수 형태이다. 이때 일직선 상의 공간에서 N개의 샘터 및 K채의 집들은 모두 서로 다른 위치에 존재한다. 다시 말해 하나의 위치에는 샘터가 있거나, 집이 있거나, 혹은 아무것도 없다.K채의 집을 지을 때, 가능하면 샘터의 주변에 집들을 지어서 K채의 모든 집에 대한 불행도의 합이 최소가 되도록 짓고자 한다. 이때 특정한 집에 대한 불행도란, 가장 가까운 샘터까지의 거리(Distanc..

[백준] 14391번 : 종이 조각 Gold3(골드3) - JAVA[자바]

[Gold III] 종이 조각 - 14391문제 링크성능 요약메모리: 17160 KB, 시간: 88 ms분류비트마스킹, 브루트포스 알고리즘제출 일자2024년 6월 19일 15:48:05문제 설명영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다...

[백준] 14284번 : 간선 이어가기2 Gold5(골드5) - JAVA[자바]

[Gold V] 간선 이어가기 2 - 14284문제 링크성능 요약메모리: 43776 KB, 시간: 356 ms분류데이크스트라, 그래프 이론, 최단 경로제출 일자2024년 6월 18일 20:28:14문제 설명정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다.s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가하는 간선의 순서를 조정할 때, 그 최솟값을 구하시오.입력첫째 줄에 정점의 개수 n, 간선리스트의 간선 수 m이 주..

[백준] 2374번 : 같은 수로 만들기 Gold4(골드4) - JAVA[자바]

[Gold IV] 같은 수로 만들기 - 2374문제 링크성능 요약메모리: 11832 KB, 시간: 72 ms분류자료 구조, 그리디 알고리즘, 스택제출 일자2024년 6월 18일 21:43:46문제 설명n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수의 그룹이 한번에 1씩 증가한다. A[1]과 A[n]은 인접해 있지 않다.예를 들어 수가 {1, 1, 1, 1, 3, 3, 1} 이었다고 해 보자. Add(2)를 하면 A[2]의 좌우로 인접한 같은 수가 1씩 증가하니까 {2, 2, 2, 2, 3, 3, 1}이 된다. 여..

[백준] 10282번 : 해킹 Gold4(골드4) - JAVA[자바]

[Gold IV] 해킹 - 10282문제 링크성능 요약메모리: 151944 KB, 시간: 860 ms분류데이크스트라, 그래프 이론, 최단 경로제출 일자2024년 6월 18일 00:56:54문제 설명최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트..

[백준] 1253번 : 좋다 Gold4(골드4) - JAVA[자바]

[Gold IV] 좋다 - 1253문제 링크성능 요약메모리: 12688 KB, 시간: 124 ms분류이분 탐색, 자료 구조, 정렬, 두 포인터제출 일자2024년 6월 18일 00:30:07문제 설명N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.수의 위치가 다르면 값이 같아도 다른 수이다.입력첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)출력좋은 수의 개수를 첫 번째 줄에 출력한다. 접근 방법1. 각 값에 대하여 투 포인터를 사용하기 위해서 정렬한다.(n ..

[백준] 14731번 : 謎紛芥索紀 (Large) Silver1(실버1) - JAVA[자바]

[Silver I] 謎紛芥索紀 (Large) - 14731문제 링크성능 요약메모리: 37048 KB, 시간: 292 ms분류미적분학, 분할 정복을 이용한 거듭제곱, 수학제출 일자2024년 6월 17일 23:59:48문제 설명성민이는 이번 학기에 미적분학 과목을 수강하고 있다. 다항함수의 미분 단원 과제를 하던 도중 미분을 하기가 귀찮아진 성민이는 미분하려는 함수 f(x)가 주어지면, 미분 된 함수 f’(x)를 자동으로 구해주는 프로그램을 만들어서 계산을 줄일 생각을 하였다. 우리도 성민이가 원하는 프로그램을 한번 같이 만들어보도록 하자.입력첫째 줄에는 항의 개수 N(1 ≤ N ≤ 100000)이 주어진다.둘째 줄부터 N개 줄에 걸쳐서 항의 계수 C(0 )와 항의 차수 K(0 ≤ K ≤ 109)가 항의 차..