주제무 다시 봐도 핵심만 보이게끔!

투 포인터 간단 정리 두 개의 포인터를 사용하여 풀이한다. 하나의 배열에서 풀이하는 문제와 두 개의 배열에서 풀이하는 문제가 있다. 핵심은 포인터를 어떤 조건에서 움직일 것인가를 명확히 하는 것이다. 두 개의 포인터와 조건을 다 따로 보려고 하면 분기점이 많아지므로 오른쪽 포인터를 고정시키는 테크닉과 오른쪽으로만 이동할 수 있는 설계가 필요하다. 예제 겹치는 건 싫어 https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net import sys de..

BFS DFS 간단 정리 DFS 스택으로 구현 스택에 추가되는 경우: 현재 노드에서 방문하지 않은 노드 중에 다음 방문예정인 노드 스택에서 빠지는 경우: 주변 노드들이 다 방문된 경우 한 노드에서 깊이 탐색이 종료된 시점에 저장해야할 값이 있다면, 인접 노드에서 재귀를 마치고 올라올 때 반환하는 값을 사용하면 된다. 재귀를 마치고 올라온다는 뜻은 주변 노드들이 다 방문된 경우이므로 스택에서 빠질 때, 즉 함수가 끝나는 시점에서 반환한다. BFS 큐로 구현 큐에 추가되는 경우: 현재 노드에서 방문하지 않은 노드 전부 큐에서 빠지는 경우: 방문하면서 빠진다 큐를 이용하기 때문에, 시작 노드로부터 떨어진 거리가 오름차순으로 정렬됨을 보장한다. 따라서 시작 노드로부터 조건을 만족하는 최소 거리 노드를 구할 수 ..

union-find, disjoint set 간단 정리 서로소 집합을 표현할 수 있다. 트리 구조를 사용하며, 한 집합은 하나의 트리구조로 표현된다. 무방향 그래프의 사이클을 검사할 수 있다. 시간 복잡도는 대략 (find 연산의 수) x (log_2 노드의 개수) 이다. union 두 원소를 같은 집합으로 합치는 연산 원소 a, b와 둘의 루트 노드 A, B가 있을 때, A를 B의 자식으로 (혹은 반대로) 연결한다. def union(x, y): x = find_parent(x) y = find_parent(y) parents[x] = y find 원소의 부모를 찾는 연산 자식에서 부모 쪽으로 거슬러 올라간다. 노드의 부모가 자기 자신이 될 때까지(루트 노드) 반복한다. 경로 압축을 통해 최적화를 할 ..

목표 코드를 치기 전에, 조건을 정확히 이해하고 주제를 정한 뒤 시간복잡도를 계산한다. 각 로직의 세부사항(분기 조건, 반복 조건, 함수 시그니처)를 이해하고 손으로 작성한 뒤에 코드를 작성한다. 도넛과 막대 그래프 https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr import sys sys.setrecursionlimit(1_000_000) N = 1_000_001 edge_in = [0] * N edge_out = [[] for _ in r..

순열과 조합 backtracking 을 이용한 조합 n, m = map(int, input().split()) data = [] def combination(pre_num): if len(data) == m: print(*data) else: for i in range(1, n+1): if pre_num < i: data.append(i) combination(i) data.pop() combination(0) 순열 n, m = map(int, input().split()) data = [] def permutation(pre_list): if len(data) == m: print(*data) else: for i in range(1, n+1): if i not in pre_list: data.appe..

이진분류와 하노이 탑 숫자 찾기 백준 1920 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. -> 정말 쉬운 문제이지만, 배운 것을 적용하기 위해서 이진 탐색 관련 알고리즘으로 구현하였다. 우선 처음에 작성한 코드 def binary_search(ordered_list, target): left, right = 0, len(ordered_list) - 1 mid = (left + right) // 2 if left == right: if ordered_list[left] == target: return True else: return False elif ordered_list[mid] > target: mid -= 1..

무방향 그래프와 서로소 집합 서로소 집합의 필요성을 이해하기 위해서 아래 문제를 읽어보자. https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제를 읽어보면 진실을 알고 있는 사람이 포함된 파티와 포함되지 않은 파티로 나누고 싶을 것이다. 바이러스가 전염되는 것처럼 진실을 알고 있는 사람이 포함된 파티(그래프)는 모두 진실을 알게 된다. 하지만 단절된 그래프는 전염되지 않기도 하다. 위와 같은 상황에서 서로소 집합의 개념을 적용할 수 있다. 서로 다른 파티..

n-queen 구현 백트레킹으로 누구나 한번쯤 들어봤을 문제. 간단하게 풀릴 것이라 예상하고 구현해봤는데 생각대로 잘 안된다. 첫 구현. def way_on_queen(i, j, q): visited(i, j, q) dx = 1 while i + dx < N: ni = i+dx visited(ni, j+dx, q) visited(ni, j-dx, q) visited(ni, j, q) dx += 1 def visited(i, j, q): if 0

코테 준비 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net import sys input = lambda: sys.stdin.readline().rstrip() N, M = map(int, input().split()) knowns = set(map(int, input().split()[1:])) party = [list(map(int, input().split()[1:])) for _ in range(M)] visited = [False] * (N+1)..

코테 연습 기타 첫 번째 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net import sys input = lambda: sys.stdin.readline().rstrip() def multiply(b): if b == 1: return A sub_result = multiply(b//2) % C result = sub_result ** 2 return result*A if b % 2 == 1 else result A, B, C = map(int, input().split()) print(multiply(B)..