Algorithm/Baekjoon117 2616. 소형기관차 (Python) 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 풀이 구간합 개념과 dp를 사용하여 해결할 수 있다. dp 배열은 2차원 배열로 이루어져 있는데 의미는 다음과 같다. # dp[1][n]: n번째 객차까지 1개의 소형 기관차를 사용했을 때 운송할 수 있는 최대 손님 수 # dp[2][n]: n번째 객차까지 2개의 소형 기관차를 사용했을 때 운송할 수 있는 최대 손님 수 # dp[3][n]: n번째 객차까지 3개의 소형 기관차를 사용했을 때 운송할 수 있는 최대 손님 수 dp = [[0 for _ in ra.. 2022. 3. 13. 1655. 가운데를 말해요 (Python) 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 가운데를 기준으로 낮은쪽을 저장하는 힙(smallerNumbers)과 높은쪽을 저장하는 힙(biggerNumbers)을 사용하여 해결하였다. smallerNumbers의 경우는 최대힙을 사용하였고 biggerNumbers의 경우는 최소힙을 사용하였다. 이는 작은 숫자들중에서는 가장 큰 숫자(smallerRep)가 가운데에 올 수 있고 큰 숫자들중에서는 가장 작은 숫자(biggerRep)가 가운데에 올 수 있기 때문이다. smallerRep와.. 2022. 3. 12. 3078. 좋은 친구 (Python) 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 풀이 슬라이딩 윈도우 개념을 사용하여 쉽게 해결할 수 있는 문제다. 이름의 글자수에 대한 리스트(lengths)를 하나 만들어 n글자의 이름이 현재 범위에서 총 몇 개가 있는지를 관리한다. 위와 같은 예제를 통해 이해해보자. 먼저 처음 CYNTHIA 이름의 길이(now)인 7을 기억한다. 그 후 K가 3이므로 LLOYD ~ KEVIN의 범위에서 이름들의 길이를 가져와 lengths에 저장한다. 그러면 lengths[5] = 2 (LLOYD, .. 2022. 3. 10. 9663. N-Queen (Python) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 백트래킹을 사용하는 대표적인 문제다. 각 행이나 열마다 퀸은 하나씩만 존재할 수 있고 대각선에 퀸이 있는지를 체크해야한다. 처음에는 함수에 열의 정보는 리스트를 활용해서 전달하고 대각선은 왼쪽 위와 오른쪽 위를 하나씩 체크하도록 for문을 사용하였다. 그렇게 했을 때 아래와 같이 시간이 많이 걸려 다른 방식을 찾아보았다. 먼저 보드에 퀸이 놓여져 있는 위치는 1차원 리스트를 통해서 표현할 수 있다. 위의 그림과 같이 board[n] = m 은 n행 m열에 퀸이 놓여져 있음.. 2022. 3. 8. 9466. 텀 프로젝트 (Python) 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 각 학생마다 dfs를 돌려서 해결할 수 있는 문제이다. 학생의 상태를 기록해 놓는 teamFlags 리스트를 하나 만들어둔다. teamFlags 리스트의 값은 0일 경우는 아직 탐색하지 않은 상태, 1일 경우는 팀을 이룬 학생, -n일 경우는 팀을 이루지 못한 학생임을 의미한다. n은 dfs 함수가 실행될 때마다 1씩 증가한다. 아직 탐색하지 않은 학생일 경우 dfs 탐색을 진행해가며 teamFlags[학생번호]에 -n을 설정한다. 탐색 과정에서 -n을 만나게 .. 2022. 3. 8. 1700. 멀티탭 스케줄링 (Python) 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 페이지 교체 알고리즘 중 하나인 OPT(Optimal Replacement, 최적 교체)를 생각하면 된다. 일단 멀티탭 구멍에 맞게 각 전기용품을 꽂은 다음 현재 멀티탭에 없는 전기용품을 사용해야 할 경우 멀티탭을 사용 중인 용품 중 가장 먼 미래에 사용될 용품의 플러그를 빼고 새로운 용품의 플러그를 꽂도록 구현해주면 된다. 코드 import sys # 제거해야 할 전기용품을 찾기 위한 함수 def removePlug(idx): maxIdx = -1 ite.. 2022. 3. 7. 이전 1 ··· 12 13 14 15 16 17 18 ··· 20 다음
