백준 온라인 저지, 1557번: 제곱 ㄴㄴ 도입 이 문제는 뫼비우스 함수를 사용하여 Square-free Integer(SFI)를 다뤄야 한다. 뫼비우스 함수를 어떻게 사용할 수 있는지 알 수 있는 좋은 문제이지만, 아직까지 그 외에 뫼비우스 함수 자체를 가져다 쓸 수 있는 사례는 찾지 못했다. 문제 파악하기 1부터 시작하여 $K$번째 SFI...

백준 온라인 저지, 10696번: Prof. Ossama 도입 이 문제는 지인에게 추천받아 풀어보게 되었다. 문제가 요구하는 것은 생각보다 간단하지만, 채점에 사용되는 테스트 케이스가 상당히 흥미롭다. 문제는 단순히 입력으로 주어진 n, x 에 대해 n % x 처리를 하면 된다. 즉, 아래와 같이 구현할 수 있다. from sys import ...

백준 온라인 저지, 5052번: 전화번호 목록 도입 문제의 목표는 주어진 전화번호들 중 어느 전화번호가 다른 전화번호의 시작 부분(접두어)가 되는지 확인하는 것이다. 예시로 주어졌듯, 911은 91125426의 시작 부분이므로 문제의 표현에 따르면 “일관성이 없는 번호 목록”이라고 할 수 있다. 문제 풀어보기 조건에 따르면 최대 10자리 전화...

도입 단순히 제시된 수열에서 두 수를 뽑아 곱하는 모든 경우를 구해 더하는 것이 목표이다. # n, nums = n, [...] result = 0 for i in range(0, n): for j in range(i, n): if i == j: continue result += nums[i] * nums[j] ...

백준 온라인 저지, 1647번: 도시 분할 계획 도입 제거할 도로를 선택하는 것과 남길 도로를 선택하는 것은 본질적으로 같으므로 제거할 도로를 선택할 대신 남길 도로를 선택하는 것으로 생각할 수 있다. 위와 같이 생각하면 단순히 가중치가 제시된 연결선에서 몇 개의 연결을 선택하여 최소한의 가중치 합을 갖는 트리, 즉 최소 비용 스패닝 트리를 구하...

백준 온라인 저지, 16724번: 피리 부는 사나이 도입 제시되는 모든 타일은 이동 방향을 지시하고 있다. 즉 어떠한 타일에 위치하든 회원들은 계속해서 일정한 경로를 순회하거나, 벽(맵의 바깥)에 막혀 이동이 정지될 것이다. 일정한 경로를 순회하도록 하는 타일의 집합도, 특정한 목적지가 있는 타일의 집합도 모두 각각 그룹화할 수 있다. 문제 풀...

백준 온라인 저지, 2166번: 다각형의 면적 문제 파악하기 입력으로 다각형 꼭짓점의 좌표가 주어진다. 이 좌표만을 사용하여 다각형의 면적을 구해야한다. 꼭짓점은 다각형을 구성하는 순서대로 제공하므로, 굳이 순서를 변경하여 문제의 의도와 다른 다각형을 고려할 필요는 없다. 문제 풀어보기 문제에서 제시하는 도형은 다각형이기만 무엇이든 가능하므로...

백준 온라인 저지, 1202번: 보석 도둑 도입 모든 가방에 대해, 각 가방이 담을 수 있는 무게 한도 내에서, 가장 가치가 높은 보석을 담도록 하는 문제이다. 가방이라는 단어가 있지만 한 가방에 한 개의 보석만 담을 수 있으므로 냅색 문제는 아니다. 문제 풀어보기 각 가방이 허용하는 무게 범위 내에서 최대의 가치를 지닌 보석을 선택하면 되므...

백준 온라인 저지, 1197번: 최소 스패닝 트리 도입 가장 기본적인 최소 비용 스패닝 트리 문제이다. 제시된 그래프에서 최소 스패닝 트리를 구성할 수 있는 간선만 선택하여 간선 가중치의 합을 구한다. 풀어보기 대표적인 최소 비용 스패닝 트리 알고리즘인 프림 알고리즘을 사용하였다. 간선의 가중치를 기준으로 모든 간선 정보를 정렬. 가...

백준 온라인 저지, 2473번: 세 용액 도입 기본적으로 두 용액 문제의 변형이다. 두 용액 문제에서는 용액을 두개만 합성하지만, 이번에는 세개를 합성한다. 용액 합성의 개수가 늘었지만, 두 용액에서 한개만 더 늘었을 뿐이므로 다소 무식하게 접근할 수 있다. 풀어보기 두 용액에서 전체 용액에 대해 투 포인터를 사용했다면, 세 용액에서는 용액 ...