전체 글 (87) 썸네일형 리스트형 BOJ 12100 2048 (Easy) www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 보드를 이동시켰을 때 보드위의 숫자들을 합하는 것이 관건인 문제였다. 나는 보드 위의 행 혹은 열을 vector v에 담아 넘겨주면, 그것을 이동시켜주는 merge 함수를 구현하였고, 이동에 따라 v에 담는 순서를 다르게 하여 merge함수에 넘겨주었고, 알아서 합쳐주게 하였다. 그것만 구현한다면, 방향에 따른 처리 순서는 인덱스 처리 문제여서 크게 문제될 것이 없다. 코드는 다음과.. BOJ 7423 합이 0인 네 정수 www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 처음 봤을 때 Naive하게 생각하는 것으로 문제를 풀면서 해를 얻어갔다. 가장 처음 생각나는 풀이는 4중 for문으로 푸는 방법이었고, 이는 시간 복잡도가 O(n^4) 으로 n >= 4000 이였기 때문에 다른 문제들에 비해 넉넉했던 12초도 부족하여 문제 풀이에 적합하지 않았다. 여기서 첫번째로 생각났던 것은 4개의 합을 한꺼번에 찾는 것이 아니라, 2개의 합 + 2개의 합 으로 나누어 생.. BOJ 2252 줄 세우기 www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 연결관계를 파악하기 위해서 graph가 필요하였고, 이를 어떻게 사용해야지 같은 graph에 속한 node간의 선후관계를 파악할 수 있을지 고민하였다. 그래프를 그려보니 가장 첫번째에 줄을 설 수 있는 node는 부모가 없음을 확인하였다. 그 노드를 지워보니 두번째에 줄을 설 수 있는 node들의 후보군들도 부모가 없음을 확인하였다. 여기서 부모가 없는 node를 줄을 세우고 제.. BOJ 11437 LCA www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net LCA 문제이다. (Lowest Common Ancestor ) 사실 이 문제에 대한 최적화 방안은 한창 알고리즘을 공부할 때 같이 스터디를 하는 형한테서 들었지만, 따로 구현은 해보지 않았었다. 처음 이 문제를 접한다면 다들 똑같은 생각을 할 것이다. (물론 나도 처음에는 같은 생각을 했었다.) "시작 node들로부터 depth가 같은 ancestor 까지 탐색을 진행 한 뒤, 방금 구한 ancestor.. BOJ 4386 별자리 만들기 www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 보자마자 greedy하게 짧은 간선들을 선택하면 어떨까 생각을 하였고, 이게 정답을 항상 낸다는 보장이 있나 생각하던 찰나에 이와 완전히 같은 크루스칼 알고리즘이 생각났다. 크루스칼 알고리즘 증명은 위키에도 있지만, 추후에 정리해보도록 하자. ko.wikipedia.org/wiki/%ED%81%AC%EB%9F%AC%EC%8A%A4%EC%BB%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#.. BOJ 1806 부분합 www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 처음 보고 생각난 Naive한 방법은 모든 경우의 수를 계산해보는 방법이었다. 합 배열을 만드는데 O(N), 시작점-끝점 경우의 수가 N^2/2 이므로, 해당 방법은 O(N^2 + N) 으로 시간내에 풀이가 불가능했다. 문제 조건을 잘 보니 "수열의 값은 자연수"임을 확인할 수 있었다. 그렇다면 arr [ i : j ] 의 합을 구한 상태에서 arr [ j ] 을 더한다면 항상 arr [ i : .. BOJ 2467 용액 www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 처음 생각한 방법은 모든 숫자쌍을 비교하는 것이였다. 하지만, 시간복잡도가 O(n^2) 였기 때문에 해당 문제를 시간 내에 푸는 것은 불가능 했다. 문제를 보면서 곰곰히 생각해보니, 두 숫자의 합의 절대값이 작은 경우들만 추려서 확인하면 될 것 같다는 생각이 들었다. 그렇게 하기 위해서는 배열을 정렬한 뒤, 양 끝에서부터 중앙으로 다가오는 포인터를 두어 포인터가 가리키는 두 정수의 절대값을 비교하면서 인덱.. 이전 1 ··· 8 9 10 11 다음