본문 바로가기

ㄴ 알고리즘/백준BOJ풀이27

[백준 2428번] 표절 풀이 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net N개의 파일 F1, F2, F3, ... FN이 주어질 때, Fi = Fj*0.9 인 두 파일쌍의 개수를 세면 된다. 가장 간단한 풀이는 이중 for문으로 두 파일을 조합을 선택하여 Fi = Fj*0.9 를 만족하는 (Fi, Fj) 쌍을 카운트하면 된다. 하지만 이렇게 풀게 되면 시간 복잡도는 O(N^2)으로 입력 값의 개수가 큰 경우 시간 초과를 얻게 된다. 다른 풀이 방법으로, 정렬과 이분탐.. 2021. 9. 25.
[백준 2121번] 넷이 놀기 풀이 2121번: 넷이 놀기 첫 줄에 점들의 개수 N(5 2021. 9. 25.
[백준 2103번] 직교다각형 복원 풀이 2103번: 직교다각형 복원 첫째 줄에 점의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 각 점의 x, y(0≤x, y≤10,000)좌표가 주어진다. 이 점들은 직교다각형을 이루는 순서대로 주어지지 않을 수도 있으며, 같은 점이 www.acmicpc.net 직교 다각형이란 모든 변이 x축이나 y축에 평행한 다각형을 말한다. 문제에서 제시한 정사각형 이외에도, 아래와 같은 다양한 직교 다각형을 만들 수 있다. 문제에서 요구한 것은 직교 다각형의 꼭짓점들이 주어졌을 때, 둘레를 구하는 것이다. 도형의 둘레는 가로 변들의 합과 세로 변들의 합으로 나누고 이들을 더해 구할 수 있다. d(A, B)를 A, B 두 점 사이의 거리라 할때, 가로변들의 합 = d(A, B) + d(C, D) + d.. 2021. 9. 25.
[백준 1448번] 삼각형 만들기 풀이 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 빨대 N개의 길이를 벡터 v에 저장하였을 때, 세가지 빨대의 조합으로 삼각형을 만들 수 있는지 확인하는 가장 간단한 방법은, 삼중 for문을 돌면서 세가지 빨대의 조합을 찾고, 해당 조합이 삼각형의 조건을 만족하는지 찾으면 된다. 그러나, 해당 알고리즘의 시간 복잡도는 O(N^3)이므로 시간 초과가 날 가능성이 매우 높다. for (int i=0; i 2021. 9. 25.
[백준 16960번] 스위치와 램프 풀이 16960번: 스위치와 램프 첫째 줄에 스위치의 수 N, 램프의 수 M이 주어진다. 둘째 줄부터 N개의 줄에는 스위치에 대한 정보가 주어진다. 스위치 정보의 첫 번째 정수는 그 스위치와 연결된 램프의 수이고, 이후 연결된 램 www.acmicpc.net N개의 스위치와 M개의 램프가 있다. N개의 스위치를 모두 누르면 M개의 램프 모두가 켜진다고 명시되어있기 때문에 모든 램프는 적어도 한번씩 N개의 스위치에 연결되어있다. 문제를 풀 수 있는 두가지 방법이 있는데, 첫째는 모든 램프가 꺼져있다고 가정하고 스위치를 한개씩 켜보는 것이다. 램프가 모두 켜질 때까지 최소로 켜야 하는 스위치 개수를 구해 이를 N-1과 비교하는 방법이다. 그러나, 해당 방법으로 문제를 풀면 정말 복잡하다. 따라서 모든 램프가 켜져.. 2021. 9. 25.
[백준 11558번] The Game of Death 풀이 11558번: The Game of Death 첫 줄에는 테스트 케이스의 숫자 T가 주어지며, 이어서 T번에 걸쳐 테스트 케이스들이 주어진다. 매 테스트 케이스의 첫 줄에는 플레이어의 숫자 N(1 ≤ N ≤ 10,000)이 주어진다. 이어서 N줄에 걸쳐 www.acmicpc.net T개의 테스트 케이스를 받아 처리해야 하므로 T개만큼 for문으로 돌려준다. 각 테스트 케이스마다 플레이어 명수 N을 입력 받고, 벡터의 1~N 인덱스에 각 플레이어가 지목한 플레이어를 저장한다. (벡터의 크기를 N+1로 지정한 이유는 1인덱스에는 플레이어 1이 지목한 사람,.. N인덱스에는 플레이어 N이 지목한 사람을 맞추어 저장하기 위함이다. 0부터 하면 또 헷갈릴테니 벡터의 0 자리는 비워둔다.) 첫번째 플레이어 1이 가.. 2021. 9. 25.
[백준 161141번] 화살표 연산자 풀이 16114번: 화살표 연산자 첫 줄에 변수 x의 초기값을 뜻하는 정수 X와 화살표의 길이를 뜻하는 정수 N(-100 ≤ X ≤ 100, 0 ≤ N ≤ 10)이 주어진다. www.acmicpc.net X의 입력 값의 범위와 N의 입력 값의 범위를 고려하여 각 상황에 따른 출력 값을 나눠볼 수 있다. N == 1(단항 연산자) N != 1 && N%2 == 1 N == 0 N != 0 && N%2 == 0 X > 0 0 ERROR INFINITE X를 연산횟수(N/2)로 나눈 몫의 올림 - 1 X .. 2021. 9. 25.

티스토리툴바