Pearl

https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 원트에 자력솔 성공했다! 채점 돌아갈 때 심장이 넘 떨렸다... 내가 구현을 깔끔하게 잘 못짜는 편이라 코드가 너무 길어지기도 했고 내가 생각한대로 딱! 구현하려다보니 뭔가 꽉 막힌 구현이 된 것 같다. 어제 알고리즘 캠프에서 그리디를 배워서 오늘 그리디 문제를 뒤적거리다가 전에 누가 추천해준 문제이기도 하고, 어제 푼 난이도랑 비슷할 것 같아서 골랐다. 그리디 접근 방식을 연..

해당 수업에서 최단거리를 구하는 여러 가지 알고리즘에 대해 간단히 리뷰했다. 0-1 BFS, 다익스트라, 벨만포드 정도를 간단하게 알려주셨다. 직접 해당하는 알고리즘의 문제를 풀면서 배운 점을 적어놓으려고 한다. 13549 - 숨바꼭질 3 (G5)https://www.acmicpc.net/problem/13549이 문제는 아마도 저번 여름 캠프때 나왔던 것 같다. 이미 풀려있는 문제여서 다시 C++으로 풀어보면서 재제출했다.사실 내게 다익스트라는 골드 하위 문제 날먹 알고리즘 정도였는데.. 한 때 스트릭 용으로 G4~G5 정도의 기본 다익 문제만 푼 적이 있다. 그런데 이렇게 연습해도 응용 문제가 되면 헷갈리는 것 같다. 아직 경험이 부족해서 그런가보다. 그래프의 형태가 기본 그래프와 달라지거나, 특수한..

23년 여름 대회 참가를 위해서 급조(?)한 팀이 같은 뜻을 가지고 오래 지속되어 기쁘다. 대회 이후에도 쭉 같이 스터디를 하고 내용을 기록하고 있다. 다만 블로그에 전부 올리기는 무리라서.. 지금까지 한 번도 안올렸는데, 중간 점검 차원에서 블로그에 포스팅하게 되었다. 아무래도 우리 학교는 알고리즘보다 개발 동아리/개발쪽 행사들이 메인인 분위기라서 같이 알고리즘 공부할 사람을 찾는 게 어렵다. 그나마 찾으려고 하면 거의 졸업할 때 쯤 코테를 준비하느라 효율적으로 몇문제 푸시는 분들 정도? 그동안 교내 자율 스터디에 조금씩 참여했었는데 다들 하루 한문제 인증만 하는 식이고, 알고리즘에 대해서 더 공부하거나 같이 이야기를 나누거나 하는 일은 없었다. 아무래도 알고리즘에 재미를 붙이고 쭉 이어나가는 사람은 ..

다익스트라(또는 데이크스트라) 알고리즘은 특정한 시작점에서 다른 모든 점들로 가는 최단거리를 구하는 알고리즘이다. 그래프 내에서 시작점과 연결되지 않은 노드가 있을 수도 있다. (최단 거리를 구할 수 없는 노드) 이렇게 연결되지 않은 경우를 나타내기 위해 거리를 나타내는 배열 dist = [ ] 의 초기 값을 INF (매우 큰 수)로 설정해주는 것이 일반적이다. 물론, 여러 간선의 가중치 합이 아무리 커도 INF 보다는 작을 것이라는 제한 조건이 붙어야 한다. 이렇게 구현하면, if dist[node] == INF 일 때, 시작점과 해당 노드가 서로 연결되지 않아서 최단 거리를 구할 수 없다는 뜻이 된다. 본격적으로 다익스트라 코드를 구현해보자. 제대로 공부하기 전에 구현된 코드를 복사해서 쓰지 말고, ..

이진 탐색은 이미 순서대로 정렬된 arr에서, 특정 값을 보다 빠르게 찾기 위해서 사용되는 방법이다. 처음부터 차례대로 탐색하는 순차탐색 O(N) 과 다르게, 중앙값 mid 를 기준으로 나눈 arr에서 target이 앞/뒤 중 어디에 위치하는지를 찾는다. 이진 탐색의 시간 복잡도는 O(log N) 으로, 보다 빠른 탐색이 필요한 PS에서 유용한 라이브러리로 사용할 수 있다. 이진 탐색 함수를 짤 때 두 가지 방법으로 짤 수 있다. 하나는 재귀적으로, 남은 하나는 반복적으로 짜는 방법이다. 간단하게 PS 용으로 쓰기 위해서는 반복적인 방법을 주로 사용한다. 코드 짜기 쉽고, Python의 재귀 깊이를 고려하지 않기 위함이다. 또한, 이진 탐색 코드를 짤 때 주의할 점이 있다. (1) 탐색을 진행할 arr가..

1. Heap Heap : 무더기, 더미를 의미함 컴퓨터 기억 장소에서 일부분이 프로그램에 할당 되었다가 회수되는 작용이 되풀이되는 영역 Heap의 기억장소는 대부분 Pointer 변수를 통해 동적으로 할당받고 돌려줌 아래 메모리 구조 그림을 참고 2. 자료구조 Heap 자료구조로 쓰이는 Heap: 데이터에서 최댓값, 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리 완전 이진 트리: 자식노드가 왼쪽부터 꽉 채워지는 트리 부모 노드 index = 자식 노드 index // 2 Left 자식 노드 index = 부모 노드 index * 2 Right 자식 노드 index = (부모 노드 index * 2) + 1 배열로 구현할 때 index 1부터 시작하는게 편함 3. Heap 사용 이유 배열에서 max,..