겹치는 직선 구간쌍의 개수 빠르게 세기

D - Intersecting Intervals (atcoder.jp) D - Intersecting IntervalsAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  50만개의 구간 [l,r]이 주어질때, 이들 중 서로 겹치는 구간 쌍의 개수가 몇개인지 구하는 문제 모든 구간 쌍에 대해 서로 겹치는지 조사할려면 $O(N^{2})$인데, 당연히 N이 최대 50만이므로 시간제한에 맞지 않는다 전체 구간 쌍의 개수는 n개중 2개를 선택하는 경우의 수이므로, nC2 = n(n-1)/2 만약 서로 겹치치 않는 구간 쌍의 개수를 구..

• format_list_bulleted 투 포인터 알고리즘
• · 2024. 8. 2.
• textsms

트리에서 임의의 노드에서 모든 노드를 적어도 1번 이상 방문하는데 걸리는 최소 거리

E - Tree and Hamilton Path 2 (atcoder.jp) E - Tree and Hamilton Path 2AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  트리의 어떤 정점 A에서 출발하여 모든 정점을 1번 이상 방문하고, 다시 정점 A로 돌아온다고 생각해보면, 만약 트리의 어떤 변을 제거하면 다음과 같이 2개의 연결성분이 생기고 출발점에서 다시 출발점으로 돌아올려면 두 연결성분을 서로 왔다갔다 해야하므로, 정확히 각 변을 2번 지나면 출발점에서 모든 노드를 1번 이상 방문하여 출발점으로 돌아올 수 있다..

• format_list_bulleted DFS BFS 정복기
• · 2024. 7. 11.
• textsms

중간에서 만나기 테크닉 - 저장하고 검사하는 것이 아니라 검사를 먼저하고 저장하기

5624번: 좋은 수 (acmicpc.net)  정수 배열에서 현재 위치 i번째 수 앞에 있는 수들 중 세 수의 합이 현재 위치 i번째 수와 같게 되는 경우,  그러한 수의 개수를 구하는 문제 "세 수"는 중복해서 선택해도 좋다 예를 들어 [-1,2,0]이면 0은 -1 -1 + 2 = 0이므로 이 조건에 만족하는 수이다 n이 최대 5000인데, 단순하게 짜면 $O(N^{4})$이라 매우 느리다 대충 이런 느낌 for i in range(n): a = A[i] for j in range(i): for k in range(i): for w in range(i): ..

• format_list_bulleted 중간에서 만나기
• · 2024. 6. 10.
• textsms

부분문자열 필수 트릭 - doubling cyclic substring trick

24597번: Reversibly Cyclic Strings (acmicpc.net)  문자열 s의 cyclic substring이라는 것은 s를 rotate했을때 부분문자열 t를 말한다. 'fatcat'에서 'atf'는 fatcat에서 왼쪽으로 1칸 rotate하면 atcatf인데 여기에 부분문자열로 있다 만약 s의 모든 부분문자열 t에 대하여 t를 뒤집은 것이 s의 cyclic substring이라면 s를 'Internally Reversibly Cyclic'이라고 정의한다. 주어진 s가 Internally Reversibly Cyclic인지 판단하는 문제  어떤 부분 문자열 t가 s의 cyclic substring이라는 것을 어떻게 알 수 있을까? 한칸 한칸씩 roate해서 판단해봐야할까? fatc..

• format_list_bulleted 문자열 알고리즘
• · 2024. 5. 9.
• textsms

이진수의 마지막 n개의 비트가 모두 켜져있는지 확인하는 방법

SW Expert Academy SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  정수 m의 마지막 n개의 비트가 모두 1인지 확인하는 문제 m이 $10^{8}$이고 테스트 케이스는 10000개이고 제한시간 2초라 단순하게 확인하면 시간초과날 것 같다 가장 쉬운 방법은 0부터 n-1까지 순회해서 각 비트가 1인지 검사하는 것 (1 이다. T = int(input())for test_case in range(1, T + 1): n,m = map(int,input().split()) no = False for i in range(n): if (1   다른..

• format_list_bulleted 비트마스킹
• · 2024. 5. 3.
• textsms

코딩테스트 복기 - 복잡한 그래프 생각하면서 효율적으로 탐색 하기

1. 문제 코딩테스트 연습 - 도넛과 막대 그래프 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 핵심은 눈치 잘 챘는데.. 시간의 압박에 못이겨서 그런건지 시간초과에서 못벗어났다.. 다시 풀어보니까 시간복잡도를 생각해서 기본에 충실하게 DFS 그래프 탐색을 구현한다면 생각보다 쉽게 풀 수 있더라고 평면에 도넛, 막대, 8자모양 그래프가 여러개 있는데.. 이 그래프와 무관한 하나의 정점을 생성하고 이 정점과 각 그래프의 임의의 정점 중 하나에 연결시켰다 무관한 하나의 정점 번호와 도넛, 막..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 2. 3.
• textsms