youngseo's TECH blog

0. 문제 별 찍기 - 11 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 1. 문제 생각 규칙을 유추해보는 과정, 패턴을 파악하는 것이 그리 어렵지는 않았으나 마음처럼 뭉탱이로 구현할 수 없어 생각을 좀 더 했던 것 같다! 재귀적으로 패턴이 반복되는 것이 보여서 아래 종이에서 보이는 것처럼 12를 채우기 위해 6으로 쪼개서 나아가고 다시 6을 채우기 위해 3으로 쪼개서 나아가는 방법으로 분할정복 재귀를 써야겠다고 생각했다. 평소 그리는 분할정복의 로직은 아래와 같다. def div_conquer(): #가장 밑 분할 노드 도착했을 때 return #분할해서 ..

0. 문제 캠프 준비 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 1. 문제 생각 처음에는 투포인터일까? 싶었다. 하지만 투포인터는 각 요소가 모두 다를 때 효율적인데 입력값에서 배열이 [10, 10, 20, 10, 40] 으로 들어온다면 이는 별 효율이 없을 것 같았다. 이후 입력값이 고작 N= L and sum(List) = X: # print(List) ans+=1 #return하면 안됨 . => 한 번 더 가야할 수도 있으니까 for i in range(node+1, N): # 1 ~ N 까지 if not visited[i]: # 중복 확인 visited[i]=1 backtracking(i, visited,Lis..

0. 문제 스카이라인 쉬운거 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 1. 문제 생각 처음에는 스카이라인이라고 해서 라인스위핑이겠거니 하고 달려들었다! 하지만 예제를 보면 처참히 깨질 수 있는데.. 하나씩 순차적으로 파악하는 형태의 로직이 아니다. 즉, 앞에서의 상황이 뒤에 의존될 수 있다. 입력값에서 주어지는 것은 '스카이라인의 고도가 바뀌는 지점의 좌표 x와 y' 이다. 즉, 이 곳에서는 무조건! 고도가 바뀌어야 한다. 그렇다면 위 그림의 상황을..

1. 문제 개미 3048번: 개미 T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다. www.acmicpc.net 2. 문제 생각 처음에는 규칙을 찾으려고 했다. T가 몇 번일 때 바뀌는 것과 바뀌지 않는 것들이 몇 번인지를 기준으로 찾아서 구현하려고 하였다. 이후 다시 보니 아래의 두 힌트가 명시적으로 N1과 N2가 굉장히 작고 T도 50밖에 되지 않아 빡구현이겠구나 하고 생각하였다. 3. 문제 풀이 N,M=map(int,input().split()) A=list(input()) B=list(input()) T=int(input()) start=A[::-1]+B for _ in range(T): flag=False; #..

0. 에필로그 원래 백준 문제는 블로그에 안 쓰고 개인적으로 정리했는데 코알라 면접 보다가 큰 영감을 얻어 열심히 기록해볼 생각이다! 👻 일주일에 적어도 5개는 풀어야징 1. 문제 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net2. 생각 "모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합"을 최소화할 수 있는 건물 두 개를 고르는 문제이다. 우선 이 문제에서 요구하는 현상을 2차원 그래프로 표현할 수 ..

목차 1. 문제 정리 2. 알고리즘 증명 및 설명 3. 코드 구현 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 1. 문제정리 2차원 평면 위에 여러 점들이 콕콕 박혀 있다. 이 점들 사이 거리 중 가장 짧은 거리를 찾으려 한다. 2. 알고리즘 증명 및 설명 일단 일일이 다 해보는 전략에 따르면, 모든 가능한 점의 쌍 거리를 구하는 데 O(N^2), 정렬하는 데 O(N^2 logN)으로 총 O(N^2 logN)의 시간복잡도가 걸린다. 그럼 이 2차원 평면을 두 개로 쪼개서 해..

세상에서 제일 화나는 TOP DOWN DP 유형이다. 저번 글에서 본 것처럼 DP-TOPDOWN의 형식적인 코드는 다음과 같다 (느낌만 알아두자) def topdown: if 마지막 노드에 다다른 조건: return ~~ if 이미 DP 테이블에 값이 있다면(memoization): return 그냥 그거 가져온다. #밑에 있는 노드를 호출해서 답 갱신 + 필요하다면 DP 테이블에도 값 갱신 DP[][]+= 또는 min .. topdown() return 해당 노드값 이 문제에서는 ‘되냐 안되냐’의 문제를 다룬다. 이럴 때 0, 1, max를 사용해서 풀 수 있다. 만약 조건에 만족하는 것이 하나라도 나올 시에는 return 1을 하고 안 나오면 계속 return 0을 한다. memoization 방법은..

일단 이 문제는 구현이 되게 생소하고 어렵다. 그래프를 표현하는 방법에 대해 생각을 많이 해볼 수 있는 문제라 좋다. 그래프를 배울 때 가장 먼저 배우는 것이자 많이 사용하는 것이 바로 계산하는 순서인 전위/중위/후위 표기식이다. 이런 표기식을 잘 생각해 보면서 문제를 풀어야 한다. 잘 나타내 보면, 규칙은 다음과 같다. ‘+’일 때는 그냥 내려간다. ‘-’일 때는 -오른쪽 자식의 상태를 switch 시킨다. -왼쪽은 그냥 내려간다. 이런 식으로 계속 상태를 바꾸어 주다가 마지막 노드인 1~N까지의 수에 도달하였을 때 연산자가 -라면 -가 몇 개 나오는지 모두 더해준다. 마지막으로 -의 개수(만약 3개라면) 에 따라서 가장 작은 수(3개)의 개수만큼을 최소 heapq에서 뽑아 SUM 값에서 빼준다. SU..