Algorithm175 15997. 승부 예측 (Python) 15997번: 승부 예측 첫 번째 줄에 조별리그를 진행할 국가명 네 개가 공백으로 구분되어 주어진다. 주어지는 모든 국가명은 알파벳 대문자로만 구성된 길이가 1 이상 10 이하인 문자열이다. 두 번째 줄부터 일곱 번 www.acmicpc.net 풀이 모든 경우의 수를 고려하여 dfs를 통해서 확률을 구하면 된다. 게임의 승패에 따른 각 나라의 승점을 기록하고 모든 경기가 끝났을 때 순위를 참고하여 확률을 더해주면 된다. 문제는 승점이 같은 나라가 있을 경우의 처리인데 문제에서 추첨으로 순위를 정한다고 하였다. 예를 들어 1위 승점이 9점이고 2위, 3위, 4위의 승점이 5점인 경우를 생각해 보자. 이 때, 1위는 문제 없이 진출할 수 있으므로 확률을 그대로 더해주면 되고 2위, 3위, 4위의 경우는 추첨.. 2022. 3. 15. 1405. 미친 로봇 (Python) 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 풀이 백트래킹을 활용해서 해결할 수 있는 문제다. 먼저 30 * 30 사이즈의 방문 체크 리스트를 만들고 로봇이 해당 리스트의 가운데에 위치해 있다고 가정한다. 그 후 동서남북으로 한 번씩 체크하여 방문하지 않은 위치에 해당하면 로봇을 해당 위치로 이동시키고 다시 함수를 호출한다. 동서남북으로 진행해 나갈때마다 해당 방향으로 이동할 확률을 곱해 나가 N번 이동을 마쳤을 때 구한 확률을 모두 더해준다. 만약 이동중에 이미 방문한 위치에 해당할 경우에는 함수를 .. 2022. 3. 15. 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. 이전 1 ··· 13 14 15 16 17 18 19 ··· 30 다음
