파이썬127 [Python] 백준 1806번 : 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 💡문제 풀이 투 포인터 문제이다. 투 포인터의 2가지 유형 중 특정 값을 넘는 배열에 대해서 구하면 된다. 누적 값이 S보다 크다면 개수를 따져주고 왼쪽 포인터를 1 늘린다. S보다 작다면 오른쪽 포인터를 1 늘린다. ✔️ 느낀 점 쉬운 문제였는데 문제를 제대로 안 읽어서 오래 걸렸다. '이상인 값 모두' 💻 코드 N, S = map(int, input().split()) arr =.. 2022. 8. 10. TIL : Two-Pointer 알고리즘 (7) 💻 알고리즘 ✔️ Two-Pointer 알고리즘이란? 리스트에 순차적으로 접근할 때 두 개의 점 위치를 기록하면서 처리하는 알고리즘! 간단히 말해서 포인터 두 개를 사용해서 데이터에 접근하겠다는 소리이다. 💡 특징 포인터 2개가 같은 방향으로 이동 → 특정 값과 일치하는 배열을 찾는 경우 포인터 2개가 양끝에서 출발해서 만남 → 특정 값과 일치하는 합을 찾는 경우 모든 범위를 확인하지 않고 O(n^2), 포인터가 각각 N번만 이동하기 때문에 O(N) ✔️ 포인터가 같은 방향으로 이동 def two_pointer(array, target): end, sum_ = 0, 0 cnt = 0 for start in range(len(array)): while sum_ < target and end < len(ar.. 2022. 8. 8. [Python] 백준 3273번 : 두 수의 합 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 💡 문제 풀이 두 포인터 문제이다. 정렬을 한 다음에 시작 값과 끝 값을 계산해서 같다면 정답의 개수를 늘리고, 계산값이 찾는 값 보다 크면 end를 줄이고, 반대라면 start를 늘리면 된다. ✔️ 느낀 점 두 포인터의 개념을 처음 공부하는 기회였다. 이번에 잘 정리해놔야겠다. 💻 코드 N = int(input()) arr = list(ma.. 2022. 8. 8. TIL : Union-Find 알고리즘, Disjoint Set 자료구조 (6) 📚 자료구조 ✔️ Disjoint Set이란? 여집합이 없는 부분집합을 저장하고 조작하는 자료 구조. 한 마디로, 서로소 집합 자료구조 세 가지 연산을 가진다. 초기화, make-set(x) : x를 유일한 원소로 하는 새로운 set을 만든다. 합치기, union(x, y) : x가 속한 set과 y가 속한 set을 합친다. 찾기, find(x) : x가 속한 set의 루트 노드 값을 리턴한다. 💡 특징 부모 노드가 자식 노드를 가리키는 트리 구조와 다르게 분리 집합은 자식 노드가 부모 노드를 가리킨다. 💻 알고리즘 ✔️ Union-Find 알고리즘이란? 그래프 알고리즘 중 하나로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 다시 말하면, disjoint set을 표현할 때 사용하는 알고리즘.. 2022. 8. 7. [Python] 백준 1976번 : 여행 가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 💡 문제 풀이 그래프 이론 중 Union-Find 문제이다. union 함수와 find 함수를 구현할 수 있다면 쉽게 풀 수 있다. 입력받은 값들에 대해서 각 node별로 연결해주고 여행 계획에 맞춰 find 함수를 사용해 1개의 값으로 귀결된다면 YES를, 아니라면 NO를 출력해주면 된다. ✔️ 느낀 점 union-find 알고리즘에 대해서 제대로 이해를 못 해서 낯설었던 문제였다. 새로운 알고.. 2022. 8. 7. [Python] 백준 1038번 : 감소하는 수 https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 💡 문제 풀이 백트래킹인줄 알고 풀었는데 브루트 포스로 풀었다. 조합을 이용해서 각 자릿수 별로 만들 수 있는 모든 값들을 만든다. 정렬을 통해서 감소하는 수를 만들어주고 배열에 넣어준다. 감소하는 수를 담은 배열을 정렬해주면 순서대로 감소하는 수를 찾을 수 있다. ✔️ 느낀 점 보자마자 가장 큰 값은 9876543210 이라고 생각했다. 범위가 생각보다 크지 않아서 모두 담아버린 .. 2022. 8. 5. 이전 1 ··· 7 8 9 10 11 12 13 ··· 22 다음