WOONY's 인사이트

0. 목차 1. 사냥꾼(#8983) 문제 2. 철로(#13334) 문제 P.S. 파이썬 sort 조건 설정 관련 팁 1. 사냥꾼 (#8983) 문제 링크: https://www.acmicpc.net/problem/8983 사냥꾼은 이제 확실히 이해해서 풀이를 업로드! 예외 조건을 잘 처리해야 100점이 가능하다. 1번 풀이: 이중 for문 이용 (시간 복잡도: O(N^2)) => 60점 1번 풀이는 가장 먼저 이 문제에 접근할 때 썼던 방법이다. 당시만 해도 아직 이분 탐색에 익숙치 않던 시절이었다. 바로 떠오르는 방법이라고는 for문 두 번 돌리기 밖에 없었다. 이 문제는 부분 점수가 주어지는 문제여서 의외로 60점이라는 높은(?) 점수를 받긴 했으나 완벽한 풀이는 아님. 방식은 이렇다. 놓여진 사대에..

0. 목차 1. 힙 자료구조 & heapq: Heap 모듈 in python 2. 가운데를 말해요 원래 오늘 정리하고 싶었던 문제는 원 영역이었는데..아 진짜 다른 풀이를 봐도 뭔가 명쾌한 이거다! 싶은 느낌이 오지 않는다. 오일러 지표(v-e+f=c)를 푸는 풀이, DFS를 이용하는 풀이 등 다양한 방식이 있는데 아직 잘 체감이 되지 않는다. 이 문제는 손에 좀 더 익히고 나서 정리하도록 할 예정. 오늘은 힙 구조에 대해 정리하고 관련 문제인 "가운데를 말해요"에 대해 정리한다. 내일은 이제까지 미처 정리 못했던 문제 중 중요한 애들(이분 탐색 - 사냥꾼 / 스택 - 원 영역, 괄호의 값, 크게 만들기 / 큐 - 뱀) 다시 정리해볼 예정..! 할 수 있다! 1. 힙 자료구조 & Heap 모듈 힙 자료구..

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

1. A Tour of Computer Systems 컴퓨터 시스템: 하드웨어 + 소프트웨어가 함께 동작해서 응용 프로그램을 돌리는 개념. 이 책에서 배울 것은 Practical skills such as how to avoid starage numerical errors How to optimize my C codes by using clever tricks compiler 등. (원서로 보다보니 100% 이해하는데 부족함이 있는지라 내용에 오류가 있다면 꼭 말씀해주세요..) 1-1. Information is Bits + Context 여기 C로 짠 프로그램이 하나 있다. 이를 hello라고 하자. #include int main() { printf("Hello, World!"); return 0; ..

오늘은 어제에 이어서 계속해서 이분 탐색 문제를 풀었다. 진도가 생각만큼 빠르게 나가지 않아 답답한 감이 없잖아 있다. 내일부터는 한 문제당 푸는 시간 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. 안전 영역 풀이 (with 재귀 dfs) 2. 정렬 알고리즘 정리 - 버블, 선택, 삽입 정렬 + 힙 정렬까지 1. 안전 영역 풀이 (with 재귀 DFS) 안전 영역은 백준 알고리즘 #2468번 문제다. 문제 내용이 기니 링크를 타고서 직접 확인해보도록 하자. 이 문제는 재귀를 이용한 DFS 방식으로 푼다. 재귀는 자기 자신을 호출하면서 스택처럼 쌓이기 때문에 DFS를 구현하기에 좋은 알고리즘이다. *재귀와 스택 관련 내용은 아래 링크에서 확인하기. https://ko.javascript.info/recursion 재귀와 스택 ko.javascript.info 곧바로 풀이로 넘어간다. 풀이는 다음 링크를 참고해 풀었다. 풀이를 소개하기 전, 먼저 설정해야 할 조건이 하나 있다. 본 풀이..

0. 목차 1. BFS - 큐 2. DFS - 스택 오늘은 사족 없이 빠르게 가보자. 아래와 같이 두 그래프가 있다. 보다시피 그래프 자체는 동일하다. 하지만 어디서부터 데이터를 읽어오는지 그 순서가 다르다. 1. BFS (Breath First Search) 왼쪽의 빨간 경로는 너비 우선 탐색인 BFS에 해당한다. 시작 노드에서 가까운 노드부터 순서대로 방문하는 탐색 알고리즘이다. 오른쪽의 DFS는 보다시피 경로 하나하나가 깊이를 주구장창 파는 반면, BFS에서는 시작 노드를 기준으로 동일한 레벨(=뎁스)에 있는 노드를 병렬적으로 방문하는 방식이다. 이를 구현하는 방식을 이해하려면 큐(Queue) 자료구조를 이해할 필요가 있다. 언젠가 큐와 스택을 구별하는 아주 명쾌한 설명을 읽은 적이 있는데, 큐는 ..

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