본문 바로가기

전체 글210

[BOJ] 13460 : 구슬 탈출 2 문제 링크 13460번: 구슬 탈출 2 (acmicpc.net) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 조금 까다로운 BFS 문제. 풀이 입력으로 보드의 모양과 구멍, 빨간구슬, 파란구슬의 위치가 주어진다. 보드를 기울이면 벽이나 구멍을 만나기 전까지 구슬은 굴러간다. 그리고 두 구슬은 만날 수 없다. 큐에는 {빨간 구슬의 위치, 파란 구슬의 위치, 기울인 횟수}를 넣어주었다. (이하 빨간 구슬 = R, 파란 구슬 = B) 그리고 기울인 횟수가 10을 .. 2022. 2. 22.

[BOJ] 3665 : 최종 순위 문제 링크 3665번: 최종 순위 (acmicpc.net) 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 풀이 작년도에 비해 상대적 순위가 바뀐 팀들의 목록을 보고 올해 팀들의 순위를 알아내는 문제. 팀별로 순위가 있는 위상정렬 문제이다. 먼저 작년도 순위를 기준으로 위상을 설정해준다. 예시를 보자. 작년순위가 5->4->3->2->1 이다. 인접 행렬이나 인접 리스트로 간선을 만들면서 각 노드의 indegree 값도 찾아준다. 1. 5->4, 5->3, 5->2, 5->1, 4->3, 4->2, 4.. 2022. 2. 21.

[BOJ] 24453 : 디버깅 문제 링크 24453번: 디버깅 (acmicpc.net) 24453번: 디버깅 첫 줄에는 자동으로 작성된 코드 줄의 수 $N$과 오류가 있는 줄의 개수 $M$이 주어진다. $(1 \le N \le 2 \times 10^7$, $1 \le M \le \min(N,\ 5\times 10^5))$ 두 번째 줄에는 코드에서 오류가 있는 줄의 번호 $M$개가 www.acmicpc.net 인규가 Y개 이상의 오류를 제거한 후 에디터가 제거해야 할 오류의 수의 최대값을 구하는 문제. 풀이 먼저 경우의 수를 나누어 보자. 1. 인규가 아무런 오류를 수정하지 않아도 에디터가 자동으로 오류를 수정해 줄 수 있는 경우 즉, 최초 입력에서 부터 이미 오류가 없는 연속된 코드의 줄의 수가 X이상인 상태. 이런 경우는 인규가 최.. 2022. 2. 18.

[BOJ] 24462 : 일어나...코딩해야지... 문제 링크 24462번: 일어나... 코딩해야지... (acmicpc.net) 24462번: 일어나... 코딩해야지... 첫 번째 줄에 두 정수 알람의 개수 $N$, 건모가 일어나야 하는 시각 $D$가 공백으로 구분되어 주어진다. $(2 \le N \le 1\,000$, $1 \le D \le 10^9)$ 둘째 줄부터 $N$개 줄의 $i$번째 줄에는 알람이 시작되는 시 www.acmicpc.net 우리 학교 대회 문제에 있어서 풀어보았다. 골드 5문제지만 푸는데 시간이 꽤 걸렸다.. ㅠ 풀이 알람을 최대한 많이 울리도록 알람 2개를 선택하는 문제이다. 단 알람이 울리는 시간이 겹칠경우 그건 알람 하나만 울린 것으로 간주한다. 즉 두 개의 알람이 각각 울린 횟수를 더해서 중복된 수만큼 빼주면 된다. 그 값.. 2022. 2. 14.

[BOJ] 4195 : 친구 네트워크 문제 링크 4195번: 친구 네트워크 (acmicpc.net) 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 유니온 파인드 문제 중 입력이 특이하게도 숫자가 아닌 문자열이 주어진 문제. 가장 먼저 고민해야될 것이 입력으로 들어온 문자열을 어떻게 인덱스화 시킬 것인가? 이다. 맨 처음 떠올린 아이디어는 벡터에 문자열들을 저장해두고 벡터의 인덱스를 문자열의 인덱스로 쓸 방법이었다. 그렇게 하면 벡터의 find 함수로 인덱스를 찾으면 된다. 하지만 매번 이렇게 find함수를 사용해서 인덱스를 찾는.. 2022. 2. 11.

[BOJ] 1167 : 트리의 지름 문제 링크 1167번: 트리의 지름 (acmicpc.net) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 임의의 두 정점 사이의 거리중 가장 긴 거리를 찾는 문제 당연히 루트노드에서 탐색을 시작하면 가장 긴 거리를 찾을 수 있을 것이라 생각. 하지만 루트노드에서 탐색하면 모든 정점은 방문할 수 있겠지만 모든 경로를 탐색하지는 못했다. 그렇다고 모든 정점에서 부터 탐색을 할 것인가?? 그럼 시간초과가 난다. 해결 1. 루트노드에서 탐색을 시작해 가장 깊은 노드를 찾는다. (여기서 가장 .. 2022. 2. 9.

[BOJ] 11066 : 파일 합치기 문제 링크 11066번: 파일 합치기 (acmicpc.net) 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 풀이 모든 파일을 합치는 최소 비용을 출력하는 문제. 동적계획법(Dynamic programming)을 활용해야한다. 그 중에서도 2차원 배열을 이용한 DP를 활용해야한다. DP[i][j] 배열에 i부터 j번째 까지의 파일을 합치기 위해 필요한 최소비용을 저장한다. 즉 DP[i][j] = Min(i K; Init(); for (int i = 1; i > File[i]; Sum[i] += Sum.. 2022. 2. 7.

[BOJ] 1450 : 냅색문제 문제 링크 1450번: 냅색문제 (acmicpc.net) 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 용량이 정해져있는 가방에 물건을 담을 수 있는 경우의 수를 구하는 냅색 문제이다. 예제1번을 예시로 보면 물건의 수는 2개, 가방의 최대 용량은 1 2개의 물건은 각각 무게가 1이다. 무게가 같더라도 두 물건은 다른 물건이다. 아무것도 담지않는 경우 1 + 첫번째 물건만 담는 경우 1 + 두번째 물건만 담는 경우 1 이렇게 해서 경우의 수는 3이다. 냅다 그냥 조합으로 경우의 수를 구하면 시간 초과다.. 2022. 2. 4.

[BOJ] 1806 : 부분합 문제 링크 1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 부분수열의 합이 S이상 되는 부분수열중 가장 짧은 길이를 찾는 문제. 골드이상엔 브루트포스로 푸는 문제는 거의 없다고 보면 된다. 이것도 브루트포스로 풀면 당연히 시간초과. 임의의 인덱스 i 에서 i + a 까지의 부분합을 어떻게 빠르게 구할까 반복문으로 i부터 i+a까지 더한다? 효율이 떨어진다 Sum이라는 배열에 각 인덱스까지의 합을 저장한 다음 Sum[i+a] - Sum[i-1]을 .. 2022. 2. 2.

이전 1 ··· 19 20 21 22 23 24 다음

티스토리툴바