WOONY's 인사이트

0. 목차 1. 아침 산책 풀이 2. 위상 정렬 점점 말이 없어진다.. 바로 풀이로 가자. 1. 아침 산책 (#21606) 먼저 문제 링크. 문제 풀이의 논리는 아래와 같다. 문제에서는 실내 노드에서 출발해 실내 노드로 도착한다고 설명한다. 그래서 실내를 기준으로 생각하게 되나, 이 문제는 실외 노드를 중심에 놓고 인접한 실내 노드를 세는 방식이 훨씬 편하다. 먼저 실외 노드를 기준으로 인접해있는 실내 노드 수를 count한다. 실외 노드를 가운데 놓고 인접한 실내 점 n개가 붙어있을 때, 갈 수 있는 경로의 수는 n * n-1 (n개의 실내 점 중 하나 고르는 경우의 수 X 실외 점 1개 고르는 경우의 수 1 X 앞에서 고른 1개의 실내 점 제외한 n-1개 점 중 하나 고르는 경우의 수) for문 돌면..

0. 목차 1. 트리 순회 - Preorder / Inorder / Postorder 2. 이진 검색 트리 - 재귀를 활용해 검색하는 방법 3. 서로소 집합 구조 & 유니온 파인드 & 크루스칼 알고리즘: 서로소인 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 1. 이진 검색 트리 & 데이터 탐색 방법: 트리 순회 - Preorder / Inorder / Postorder 개념 정리부터 먼저 하고 넘어가자. 이진 트리란, 부모 노드가 왼쪽/오른쪽 자식 이렇게 두 개의 자식 노드만을 갖는 트리를 말한다. 이때, 왼쪽/오른쪽 자식을 구분한다. 이진 트리에 대한 보다 자세한 정리는 아래 챕터에서 하기로 하고, 여기서는 곧바로 문제를 보면서 이진 트리에서 데이터를 탐색하는 방법인 트리 순회에 대해..

오늘 2주차 시험에서는 1시간 반 동안 겨우 1문제 풀었다. 공부할 때도 엄청 빡셌지만 어찌어찌 익혔다는 느낌이 없잖았는데 결과가 이러니 참담하다 싶지만..! 그래도 한 문제 푼 게 어딘가! 아자자! 잘했다! 한 걸음씩 가는 거지! 1. MOO 게임(#5904) 문제 링크는 여기. 도저히 어떻게 접근해야 좋을지 몰라, 맨 처음에는 아예 수열 자체를 구해버리려고 했다. 10^9를 넘는 가장 작은 수열을 뽑으려고 해봤는데 대략 n이 10~20 사이에서 될 것 같더라! 문제는 n=12를 넣을 때부터 연산이 뻗는다는 느낌이 들기 시작하더니 n=15쯤 가니 허송세월하고 있더라. 이렇게는 도저히 못 풀겠다 확신만 하고 끝남..^_^ 지훈이의 풀이를 공부한 내용을 정리하자면, 이 문제는 재귀로 이루어진 점화식을 길이..

0. 목차 1. 분할 정복 정리 2. 곱셈 3. 히스토그램에서 가장 큰 직사각형 4. 행렬 제곱 5. 가장 가까운 두 점 1. 분할 정복 정리 분할 정복 알고리즘은 그 자체로 해결할 수 없는 문제를 작은 문제로 쪼개서 해결하는 방법이다. 예시로는 정렬 알고리즘 중에서 퀵 정렬이나병합 정렬(merge sort), 이진 탐색 등이 있다. 방식은 아래와 같다. 1. Divide 주어진 문제를 잘 쪼개서 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때까지 나눈다. 2. Conquer 각 하위 문제를 재귀적으로 해결한다. 이때, 하위 문제를 더 이상 나눌 수 없는 상황이 되면 종료 조건을 설정하고 해결. 3. Combine Conquer한 문제를 통합해서 원래 문제의 답을 구한다. 대략 재귀랑 비슷한 방식인..

오늘은 어제에 이어서 계속해서 이분 탐색 문제를 풀었다. 진도가 생각만큼 빠르게 나가지 않아 답답한 감이 없잖아 있다. 내일부터는 한 문제당 푸는 시간 30분 / 답지 보고 확인하는 시간 30분으로 시간 제한을 좀더 엄격하게 지킬 예정. 빠르게 후루룩 넘기고 다시 보는 게 낫지 하나하나 공들여서 공부하기에는 시간이 너무 부족하다. 1. 두 용액 두 용액 문제는 투포인터 알고리즘을 이용해 푸는 방식이다. 이진 탐색 카테고리에 두 용액 문제가 속해있어서 이진 탐색으로 풀어야 한다는 전제에서 문제를 접근하려니 어디에 mid를 잡아야 할지 도통 감을 잡지 못했다. 하지만 이 문제는 투포인터 알고리즘을 이용해 풀어야 한다는 점과 투포인터 알고리즘은 이분 탐색과 약간 다르다는 점을 알고 있어야 문제에 보다 수월하게..

1. 이진 탐색(Binary Search) 보통 우리가 탐색을 시도할 때는 순차적으로 탐색하는 방법을 이용한다. 기존의 순차 탐색은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 데이터를 확인하는 방법이다. 리스트에서 특정 데이터를 찾기 위해 검사할 때, 별 다른 조건이 없으면 순차적으로 탐색을 시도한다. 이와 달리 이진 탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 여기서 전제는 탐색하려는 리스트가 정렬되어 있어야 한다는 점이다! 이진 탐색을 하기 위해서는 탐색 범위를 설정해줘야 하는데, 총 세 가지 포인트가 있다. 시작점 (start) 끝점 (end) 중간점 (mid = (start+end)//2) 이 셋을 이용해 탐색한다. 순서는 아래와 같..

오늘은 1주차 알고리즘 시험날. 문제는 #1924, #2503, #6603이 나왔고 1시간 반 동안 푼 문제는 #1924와 #6603으로 3문제 중 2문제. 오늘 시험 목표가 2문제 이상 맞추기였으니 선방은 했는데, 생각보다 1924와 6603을 쉽게 풀어 2503까지 풀지 못한 건 좀 아쉽긴 하다. 시험이 끝나고 바로 2주차 문제가 주어졌으나, 오늘은 푼 문제를 리뷰하면서 시간을 보냈다. 오후에는 #2503을 푸는데 시간을 썼다. 어렵다고 생각했지만 조금 해보니 어느 정도 감이 잡히더라. 스트라이크와 볼을 if문 두 번으로 처리하는 개념만 잘 생각하면 괜찮다. 오히려 쉽게 풀었던 #6603에서 시간을 많이 썼는데, 재귀를 이용한 다른 풀이를 익히느라 고생했다. 시험에서는 조합을 이용해 쉽게 풀었으나 원..

0. 목차 1. Dynamic Programming (DP) 2. 외판원 순회 문제(TSP) 어제는 일요일이었기에 TIL을 생략하고 8일차 TIL을 업로드한다. 그렇다고 어제도 공부를 하지 않은 것은 아니었는데, 어제부터 시작해 오늘까지 하루종일 괴롭혔던 건 외판원 순회 문제(TSP)였다. 먼저 외판원 순회 문제에 대한 설명을 읽어보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지..

첫날부터 흡사 정글에 있는 듯한 기분을 느끼게 했던 0주차 프로젝트가 끝나고 어제 목요일, 1주차 알고리즘 풀이에 들어섰다. 자료구조/알고리즘 문제를 공부하며 컴퓨팅 사고로 전환하는 것이 앞으로 4주 간의 목적이다. 알고리즘은 연구실에 있던 시절에 취미로 조금씩 풀어봤던 터라(그래봤다 한 30문제 풀었나..) 약간 익숙하긴 했지만 그래봤자 기초 수준이었다. 이번 주에 주어진 문제는 총 36문제. 어제 2시간 + 오늘 하루종일 해서 푼 문제는 25문제였다. 골드바흐의 추측 문제를 제외하면 다 풀기는 했다만 속도가 그렇게 빠르다고 느끼지는 않아 앞으로도 연습이 많이 필요할 것 같다. 모든 문제를 리뷰하기보다 풀면서 기억해두면 좋은 스킬 + 좋다고 생각한 문제 리뷰 정도로 진행하려 한다. 1. 기억해두면 좋은..