본문 바로가기
728x90

TIL - 프로그래밍/Python 알고리즘198

[프로그래머스] 2023 KAKAO BLIND RECRUITMENT 미로 탈출 명령어 - Python https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 우선 미로를 탈출 할 수 없는 경우와 있는 경우를 나누어 생각했다. 미로를 탈출할 수 없는 경우 (impossible) 출발지와 도착지의 최단거리를 계산 후 1) 남은 거리가 홀 수 또는 2) 최단거리가 k보다 멀다면 도착할 수 없다. 남은 거리를 (d,u), (l,r) 쌍으로 채울 수 있는데 무조건 짝수여야한다. 미로를 탈출할 수 있는 경우 문자열이 사전 순으로 가장 빠른 경로로 탈출 q.. 2023. 11. 12.
[백준] 2042. 구간 합 구하기 - Python (세그먼트 트리 개념 설명) 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합 구하기 배열에서 특정한 범위의 데이터 합을 가장 빠르게 구하는 방법은 무엇인가? data = [1,2,3,4,5] 방법 1. 단순 배열을 이용해 선형적으로 구하기 인덱스 i부터 j까지 데이터 더하기 print(sum(data[i:j+1])) 앞에서 하나씩 더해가므로 데이터의 개수가 n이면 시간 복잡도 O(N), n이 매우 커지면 구간의 합을 구하는 속도가 너무 느리기 때문에 더 좋은 알고리즘이 필요하다. 방법2. 트리 구조 이용하여 구하기 세그먼트 트리 배열의 특정 구간에 대한 정보를 추가로 담고 있다. 트리 구조의 특성상 합을 구할 때 시간 복잡도 O(logN) 1️⃣ 구간 합 트리 생성하기 가장 최상단의 노드에는 전체 원소의 합이 들.. 2023. 7. 4.
[백준] 20303. 할로윈의 양아치 - Python https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 풀이 1명의 아이 사탕을 뺏으면 연결 친구들 다 뺏어야 함 아이들을 그룹 형태로 묶자 deque 사용 [각 그룹의 아이 수, 각 그룹에 아이들 사탕 총 합] k명 이상 뺏으면 안됨 각 그룹의 사탕을 뺏기와 안뺏기 중 더 나은 상황 선택 배낭 문제 - Knapsack 알고리즘 사용 코드 ''' 접근법 ''' fro.. 2023. 6. 12.
[프로그래머스] 표현 가능한 이진트리 - Python https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이진트리를 수로 표현 10진수를 2진수로 만들기 : bin(num)[2:] 포화 이진 트리로 만들기 포화 이진 트리 노드 개수 == (2**n)-1 n 을 구해야 함 (아래 표 보기) n = 정수(log2(길이)) + 1 n == (int(math.log(len(num), 2)) + 1) 2진수에서 왼쪽에 모자란 길이만큼 0 추가 포화 이진 트리가 가능한 형태인지 확인 부모가 없이 자식만 .. 2023. 6. 12.
[백준] 11758. CCW - Python https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 풀이 https://chaemi720.tistory.com/304 [알고리즘] CCW (선분 교차 판별) CCW : Counter Clock Wise 3개의 점 A, B, C가 있을 때 이 점 3개를 이은 직선의 방향을 알고자 할 때 유용한 기하 알고리즘 3가지 경우의 수 외적을 통하여 구할 수 있다. 외적의 결과가 음수면 시계 .. 2023. 5. 3.
[알고리즘] CCW (선분 교차 판별) CCW : Counter Clock Wise 3개의 점 A, B, C가 있을 때 이 점 3개를 이은 직선의 방향을 알고자 할 때 유용한 기하 알고리즘 3가지 경우의 수 외적을 통하여 구할 수 있다. 외적의 결과가 음수면 시계 방향 직선은 0 양수면 반시계 방향 외적이란 두 벡터에 동시에 수직인 벡터를 찾는 연산 두 벡터에 동시에 수직인 벡터는 2개이므로 두 벡터의 순서로 방향을 결정 외적 계산 i, j, k : x축, y축, z축 단위 벡터 선분 교차 교차할려면 A와 B는 CD를 기준으로 다른 영역에 있어야 한다. 즉, CCW 부호가 달라야 한다. 하지만 반드시 교차는 아니다. 양쪽에 대해 둘 다 방향이 달라야 실제로 교차함을 확인 가능 예외 네 점 중 세 점이 일직선 하나의 점이 나머지 선분 사이에 있.. 2023. 5. 3.
반응형

티스토리툴바