코딩 연습장

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..

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, ... 어디서 많이 본... 피보나치네요. 그림그리는게 문제 푸는 것보다 오래 걸린 문제네요. 수고하세용 :)

오랜만의 글 이네요. 백준 5549번 - 행성 탐사입니다. https://www.acmicpc.net/problem/5549 전형적인 구간합 문제 입니다. N x M 크기의 행성의 지도와, 조사 대상 영역 K개 각각의 양 끝 좌표가 주어집니다. 행성을 한 번 탐사하기 위해 걸리는 시간은 O(NM), 즉 모든 K에 대해 재탐사를 수행한다면 시간 복잡도는 O(KNM)이 됩니다. 따라서 탐사는 재탐사는 불가능합니다. 한 번의 탐사 결과를 기억해서 재활용합시다. 간단하게 (1, 1)부터 시작해서 (X, Y)까지 탐사 결과를 dp[ X ][ Y ]에 저장합니다. 이제 (X1, Y1)부터 (X2, Y2),까지의 탐사 결과는 구간합(prefix-sum)을 이용하여 쉽게 구할 수 있습니다. 위와 같이 N x M이 4구..

백준 1325번 - 효율적인 해킹입니다. https://www.acmicpc.net/problem/1325 학부 과제로 비슷한 유형의 문제를 풀어본 적이 있어 금방 해결하였습니다. 연결된 네트워크상에서 컴퓨터를 해킹할 수 있는 개수를 찾는 문제입니다. 예제 입력1을 그림으로 표현하면 이와 같습니다. 화살표는 신뢰받고있는 관계, 즉, 해킹할 수 있는 방향을 의미합니다. 이 경우에는 1 혹은 2를 해킹하면 네트워크 상의 모든 컴퓨터를 해킹할 수 있습니다. 간단하게 해결하기 위해 인접리스트를 사용합니다. 인접리스트는 그래프의 연결관계를 리스트로 표현한 것입니다. 인접 리스트는 주로 인접 행렬과 비교되는데, 노드가 N개, 간선이 E개라고 했을 때, 연결된 모든 노드를 방문하기 위해 인접 행렬은 행렬의 모든 값을..