본문 바로가기

Algorithm/BOJ

 (95)
[BOJ] 2003. 수들의 합2 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 투 포인터를 활용 - 왼쪽 첫 번째 두 번째를 target으로 잡고 합을 계산 - 합이 M보다 작다면 두 번째 타겟의 위치를 +1, 반대면 첫 번째 타겟의 위치를 -1, 합이 M 이라면 count + 1 - 첫 번째 타겟이 N보다 같거나 커지면 종료 2. 시간 복잡도 - O(N) """ 2. 정답코드 import sy..
[BOJ] 3273. 두 수의 합 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i 위의 방식은 시간 초과 발생 새로운 아이디어 생각해야함 - 투포인터를 활용하면? - 배열을 오름..
[BOJ] 2559. 수열 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 투포인터를 사용 - for문을 이용해서 처음의 k개의 값을 저장 - 다음 인덱스를 더하고, 이전 인덱스를 뺴줌 - 이때마다 최대값 갱신 2. 시간복잡도 - O(2N) == O(N) 3. 자료구조 배열 : int[] """ 2. 정답코드 import sys input = sys.stdin.readline N, K = map(int, input()...
[BOJ] 14719. 빗물 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 세로 H와 가로 W를 입력받아 2차원 배열을 만든다. - 특정 위치를 기준으로 양 옆에 자신보다 작은 높이의 블록이 있다면 물이 고일 수 없다. - 특정 위치에서 왼쪽에서 가장 큰 블록과 오른쪽에서 가장 큰 블록중에서 비교한다. - 왼쪽, 오른쪽에서 가장 큰 블록을 비교해서 둘 중 작은 블록을 구한다. - 만약 구한 블록 값이 해당 위치의 ..
[BOJ] 17144. 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 공기 청정기의 위치를 확인하여 위쪽에 해당하는 위치를 front에 할당하고, 아래쪽에 위치는 위쪽 위치에 1을 더한 값을 back에 할당. - 입력받은 T초 만큼 확산 함수(spread())를 실행, 공기청정기 함수 실행 -> 위쪽 (air_up()), 아래쪽 (air_down()) - R * C 크기의 2치원 배열 graph를 생성 - 반복문을 돌아서 그..
[BOJ] 16234. 인구 이동 1. 해결방법 """ 1. 아이디어 - 2중 반복문을 통해서 graph[0][0]부터 시작해서 BFS를 돈다. - 위치를 추가시켜 해당 그래프의 인구 수가 만약 L명 이상 R명 이하면, 방문 기록을 체크하고 큐에 삽입한다. - 인구 수 이동을 하고 인구수의 평균 값을 구하기 위해 temp라는 배열을 추가해서 인구 이동이 가능한 나라의 위치 값을 append한다. - while문을 계속 돌때마다 check 방문 기록 체크 배열을 초기화 하고 0, 0위치부터 계속 검사한다. - 연합된 나라의 총 인구수 / 카운트 로 계산해서 인구수를 이동시킨다. (소수점 버림) - while문이 끝날 때 마다 answer 지나간 날 +1 을 한다. """ 2. 정답 코드 입력 예제(1) 2 20 50 50 30 20 40 ..
[BOJ] 14891. 톱니바퀴 1. 해결 방법 """ 1. 아이디어 - 회전시킬 톱니가 시계방향으로 회전 했을 때, 맨 뒤의 큐 데이터를 빼고 앞에 붙인다. (pop()) - 시계 반대 방향이면 앞의 데이터를 빼고 뒤로 붙인다. (popleft()) - 3번째 톱니를 회전시킬 때 1, 2번째 톱니의 오른쪽 위치와 극이 다른지 같은지 확인 - 3번째 톱니를 회전시킬 때 4번째 톱니의 왼쪽 위치와 극이 다른지 같은지 확인 - 3번째 톱니를 시계 방향으로 회전했을 때 4번째 톱니의 왼쪽 위치와 3번째 톱니의 오른쪽 위치가 극이 같으면 리턴, 다르면 반대 방향으로 회전 후 pop, popleft - 2번째 톱니의 오른쪽 위치와 3번째 톱니의 왼쪽 위치 극이 다를 때, 2번째 톱니는 시계 방향으로 회전 Pop, popleft - 1번째도 반복..
[BOJ] 1966. 프린터 큐 1. 해결방법 """ 1. 아이디어 - 입력 받은 문서의 개수 만큼 큐를 생성 - m을 -1만큼 돌면서 큐를 pop하며 우선순위가 높은 원소 값을 찾는다. - pop으로 제거된 숫자의 우선순위가 크면 answer + 1을 하며 출력한다. - 낮은 원소 값은 pop을 한 후 append를 통해서 맨 뒤로 이동. - 원하는 문서가 뒤로 갈 때, m의 값도 큐 길이의 -1 만큼 초기화 해준다. 2. 시간복잡도 - O(T * N) 3. 자료구조 - while - Queue """ 2. 정답코드 입력 예제(1) 3 1 0 5 4 2 1 2 3 4 6 0 1 1 9 1 1 1 출력 예제(1) 1 2 5 코드 from collections import deque import sys input = sys.stdin.r..

티스토리툴바