잡담연구소

A - 평범한 배낭 B - 연구소 C - 암기왕 D - 스타트 택시 E - 상근이의 여행 F - 감소하는 수 1204 기분 개좋음 왜냐? 3문제나 풀었기 때문ㅜ 야호 평범한 배낭은 저 배낭 알고리즘 공부할 때 설명했으니까 pass E. 상근이의 여행 9372번 (www.acmicpc.net/problem/9372) 이제 유니온파인드나 크루스칼 알고리즘은 나의 favorite 가뿐하다구욧 #include #include #include using namespace std; //vector airplane; vector parent; int getparent(int x) { if (parent[x] == x) return x; return parent[x] = getparent(parent[x]); } vo..

요새 넘나 소홀했던 거 ㅇㅈ 그래서 반성하는 마음으로 알고리즘 스터디 한 당일 날 배운 알고리즘을 정리한당,,,흑,,, 앗 스터디장님이 새로 바뀌셨다. 기존 상규님이 갓카오에 합격하는 바람에 녹형님이 새로운 스터디장이 되셨다. 상규님이 하시는 모든 일 다 잘됐으면 좋겠다 ㅎㅣㅎ ' 배낭 알고리즘은 다이나믹프로그래밍 dp 유형 중 하나다. 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은? 가방의 최대 용량은 10kg 이고 현재 보석은 이렇게 6개가 있다고하자. 그러면 6개 중 10kg를 넘지 않게 잘 골라서 가장 비싼 것들..

크루스칼 알고리즘 (Kruskal algorithm) 스터디장님 설명듣고 동빈나 블로그 보고 크루스칼 알고리즘 복습함 (m.blog.naver.com/ndb796/221230994142) 갓동빈님 1. 간선의 크기만큼 그래프를 생성한다. 2. 각 간선에는 연결된 노드들이 적혀있다. 3. 간선들을 오름차순으로 정리한다. 4. 간선 값이 가장 작은 녀석부터 이어간다. 여기서 유니온파인드를 이용한다. 5. 만약 간선의 두 노드가 이미 연결되어있다면 SKIP 해버린다. → 왜? 오름차순으로 정렬된 상태에서 진행되기때문에 만약 연결되어있었다면 이전의 간선 값이 더 작을 것이기 때문이다. 6. 모든 부모노드가 1이 되면 (꼭 1일 필요없음 그냥 연결만 되면 됨) 끝내버린다. 이걸 코드로 구현을 해보자 백준 1197..

유니온 파인드 (union-find) 동빈나 유튜브로 예습하고 스터디장님 설명 듣고 문제풀려는데?! 기억이 안남 그래서 다시 동빈나 블로그로 예습함. ( m.blog.naver.com/ndb796/221230967614 ) 1. 맨처음 부모노드를 자기 자신으로 초기화한다. 1 2 3 4 1 2 3 4 2. 주어진 두 인덱스에 대해서 부모노드가 다르다면 부모노드를 같게 만들어준다. → unionparents 인덱스번호가 더 작은 쪽으로 부모노드를 바꾸는 게 국룰인거 같습니다. 큰 쪽이어도 상관은 없음 EX) 1,3 번을 합하라 1 2 3 4 1 2 1 4 EX) 2,4 번을 합하라 1 2 3 4 1 2 1 2 EX) 2,3번을 합하라 1 2 3 4 1 1 1 2 원래 2번이랑 4번은 부모노드가 2로 같았는..

영어논문 스터디의 스타트를 내가 맡게 되었다. 이번에 내가 준비한 논문은 CNN 모델의 조상격인 ImageNet Classification with Deep Convolutional Neural Networks 알렉스넷이라고 더 잘 알려져있는 모델이다. PPT로 설명을 해보자 비전 분야의 올림픽이라고도 불리는 ILSVRC라는 이미지 인식 대회가 있는데 imagenet에서 제공하는 이미지 subset을 모델이 얼마나 잘 인식하는지를 평가하는 대회입니다. 2012년도 ILSVRC 대회에 2등과 10% 이상의 압도적인 성능차이를 보이며 혜성같이 alexnet이 1등을 손에 거머쥐게 됩니다. 왜 알렉스넷이냐!하면 논문의 제 1저자 이름이 알렉스이기 때문이죠 ㅋㅋㅋㅋㅋ 그 전년도인 2011년도에 우승을 했던 sv..

이건 동빈나 prefix sum보다가 우연히 보게 됐는데 이번주 스터디 숙제에도 껴있었다. youtu.be/rI8NRQsAS_s 이건 쉬워서? 맞나? 바로 이해함 오홍 단조 증가 / 감소해야지 투 포인터를 쓸 수 있는 것 같다. 그래야 특정 값이 나오면 end를 멈춰버리고 start를 갱신! 백준 2003번 수들의 합2 (www.acmicpc.net/problem/2003) #include #include #include using namespace std; vector arr; int main() { int n, m , number; cin >> n >> m; arr.resize(n + 1); for (int i = 1; i > m; arr.resize(n + 1); for (int i = 1; i