'알고리즘' 태그의 글 목록

2024. 6. 5. 15:05 Algorism/백준

https://www.acmicpc.net/problem/1515 문제 약간의 그리디 알고리즘을 가미한 구현문제이다. 입력으로 주어지는 수는 3000자리이고 0~9까지는 10개이다. 3000 * 10 = 30000 이내에서 2초동안 모두 찾을 수 있다. 입력값 290119으로 예시를 들겠다. 이 문자열의 문자마다 위치를 가르키는 index가 있다. 그리고 1 부터 시작하는 값 Num의 각자리수와 비교를 해준다. Num이 2일때를 생각해보자. 이때의 index는 0이다. 290119의 0의 인덱스 위치는 2이다. Num과 인덱스 위치의 값이 같기 때문에 index를 증가시킨다. (index = 1) 이후 Num이 9일때도 마찬가지로 index를 증가시킨다. (index = 2) 그다음 Num이 10일때는..

[백준] 21921번 : 블로그 - JAVA [자바]

2024. 6. 4. 16:33 Algorism/백준

https://www.acmicpc.net/problem/21921 문제 위 문제는 N이 250,000 이하의 값을 가지기 때문에 O(N*N) 형식의 완전탐색으로 푼다면 시간 초과가 걸릴 것이다.X의 기간은 항상 값을 유지하기 때문에 이를 슬라이딩 윈도우 아이디어로 풀면 되겠다는 생각을 했다. X의 값만큼의 윈도우를 설정하고 한칸씩 밀어버리는 방법이다.이렇게 푼다면 O(N)으로 풀 수 있다. 윈도우 범위와 인덱스의 위치등 값만 신경써서 해주면 된다. 전체 코드public class Main { public static void main(String[] args) throws Exception { System.setIn(new FileInputStream("./input.txt")); ..

[백준] 2512번 : 예산 - JAVA [자바]

2024. 6. 4. 15:40 Algorism/백준

https://www.acmicpc.net/problem/2512문제 위 문제는 단순하다. 하지만 N의 범위가 10,000일 경우에는 완전 탐색으로 풀었을 경우 1초가 넘어가게 된다. 그래서 완전탐색이 아닌 O(logn)으로 풀 수있는 이분탐색을 활용했다. 풀이는 O(nlogn)이다. 풀이는 아래와 같이 진행된다. 1. 입력값을 받는다.2. 이분탐색을 위한 배열 정렬을 오름차순으로 진행한다.3. left, right의 적절한 값을 넣어서 범위를 지정한다.4. 루프를 돌면서 중간값을 계산하고, 루프 내에서 배열을 완전 탐색해서 mid의 값이 넘어가면 총합에 mid를 더하고, 아니면 배열값 자체를 더한다.5. 구해진 총합을 M과 비교해서 적절하게 left, right를 조절한다.6. 루프가 끝나게 되면 ri..

[백준] 20040번 : 사이클 게임 - JAVA [자바]

2024. 1. 5. 11:59 Algorism/백준

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 문제 이 문제는 유니온파인드로 풀 수 있다. 문제가 요구하는 것은 간단하다. 그래프(집합)을 형성할때, 만약 사이클이 발생한다면, 그 차례의 수를 출력하는 것이다. 생각을 해보자 사이클은 언제 발생 될까? 두개의 점을 그래프를 연결하기전에 이미 두개의 점들의 대표자가 같다면 싸이클이다. - 그림을 그려보면 쉽게 알 수 있다. 아래는 실제로 풀면서 내가 그린 그림이다. 이점을 이용해서 유니온파..

[백준] 1717번 : 집합의 표현 - JAVA [자바]

2024. 1. 5. 11:53 Algorism/백준

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 문제 이 문제는 유니온파인드의 기초문제라고 할 수 있다. 유니온 파인드를 모른다?! 바로 아래 포스팅을 먼저 보고오자. https://bean-conding.tistory.com/19 알고리즘 - 유니온파인드, 서로소집합 (Unionfind) 서로소 집합에 대한 알고리즘인 유니온파인드를 계속 까먹고, 다른 포스트에서 보면 다양한 방식이 있어, 그때 그때 찾고 ..

[백준] 11060번 : 점프 점프 - JAVA [자바]

2024. 1. 3. 16:16 Algorism/백준

https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 문제 위 문제는 DP 풀이법으로 풀었다. 아래의 문제와 유사하다. https://bean-conding.tistory.com/16 [백준] 11048번 : 이동하기- JAVA [자바] https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다...

[백준] 11048번 : 이동하기- JAVA [자바]

2024. 1. 3. 15:38 Algorism/백준

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 문제 이 문제는 DP의 Memonization을 이용하여 풀었다. 문제는 간단하다 (1, 1) 좌표에서 시작하여 (N, M) 좌표까지 이동하면서 사탕을 먹으면서 간다. 방향은 3가지로 아래, 오른쪽, 오른쪽 아래 대각선을 이동할 수 있다. DP의 기본적인 문제라고 생각한다. 왜냐하면 특별한 점화식이 필요없기 때문이다 나의 로직은 아래와 같다. (1, 1) 좌표에서 내가 갈 수 있는 ..

[백준] 5014번 : 스타트링크 - JAVA [자바]

2024. 1. 2. 19:57 Algorism/백준

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 이 문제는 BFS로 쉽게? 풀었다. 로직은 아래와 같다. 1. Route 클래스를 저장하는 Queue를 생성한다. 2. Queue에 초기값인 현재층수와 버튼을 누룬횟수인 0을 넣는다. 3. BFS을 돌면서 아래의 조건을 만족하면 Queue에 다음층을 넣는다. 다음 층이 F층 위에 있거나, 1층 밑이면 Continue 다음 층이 만약 방문한 층이면 Continue 다음 층이 만약 목적지에 도착한다면 Ret..

[백준] 14225번 : 부분수열의 합 - JAVA [자바]

2024. 1. 2. 14:12 Algorism/백준

https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 문제 아래 문제를 풀면서 부분집합을 비트마스킹으로 더 풀고 싶었고 부분집합 문제를 풀기위해 이 문제를 풀었다. https://bean-conding.tistory.com/12 [백준] 15661번 : 링크와 스타트 - JAVA [자바] https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트..

[백준] 15661번 : 링크와 스타트 - JAVA [자바]

2024. 1. 2. 11:27 Algorism/백준

https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 문제 이 문제는 실버1 스타트와 링크의 후속 문제이다. 아래의 글을 먼저 보고오면 편하다. https://bean-conding.tistory.com/10 [백준] 14889번 : 스타트와 링크 - JAVA [자바] https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2..

티스토리툴바