코딩 연습장

1005. ACM Craft (G3) https://www.acmicpc.net/problem/1005 1516. 게임 개발 (G3) https://www.acmicpc.net/problem/1516 2623. 음악프로그램 (G2) https://www.acmicpc.net/problem/2623 2252. 줄세우기 (G2) https://www.acmicpc.net/problem/2252 더보기 Topological Sort, O(V + E) 기본 위상정렬 문제 각 버텍스에 도달한 최대시간 or 적당히 붙이기.. 1707. 이분 그래프 (G4) https://www.acmicpc.net/problem/1707 더보기 Graph, O(V + E) 두가지 색으로 칠하면서 BFS 8452. 그래프와 쿼리 (..

4195. 친구 네트워크 (G2) boj.kr/4195 더보기 DisjointSet, O(T * N * a(N)) 유니온파인드 연습 문제, 맵을 이용해 각각의 사람에 id를 할당하고 이를 union-find, 유니온할때마다 Set의 사이즈를 출력해주면 됨 3697. 정상 (P4) boj.kr/3697 더보기 BFS + DisjointSet, O(NM * log(NM) 맵에서 높은 순서대로 Queue에 삽입, 한개씩 꺼내서 BFS 및 라벨링 라벨링이 된 곳을 방문(d-차이 이내로)할 수 있다면 d-정상이 아님 방문하는 같은 높이를 카운팅하였다가 d-정상이라면 결과에 더해줌 1194. 달이 차오른다, 가자. (P5) boj.kr/1194 더보기 BFS + Bitmask, O(6! * NM) 키 보유 상태에 ..

2206. 벽 부수고 이동하기 (G4) boj.kr/2206 14442. 벽 부수고 이동하기 2 (G3) boj.kr/14442 16933. 벽 부수고 이동하기 3 (G1) boj.kr/16933 더보기 Graph, O(NM) 2206, 14442 -> 1을 k번 통과할 수 있는 bfs, 벽을 부순 횟수까지 포함하여 방문 처리 16933 -> 밤/낮 추가된 버전, 같은 방법으로 bfs, 밤낮을 포함하여 방문 처리 16946. 벽 부수고 이동하기 4 (G2) boj.kr/16946 더보기 Graph, O(NM * a(K)) 연결요소(0으로 이루어진 군집)를 라벨링하여 크기를 기억한 후, 1을 만날 때마다 주위 4칸의 합계를 출력 17136. 색종이 붙이기 (G3) boj.kr/17136 더보기 Back-t..

3197. 백조의 호수 (G2) boj.kr/3197 더보기 Graph + DisjointSet, O(NM * a(K)) 모든 영역을 라벨링하여 큐에 넣은 뒤, 백조가 속한 두 영역이 합쳐질 때까지 한 칸씩 BFS 17406. 배열 돌리기 4 (G5) boj.kr/17406 더보기 Permutation + Simulation, O(K! * KNM) 주어진 쿼리의 순서를 바꿔가며 회전을 수행한 후 배열의 값을 계산 6593. 상범 빌딩 (G4) boj.kr/6593 더보기 Graph, O(T * LRC) 단순 3차원 BFS, 채점 시간을 보니 테스트케이스가 다소 부실하지 않나 생각 2636. 치즈 (G5) boj.kr/2636 2638. 치즈 (G4) boj.kr/2638 더보기 Graph, O(K * N..

문득 드는 생각. 나는 대학교에서 자료구조를 배울 때 pop에 반환 값이 있는 형태로 배웠는데, 왜 STL에선 pop과 top을 나눠놓았을까? 에 대한 이유이다. 우선 STL stack의 pop, top 함수의 원형을 살펴보면 다음과 같다. void pop( ) { c.pop_back( ); } reference &top( ) { return (c.back( )); } pop은 맨 위의 요소를 버리는 연산, top은 맨 위의 요소를 반환하는 연산이다. Java처럼 pop 연산이 맨 위의 값을 꺼내서 반환하는 일반적인 스택과는 다소 차이가 있다. STL에서 top과 pop을 분리한 데는 여러 이유가 있다. Command–query separation(CQS) 원칙을 지키기 위해서가 될 수도 있고, 효율이 ..

간만에 업데이트 했길래 잠깐 플레이했습니다. 여전히 갓겜이네요.

https://www.acmicpc.net/problem/11003 A[i], A[i-L+1] 사이에서 최소값을 찾는 슬라이딩 윈도우 문제입니다. 아무생각없이 원형큐에 검사해야할 값들 저장해서 최소값찾기 했더니 O(nl)이라 시간초과로 실패했습니다. 기억해야할, 혹은 의미있는 변수들을 고민해봅시다. 우선, 윈도우에서 가장 작은 값. 윈도우에 들어오는 값 - 가장 작은 값과 비교하여 가장 작은 값을 갱신해야 합니다. 윈도우에서 나가는 값 - 나가는 값이 가장 작은 값이라면 가장 작은 값을 그 다음으로 업데이트해야 합니다. 이때, 그 다음 값을 순서대로 모두 기억하고 있어야합니다. 만약 1, 2, 3, 4, 5 처럼 오름차순의 입력이 주어진다면 슬라이딩 윈도우의 크기만큼 최솟값을 모두 기억하고 있어야 출력할..

백준 11726번 - 2xn 타일링입니다. https://www.acmicpc.net/problem/11726 DP를 공부했다면 한 번쯤 봤을 문제입니다. 상당히 간단합니다. N=1일 때부터 하나씩 채워나갑시다. 구분하기 편하게 알록달록 색을 넣었습니다. 청색, 황색 블럭은 기존에 타일링에 이용했던 모양, 녹색 블럭은 n이 증가함에 따라 새롭게 추가된 모양입니다. 이런 규칙으로 구해보면 N 출력 1 1 2 2 3 3 4 5 5 8 6 13 7 21 8 34 9 55 ... 1, 2, 3, 5, 8, 13, ... 어디서 많이 본... 피보나치네요. 그림그리는게 문제 푸는 것보다 오래 걸린 문제네요. 수고하세용 :)