전체 글
-
BJ 7523. Gauß https://www.acmicpc.net/problem/7523 7523번: Gauß 각 테스트 케이스마다 "Scenario #i:"를 출력한 다음, n부터 m까지 모든 정수의 합을 출력한다. 각 테스트 케이스 사이에는 빈 줄을 하나 출력한다. www.acmicpc.net 생각 왜 시간 복잡도에 대한 고려가 필요한지 살펴보는 문제이다. 간단한 구간 더하기 이므로 for 문을 이용할 수 있지만 N 제한이 -10^9 ≤ n ≤ m ≤ 10^9 으로 O(N)이 10억을 넘는다. 따라서 Gauß의 더하기 연산을 통해서 처리해줘야 한다. 추가로 더하기의 결과가 int의 범위를 넘기 때문에 long으로 처리해 주어야 한다. 코드 구현 Java 더보기 package bj.bronze.l3;..
[BJ] 7523. GaußBJ 7523. Gauß https://www.acmicpc.net/problem/7523 7523번: Gauß 각 테스트 케이스마다 "Scenario #i:"를 출력한 다음, n부터 m까지 모든 정수의 합을 출력한다. 각 테스트 케이스 사이에는 빈 줄을 하나 출력한다. www.acmicpc.net 생각 왜 시간 복잡도에 대한 고려가 필요한지 살펴보는 문제이다. 간단한 구간 더하기 이므로 for 문을 이용할 수 있지만 N 제한이 -10^9 ≤ n ≤ m ≤ 10^9 으로 O(N)이 10억을 넘는다. 따라서 Gauß의 더하기 연산을 통해서 처리해줘야 한다. 추가로 더하기의 결과가 int의 범위를 넘기 때문에 long으로 처리해 주어야 한다. 코드 구현 Java 더보기 package bj.bronze.l3;..
2023.01.24 -
BJ 1202. 보석도둑 문제링크 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/QgHV5h8kZuk 소스보기 동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다. 소스를..
[BJ]1202. 보석도둑BJ 1202. 보석도둑 문제링크 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/QgHV5h8kZuk 소스보기 동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다. 소스를..
2023.01.15 -
이번 포스트에서는 앞서 살펴봤던 투포인터와 아주 유사한 슬라이딩 윈도우에 대해 살펴보자. https://soeasyalgo.tistory.com/47 투포인터 이번에 살펴볼 투 포인터나 다음에 살펴볼 슬라이딩 윈도우는 모두 1차원 배열 상에서 O(N*M)의 시간 복잡도로 해결해야 할 일들을 O(N)에 해결하게 도와주는 알고리즘이다. 특별하게 코드가 복잡 soeasyalgo.tistory.com 슬라이딩 윈도우(Sliding Window) 알고리즘 문제 살펴보기 먼저 Sliding Window를 이용해서 풀어볼 수 있는 간단한 문제를 살펴보자. https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최..
슬라이딩 윈도우 알고리즘이번 포스트에서는 앞서 살펴봤던 투포인터와 아주 유사한 슬라이딩 윈도우에 대해 살펴보자. https://soeasyalgo.tistory.com/47 투포인터 이번에 살펴볼 투 포인터나 다음에 살펴볼 슬라이딩 윈도우는 모두 1차원 배열 상에서 O(N*M)의 시간 복잡도로 해결해야 할 일들을 O(N)에 해결하게 도와주는 알고리즘이다. 특별하게 코드가 복잡 soeasyalgo.tistory.com 슬라이딩 윈도우(Sliding Window) 알고리즘 문제 살펴보기 먼저 Sliding Window를 이용해서 풀어볼 수 있는 간단한 문제를 살펴보자. https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최..
2022.12.26 -
BJ P5 2842 집배원 한상덕 문제링크 https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/oNqMTOIyLrI 소스보기 동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다. 소스를 보고 작성해 본 후 스스로 백지 ..
[BJ] 2842 집배원 한상덕BJ P5 2842 집배원 한상덕 문제링크 https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net * 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다. 동영상 설명 1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다. 더보기 https://youtu.be/oNqMTOIyLrI 소스보기 동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다. 소스를 보고 작성해 본 후 스스로 백지 ..
2022.12.22 -
이번에 살펴볼 투 포인터나 다음에 살펴볼 슬라이딩 윈도우는 모두 1차원 배열 상에서 O(N*M)의 시간 복잡도로 해결해야 할 일들을 O(N)에 해결하게 도와주는 알고리즘이다. 특별하게 코드가 복잡하지도 않고 쉽게 이해할 수 있는데 왕왕 써먹을데가 많은 알고리즘 중 하나이다. 투 포인터(Two Pointer) 알고리즘 문제 살펴보기 먼저 Tow Pointer를 이용해서 풀어볼 수 있는 간단한 문제를 살펴보자. https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶..
투포인터이번에 살펴볼 투 포인터나 다음에 살펴볼 슬라이딩 윈도우는 모두 1차원 배열 상에서 O(N*M)의 시간 복잡도로 해결해야 할 일들을 O(N)에 해결하게 도와주는 알고리즘이다. 특별하게 코드가 복잡하지도 않고 쉽게 이해할 수 있는데 왕왕 써먹을데가 많은 알고리즘 중 하나이다. 투 포인터(Two Pointer) 알고리즘 문제 살펴보기 먼저 Tow Pointer를 이용해서 풀어볼 수 있는 간단한 문제를 살펴보자. https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶..
2022.12.21 -
주어진 2차원 배열을 다양한 형태로 사용하는 것을 연습해보자. 기본 배열 연습에서 사용할 배열의 기본 형태는 아래와 같이 [4*5]의 char 배열이다. [A, B, C, D, E] [F, G, H, I, J] [K, L, M, N, O] [P, Q, R, S, T] 배열 탐색 행우선 탐색 기대출력결과: ABCDEFGHIJKLMNOPQRST 열우선 탐색 기대출력결과: AFKPBGLQCHMRDINSEJOT 지그재그탐색 기대출력결과: ABCDEJIHGFKLMNOTSRQP 달팽이탐색 기대출력결과: ABCDEJOTSRQPKFGHINML 방향 탐색 자음의 주변을 + 로 탐색하고 요소의 합을 출력하시오. ('A'=0, 'B'=1, ...) 기대출력결과: 498 모음의 주변을 X로 탐색하고 요소의 합을 출력하시오. ..
[배열] 배열 조작 연습주어진 2차원 배열을 다양한 형태로 사용하는 것을 연습해보자. 기본 배열 연습에서 사용할 배열의 기본 형태는 아래와 같이 [4*5]의 char 배열이다. [A, B, C, D, E] [F, G, H, I, J] [K, L, M, N, O] [P, Q, R, S, T] 배열 탐색 행우선 탐색 기대출력결과: ABCDEFGHIJKLMNOPQRST 열우선 탐색 기대출력결과: AFKPBGLQCHMRDINSEJOT 지그재그탐색 기대출력결과: ABCDEJIHGFKLMNOTSRQP 달팽이탐색 기대출력결과: ABCDEJOTSRQPKFGHINML 방향 탐색 자음의 주변을 + 로 탐색하고 요소의 합을 출력하시오. ('A'=0, 'B'=1, ...) 기대출력결과: 498 모음의 주변을 X로 탐색하고 요소의 합을 출력하시오. ..
2022.12.13