분류 전체보기

문제 접근 입력 받은 것들을 인접 행렬로 구현하고, 1번에 대해 DFS 한 뒤 탐색하는 것들의 수를 cnt 변수에 기록해 반환하여 풀었다. 간단한 문제! 문제 코드 #include using namespace std; int v,e; bool adj[101][101] = {false}; bool visited[101] = {false}; int dfs(int n) { int cnt=0; visited[n] = true; for(int i=1; i>v>>e; for(int i=0; i>in>>out; adj[in][out]=adj[out][in]=true; } cout

문제 접근 최대 힙, 최소 힙 코드 응용해서 구현했는데 일단 테스트 케이스는 잘 돌아가고 제출 때 시간 초과가 나온다. 시간 복잡도를 계산해보니 insert 함수는 O(lgN) 인데, delete 함수는 find 함수로 인해 O(N) 이다. lower_bound() 사용 시 O(lgN) 에 찾을 수 있다고 해서 바꿔봤는데 시간 초과는 해결되어도 틀렸다고 나온다. 확인해보니 lower_bound() 는 정렬되어 있는 상태에서 목표값 n 보다 같거다 큰 원소의 주소를 반환하는 함수여서 정렬이 되어있어야 한다. find() 함수를 직접 O(lgN) 으로 구현해보려고 했는데 방법이 없는 것 같다. 문제 코드 ( 시간 초과 ) #include #include #include using namespace std; ..

문제 접근 두 문제는 어떻게 트리를 구성하느냐의 차이이지 사실 상 같은 문제라고 할 수 있다. 처음에는 priority_queue 로 풀어보고, 직접 heap 을 구현해보고 싶어서 구현한 뒤 실행시켜봤다. 예제 케이스와 직접 만들어 본 테스트 케이스에서 잘 돌아가길래 제출해봤는데 '틀렸습니다' 가 나온다. 얼핏 생각해봤을때 이상한 부분이 없기도 하고 조금 피곤해서 잠깐 쉰 뒤 주석 달면서 코드 분석을 했다. 그런데 어머나 웬걸? 원소 삭제하는 함수에서 leaf 를 하나만 가지고 있는 원소가 있으면 오른쪽 leaf 가 없어서 계산에 허점이 생기고 바뀌지 않는다는 걸 알아차렸다! 해당 while 문의 조건을 바꾸고 내부적으로 break 하는 방식으로 바꿨고, 자식이 하나있는 경우는 while 문 외부에서 처..

문제 접근 이 문제는 부분합의 총합이 최소가 되게 하는 문제이다. x 번 사람이 대기하는 시간을 Px 라고 할 때 5명이 대기한다면 부분합의 총합 Ans = 5*P1 + 4*P2 + 3*P3 + 2*P4 + 1*P5 이다. 따라서 n 에 대해 Pn = n*P1 + (n-1)*P2 + (n-2)*P3 + ... + 2*P(n-1) + 1*Pn 이라고 할 수 있다. 고로 작은 순으로 정렬한 뒤 부분합의 총합을 구하면 끝! 문제 코드 #include #include #include using namespace std; int main(void) { int N, ans; cin>>N; vector P(N); for(int i=0; i>P[i]; sort(P.begin(), P.end()); ans = P[0];..

문제 접근 처음에는 STL 의 set 이나 map 을 이용하려 했다. 자동으로 sort 되는 건 좋았지만, find 로 찾은 뒤 (해당 문자열 주소값) - (시작 주소값) 으로 인덱스를 출력하려고 하면 에러나서 이 문제에서 set 을 사용하지 않기로 했다. 에러는 iterator 여서 - 연산자 사용이 불가하는 것이었다. 그래서 vector 에 넣어서 sort 하고 unique 로 중복 제거한 뒤, 마찬가지로 주소값으로 접근했는데 실행은 잘 되지만 시간초과났다. set 에서는 주소값 계산이 안 됐는데 vector 에서는 돼서 왜 그런지 고민하고 찾아봤다. C++ STL 에서 컨테이너는 크게 두 가지 종류가 있는데, 배열처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너(Sequence Container) ..

문제 접근 말 그대로 연결 요소의 개수를 구하는 문제여서, DFS 로 풀었다. 한 연결 요소에 포함되어있는 모든 정점은 그 중 하나의 정점에 대하여 dfs() 를 호출하면 다 방문하게 되니, main 에서 dfs 를 호출하는 횟수가 연결 요소의 개수가 된다. 문제 코드 #include #include using namespace std; // 인접 리스트 vector adj(1001); bool visited[1001] = {false,}; void dfs(int n) { // dfs() 호출할 때 해당 정점 방문한 걸로 처리 visited[n] = true; for(int i=0; i>N>>M; for(int i=0; i>start>>end; adj[start].push_back(end); adj[en..

문제 접근 처음에는 아무 생각없이 코드 작성했는데, 지금 보니까 시간 복잡도가 O(N^2*M^2) 인 것 같다 ( 최악의 경우 cnt 가 N*M 이므로). 시간 초과 나오길래 BFS 로 다시 구현했다. BFS 로 구현한 코드는 시간복잡도가 O(V+E) 인 것 같다. ( V : 값이 1인 정점의 개수, E : 값이 1인 정점에서 값이 0인 정점으로 향하는 간선의 개수 ) 시간 복잡도를 계산하는 것에 조금 더 익숙해질 필요가 있는 것 같다. 문제 코드 ( 시간 초과 ) #include #include using namespace std; // cnt = 0의 개수 // 모든 0이 지워져야되는거니 루프마다 0의 개수를 세기보다는 cnt 를 감소하도록 구현했다. int M,N,cnt=0,ans=0; int bo..

문제 접근 처음에는 모듈러 연산 문제인 줄 알고 단순하게 구현했다. 그런데 2147483646 2147483646 2147483647 넣었을 때 시간이 굉장히 오래 걸렸다. 그래서 생각한 게 모듈러 연산이 제곱에서도 성립하니 제곱에 제곱을 하는 방식으로 조금 더 빠르게 풀 수 있을 것 같았다. 그래서 제곱을 처리하는 모듈러 연산을 알아보던 중 칸 아카데미에서 잘 정리한 글을 찾을 수 있었다. https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation 빠른 모듈로 거듭제곱법 (개념 이해하기) | 암호학이란? | 칸아카데미 ko.khanacademy.org 처음에는 2의..