고인물을 지양하는 블로그

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 올 2월 겨울방학 스터디 때 교수님이 backtracking 소개를 해주시며 처음 접하게 된 문제로, 가장 기본적인 backtracking 문제이다. brute force를 이용한 문제 해결의 시간 복잡도를 알아보면, 해당 위치에 퀸을 놓을 수 있는지 확인하는 possible 함수가 //(O(N^N)//) 번 호출되는데, 그 때마다 //(O(N)//) (혹은 //(O(N)//)) 시간을 들여 그 자리에 놓을 수 ..

Function Templates Class Templates Template Specialization Template Aliases (C++11) Variadic Templates (C++11) Variable Templates (C++14) 템플릿은 함수, 클래스 등이 제너릭 타입에서 동작할 수 있도록 하는 기능이다. 템플릿의 장점은 매 type별 명시적 함수 overloading 없이도 정의된 하나의 클래스/함수에서 여러 type에 대응해 동작할 수 있게 하는 데 있다. 템플릿은 크게 세 종류로 구분된다: class templates, function templates, variable templates (C++14) C++11부터 템플릿은 variadic 이거나 non-variadic이다. 이전..

https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다. www.acmicpc.net 일전에 작성했던 간단한 크루스칼 알고리즘으로 접근했다가 오답이 나왔다. 문제 이해를 조금 잘못했는데, 임의의 정점간 통신에 걸리는 시간이 원래 네..

크루스칼 알고리즘은 여러 개의 트리를 하나의 트리로 키워나가는 알고리즘이다. 간선의 길이가 짧은 엣지 순으로, 두 정점 {u,v}가 서로 다른 집합에 있으면 연결한다. 슈도 코드는 다음과 같다. MST = ∅ 모든 v ∈ G.Vertex에 대해: v가 속한 집합을 자기 자신(v)로 초기화 (u, v) ∈ G.Edge 의 가중치가 증가하는 순서대로 정렬; 정렬된 (u, v) ∈ G.Edge 에 대해 n-1개의 Edge가 추가될 때 까지: if FIND-SET(u) ≠ FIND-SET(v): // 정점 u, v가 속한 집합이 다르면 (서로 연결이 안됐으면) MST = MST ∪ {(u, v)} // MST에 엣지 추가 UNION(FIND-SET(u), FIND-SET(v)) //u, v 같은 집합에 추가 (..

종강 직후인 6월 24일 ~ 8월 23일까지 여름방학 싹싹 긁어 알고리즘 & 관심분야 공부에 투자했다. 가장 큰 목표였던 알고리즘은 백준 기준 평균적으로 한 주에 15문제 정도를 푼 것 같다. 금요일 저녁 집 가기 전, github에 push 하며 한 주간 풀었던 문제 수를 셀 때가 가장 뿌듯했다. 개강이 다가오면서 비교적 간단한 DFS/BFS 문제들은 제쳐두고 조금 난이도 있는 문제들에 도전해 봤는데, 확실히 시간이 지나며 구현에 걸리는 시간은 줄어든 것을 느꼈다. 다만.. 아무리 반례를 찾아봐도 절대 통과가 안 되는 문제들이 생길 때에는 정말 때려치고 그냥 짐 싸서 집에 가고 싶었다. 일례로, USACO 기출문제였던 문제가 있었는데, USACO TC는 모두 통과해도 백준에서는 통과를 못하는.. 이런 ..

데이터를 그룹으로 나누기 SELECT~ FROM 테이블명 GROUP BY 열명1,[열명2, ...] 지정한 그룹 열마다 집약해서 그룹 열로 나눈 그룹 수의 결과를 되돌려준다 select district, count(*) from city where countrycode="KOR" GROUP BY district; +---------------+----------+ | district | count(*) | +---------------+----------+ | Cheju | 1 | | Chollabuk | 6 | | Chollanam | 5 | | Chungchongbuk | 3 | | Chungchongnam | 6 | ... | Kyonggi | 18 | | Kyongsangbuk | 10 | | K..

이번 학기 수강할 데이터베이스 과목 수업 이전에, 데이터베이스의 기본 및 DBMS의 기본 기능들을 공부하기 위해 방학 마지막 주도 반납한다. ㅠㅜ show databases; +--------------------+ | Database | +--------------------+ | information_schema | | mysql | | performance_schema | | sakila | | sys | | world | +--------------------+ show 키워드를 이용, 데이터베이스 항목을 출력한다 use world; Database changed sample의 world 데이터베이스(스키마)를 이용한다. use 키워드를 이용, 이용할 데이터 베이스를 선택한다. 이후부터 관계형 데..

https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 가중치이다(1 ≤ i ≤ n). 셋째 줄부터 마지막 줄까지는 에지 리스트가 주어지는데, 한 줄에 하나의 에지를 나타낸다. 에지는 정점의 쌍으로 주어진다. 입력되는 정수들 사이에는 콤마가 없고 대신 빈칸이 하나 혹은 그 이상 있다. 가중치 www.acmicpc.net 목차 독립 집합의 크기 최대 독립 집합의 원소들 찾기 독립 집합의 크기 독립 집합의 정의는 다음과 같다. 그래프 G(V, E)에서..