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

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

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

백준 온라인 저지, 10942번: 팰린드롬? 도입 이 문제는 매우 빡빡한 시간 조건과 매우 넓은 범위의 입력값을 가졌다. 언듯 보면 팰린드롬 여부만 파악하면 될 것 같지만, 1십만 개의 숫자 배열에 대해 최대 1백만회 일정 범위에 대해 팰린드롬에 대해 물어볼 수 있다. 팰린드롬 처리에만 집중한다면 시간 초과가 발생하기 쉽다. 문제 풀어보기 ...

백준 온라인 저지, 27903번: 인생 도입 코드 안에 백준 아이디를 구성하는 그 어떤 문자도 포함할 수 없다. 아이디가 belline0124이므로 b, e, i, l, n, 0, 1, 2, 4를 코드에 사용할 수 없다. 풀어보기 아이디에 포함된 문자 피하기 문자도 결국 일정한 정수로 표현할 수 있다. 문자 ...

백준 온라인 저지, 27885번: 가희와 열리지 않는 건널목 도입 문제의 상황을 아래와 같이 정리할 수 있다. 건널목을 통과하는 열차가 없다면 차단기가 올라간다. 그렇지 않으면 차단기가 내려간다. 열차가 건널목을 접근(=통과하기 시작)하면 40초 뒤 완전히 빠져나간다. 상행 열차와 하행 열차가 동시에 통과할 수 있다. 같은 방향의...

백준 온라인 저지, 2557번: Hello World 도입 백준 온라인 저지에서는 어셈블리 언어 채점 환경을 NASM 32비트/64비트 구현체로 제공한다. 어셈블리 언어는 실행 환경에 따라 요구하는 코드 스펙이 조금씩 다르기 때문에, 채점 환경인 AWS EC2에 맞는 코드를 작성해야 한다. 구체적으로 NASM은 x86 아키텍처를 대상으로 하고,...

백준 온라인 저지, 1269번: 대칭 차집합 도입 문제에서 제시한 두 개의 집합의 대칭 차집합의 원소의 개수를 구한다. 풀어보기 각 집합의 원소의 개수가 $200,000$개까지 도달할 수 있으므로, 원소의 검색은 매우 오랜 시간이 걸릴 수 있다. 따라서 어떤 값 $N$에 대해 즉시 검색 가능하도록 맵 자료구조를 사용한다. for i in m...

백준 온라인 저지, 11332번: 시간초과 도입 주어진 시간 복잡도 $O(?)$ 식을 그대로 연산하여 제한 시간 내에 해당 시간 복잡도 알고리즘으로 통과할 수 있는지 여부를 출력한다. 풀어보기 Source: Big-O Cheat Sheet 다른 시간 복잡도 케이스와는 달리 $O(N!)$은 팩토리얼 값을 직접 계산해야 한다. 문제는 팩토리얼...

백준 온라인 저지, 24025번: 돌의 정령 줄세우기 도입 문제의 요구사항은 제시된 “시야 점수와 관련된 정수”의 조건에 충족되는 배치를 출력하는 것이다. 정령들이 가질 수 있는 시야 점수는 $j-i$로 정의된다. $A_i$가 음수라면 시야 점수는 $-A_i$로 정의되므로, 부호는 방향으로 생각할 수 있다. 돌정령이 오른쪽을 바라보므로, 양수는 ...