![]()
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차원 그래프로 표현할 수 ..
![]()
백준에는 잘 나오지 않는 부분 배열/부분 집합 DP 로직에 대해 정리해 보았다. 1차원 배열 A에서 생각해볼 수 있는 DP 접근을 다양하게 해볼 수 있다. 간단한 목차는 아래와 같다. 1. 배열 A의 부분 배열의 최댓값 (제한 X) 2. 배열 A의 k개의 연속한 부분 배열의 최댓값 (k개라는 제한이 존재한다) 3. 배열 A의 k개 이상 연속한 부분 배열의 최댓값 (k개 이상이라는 제한이 존재한다.) 4. 배열 A에서 부분집합의 합이 S인 부분집합이 존재하는가? (존재 여부, 제한 X) 5. 배열 A에서 k개의 부분집합의 합이 S인 부분집합이 존재하는가? (존재 여부, k개라는 제한이 존재한다)1. 배열 A의 부분 배열의 최댓값 (제한 X)배열 A가 주어졌을 때, 이 배열의 부분 배열 A의 최댓값을 구하라..
![]()
목차 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차원 평면을 두 개로 쪼개서 해..
![]()
문제 일단 프로그래머스는 시간제한이 따로 명시되어 있지 않다. 약 1~10초 정도의 시간 안에 풀면 된다고 암묵적으로 정해져 있다고 한다. 입력 N값이 최대 100만이므로, O(N^2)은 안된다. IDEA (잘못된 생각들..) 일단 for문 두 개로 돌리는 방법은 절대 통하지 않는다. O(N^2) 그래서 뒤에서부터 하나씩 숫자들을 판단해가면서 dictionary에 최소 index를 저장해주고 탐색하는 식으로 가려고 했으나, dictionary에 저장되는 수마저 100만이므로 똑같이 O(N^2)가 되어 이 방법도 불가능하다. IDEA - stack 자료구조 + while문 결국 아이디어를 참고하고 만 문제이다.😓 다음과 같이 하나씩 돌면서 numbers[i]가 '가까운 가장 큰 수'인 것들을 stack에서..
세상에서 제일 화나는 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..
지금껏 다익스트라는 adj라는 배열만 만들어서 사용했었는데, 이 문제는 dijkstra를 눈치채고 다익스트라를 구현하기까지 쉽지 않았다. 일단 맨 처음 문제를 보았을 때에는 floodfill 먼저 떠올랐는데(GridWorld라서 더 그랬다), floodfill과는 결이 다르다. 왜냐면 이미 갔던 곳도 더 빠른 방법이 있다면 왼/오/위/아래 의 방법을 선택해서 빠른 방법으로 갱신해낼 수 있기 때문이다. 그래서 가중치를 가지는 다익스트라로 구현할 수 있다. 다익스트라의 특징은 다음과 같다. 가중치가 모두 양수이다. 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다. 각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 더 작은 값으로 다시 갱신되지 않는다. 우선순..
밑은 내가 맨 처음에 호다닥 작성한 코드. 그리고 시간초과를 받았다😥 bottom up 방식으로, 외판원이 현재 위치에서 갈 수 있는 위치로 간 후 갱신 -> 다시 그 위치에서 갈 수 있는 위치로 간 후 갱신 ---> 이 방법을 반복하였다. 어떻게 보면 DFS 느낌?으로 해결하려 했다.(이 발상이 이게 참 문제임 ) 이 코드의 문제는 DP에서 가장 중요한 문제인 MEMOIZATION이었다. DP 테이블을 갱신하는 방법은 이미 계산된 결과 이용하기 가 바탕이고, 다양한 방법이 있는데, 내가 짠 건.. 앞에서 왔던 길을 보는 게 아니라 갈 길에 체크를 하는 ,, 아주 바보같고 느린 방법을 사용했다. 암튼 이 코드는 매우 비효율적. '차곡차곡 쌓자'라는 접근방식을 자꾸 생각하는 걸 줄여나갈 필요가 있다. 배낭..
![]()
분할정복의 시간복잡도는 NlogN이다. (단계 별 문제 개수 (N//2^K) X 해당 단계에서 쪼개는/병합하는 시간(2^K) X 단계 개수(크기가 이진탐색 수준으로 줄기 때문에 logN)) 이것을 밑으로 내려가면서 쪼갤 때 / 위로 올라오면서 병합할 때 2번해서 어차피 2 NlogN이므로 시간복잡도는 그냥 NlogN이다. (DP테이블은 문제 종류가 M이라고 하면 O(NM)이라 더 효과적인 것을 확인할 수 있음) ★DP와 다른 점 부분 문제가 서로 중복되지 않는다. 위 사항 덕분에 Memoization이 필요하지 않다. 굳이 내가 알아낸 데이터를 저장하지 않는다. ★이분탐색트리 또는 세그먼트 트리와 다른 점 이분탐색/세그먼트는 일단 아는 노드를 쭉 나열해 두고 둘씩 짝지어서 위로 올라가며 판단하는 과정을 ..
binary search, 이분법적으로 딱 ' 이 시간. 이 숫자. 이 갯수 '를 구하고 싶을 때 매우 강력한 툴이다. 하지만 너무 생각할 게 많다.. 그래서 꾸준히 정리를 해보도록 하겠다!!! (자꾸 끼워 맞추면서 풀다가 실전에서 시간 너무 오래 잡지 말자...) [1, 2, 3, 3, 3, 3, 4, 5, 5] 라는 배열이 있다. 우리는 3을 찾고 싶다. 음.. 3 중에서도 가장 최소의 index를 가지는 3을 찾고 싶다면, 이렇게 mid가 가장 왼쪽을 향하게 하도록 극한으로 몰아세운다. (직접 해보면 이해 잘 됨) while lo target: return binary_search(array, target, start, mid) #중간값의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 elif ar..
비트마스킹을 이용하면 굳이 배열을 쓰지 않아도 되므로 메모리도 절약될 뿐만 아니라 배열의 index로도 쓸 수 있어(0001은 1로, 0010은 2로 쓸 수 있다.) 매우 강력한 툴이다! 주로 있다/없다 의 이분법적 현상을 반영해서 표현할 수 있다. 이것만 알면..!! 된다!! & -> 모두 1일때 1반환 | -> 하나라도 1일때 1 반환 / 모두 0일 때 0반환 ^ -> 대응하는 두 비트가 서로 다를 때 1반환 >> -> 오른쪽으로 비트 옮김 100>>2:1 ★삽입 시! i번째 비트를 i값으로 변경할 때 10101에서 11101 만들고 싶다면 10101 | 1
![]()
문제정리 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 사다리 문제. 일단 문제 파악이 쉽지 않아 여러 사다리를 마구 만들어봤다. 생각노트 세로선이 - - 이렇게 똑같은 높이에 그어지면 안된다. 앞에서부터 최대한으로 만족 시키다가 아무리 앞을 바꿔도 뒤에서 더이상 안되는 경우가 생긴다. 위의 경우처럼. 선을 추가하는 경우와 추가하지 않는 경우를 생각해볼 수 있는데, 선을 추가하는 경우 그 칸이 홀수일 때, 선을 추가하지 않는 경우는 그 칸이..
![]()
문제정리 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 생각노트 두 자동차가 가는 길이 있다고 했을 때 어떻게 하면 최소로 갈 수 있을까. 이때 각 자동차를 "무조건 가까운 곳"으로 선택해서 가는 방법은 조금 생각해보면 안 된다는 것을 알 수 있다. 몇 번째 사건을 누가 처리하느냐에 따라 의존성이 계속해서 바뀌기 때문이다. (아무리 경찰차2랑 현재 거리에서는 가깝다고 하더라도 경찰차1이 사건 1,2,3을 처리하다가 더 ..
대뜸 다음 코드에서 값이 어떻게 나올지 예상해 보자. def spam(eggs): eggs.append(1) eggs=[2,3] ham=[0] spam(ham) print(ham) 그래, 배열은 메모리 주소값을 할당하는 거라고 했고, 함수 spam에 인수로 넣은 ham이 eggs가 되는 격이니까 답은 [2,3]! 이라고 했다면... ㅎㅎ이 글을 보게 된 것이 다행이다!! spam에 함수의 parameter는 eggs이다. 따라서 우리가 ham을 spam에 넣어준 동시에 함수의 parameter eggs는 ham 자체가 된다. 3행에서 eggs는 새로운 리스트를 만드는 코드이다. 그래서 이 경우, 더는 ham과 eggs와 같은 메모리 주소를 가리키지 않고 eggs는 자신만의 메모리 주소를 가지게 된다. 함..
![]()
먼저 python list의 메모리 관리 방식에 대한 이해가 필요하다. python에서 연산자 중에 '=='는 값을 비교하는 연산자이고, 'is'는 메모리의 주소를 비교하는 연산이다. 아래 코드를 보자.a=300 b=300 a is b #False a == b #True그런데 조금 다른 결과가 나타나는 경우가 있는데,a = 1 b = 1 a is b #True a == b #True엥? 이 때는 a와 b의 메모리 주소가 같은 걸까?? 이것은 파이썬의 정수형 저장 방식의 특성 때문인데, -5부터 256까지의 정수값은 특정 메모리 주소에 저장한 후 해당 숫자를 할당하려고 하면 해당 변수는 그 숫자가 가진 메모리 주소로 연결한다. 리스트가 위와 같은 메모리 저장 방식을 택하고 있다고 생각하면 되는데, 파이썬은..
카카오인턴 2022 05 07 후기! 시험은 2시부터 7시까지 5시간동안 진행되었다. 생각보다 5시간 집중하는 게 쉽지 않았다.! 1 1솔 2 1솔 3 ㅠ 4 0.5솔 5 0.5솔 4,5번은 구현은 했지만 효율성에서 몇 개를 통과를 못 했다ㅠㅠ 일단 5번은 뭔가 사람들이 다 잘 풀었을 것 같아서 합격은 장담이 안될 것 같다. 그래도 아직 시간 많으니까 좋은 경험이었다. 문제를 풀어보면서 일단 4번에서 다익스트라 알고리즘이 나온 것 같은데 이 문제를 풀면서 다익스트라에 대한 이해도가 좀 더 높아진 것 같다(heap을 사용할 때 최소힙 최대힙 쓰자고 했던 것들을 막상 구현할 때 좀 생각을 못 한 것 같아서 아쉽다ㅠㅠ) 그리고 공부할 때 가끔 문제를 좀 선별해서 풀다보니까 도형 쪽 공부는 안 해왔던 게 탄로나..
