. '프로그래밍 공부' 카테고리의 글 목록 (5 Page)
본문 바로가기

프로그래밍 공부65

아~ 와이파이 잘되는 집을 찾으시는구나? (백준 2110 : 공유기 설치) 2110번: 공유기 설치 (acmicpc.net) 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net N : 집 갯수, C : 공유기 갯수 우선, 집 좌표를 받아서 sort하자 N, C = map(int,sys.stdin.readline().split()) house = [int(sys.stdin.readline()) for _ in range(N)] house.sort() 딱봐도 맨 처음과 맨 끝 좌표에는 좌표기를 설치해야될 것 같지 않는가. (반례가 있나? .. 2020. 12. 18.
나무를 자르다니 나무해 (백준 2805:나무자르기) 2805번: 나무 자르기 (acmicpc.net) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 www.acmicpc.net 나무의 수 : N 원하는 나무의 길이 : M 상근이가 환경에 관심이 많기 때문에 최소한의 나무만 자르고 싶다고 한다. 정말 기특하지 아니할 수 없다. 상근이를 위해서 열심히 풀어보자. - 대전략 항상 수능을 공부할 때 들었던 말이 있다. "출제자의 의도를 파악하라." 다행히도 백준의 출제자의 의도는 알고리즘 분류에 나타나있다. 이 문제의 알고리즘 분류는 이분 탐색이다. 이분.. 2020. 12. 18.
야구는 9회말 2아웃부터 (백준2053:숫자야구) 2503번: 숫자 야구 (acmicpc.net) 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 어렸을 적에 많이 했던 숫자 야구이다. 그래도 나름 잘했던 게임이라 생각하는데 이런식으로 뒤통수맞을 줄이야. - 대전략 : 생각하고 있을 답의 총 개수라면, 결국 경우의 수를 전부 뽑아내어 간추릴 수 밖에 없다. 첫번째 대답에서 1스트라이크 1볼이라고 했으니, 1개는 자릿수와 숫자가 맞고, 1개는 자릿수가 맞고, 1개는 틀렸을 경우의 수를 전부 뽑아낸 뒤, 뒤의 조건에 대입하여 소거시킬 수 밖에 없다. 일단, 입력.. 2020. 12. 17.
아래로부터의 혁명 (백준 9095 : 1, 2, 3 더하기) 9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net - 대전략 : 예를 들어 입력값이 5(N)라고 하자. 일단 1부터 올라가야 할 것이다. 그러면 [1 1 1 1 1]이 될 것이고 이 조합의 수는 1개이다. 그다음은 1 2개를 합쳐서 [2 1 1 1]을 만들고 이 조합의 수는 4! (요소의 갯수) / 3! (중복된 숫자의 갯수) 가 된다. 리스트 안의 1, 2, 3의 갯수를 리스트화 하자. arr = [a b c]에서, a는 3의 갯수, b는 2의 갯수, c는 1의 갯수가 된다. 즉, [1 1 1 1 1] 은 arr=[0 0 5] 가 되고, [2 2 1.. 2020. 12. 17.
여인천하 (백준 9669번 : N-Queen) 9663번: N-Queen (acmicpc.net) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 재귀알고리즘의 대표 문제 중 하나인 퀸 문제다. 외판원 순환2랑 비슷하지만, 경우의 수가 더 많고 공간적으로 생각할 것이 더 많은 문제이다. - 대전략 : N * N 으로 체스판을 만들고, T/F로 구분한다. (퀸을 배치했거나 갈 수 없는 곳은 F) 우선 y=0인 곳에 퀸을 놓는다. 그 후, 다음 y열~N-1열에서 같은 x방향, 대각선을 모두 False한다. 그리고 다음 y열에서 x=0행부터 N-1행까지 True를 탐색하고, .. 2020. 12. 16.
이 세상의 모든 세일즈맨을 위하여 (백준 10971번 : 외판원 순회2) 10971번: 외판원 순회 2 (acmicpc.net) 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net - 대전략 이 행렬에서 중요한 것은 도시의 시작점인 y=0(x[0])이다. 결국 이 문제도 N-Queen과 같은 문제가 아닐까. x=i, y=0 을 시작점으로 하고, 0 이 아닌 곳에 가는 경우의 수를 구현해본다. 그러면 for로 y=0을 돌린다. 그리고 안에서 재귀함수로 실행시켜야 할 것 같다. 만약 (0,0)에서 시작한다면 각각 (0,1) (0,2) (0,3) .. 2020. 12. 15.
날씨의 아이 (백준 2468번 : 안전 영역) 2468번: 안전 영역 (acmicpc.net) 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net - 대전략 (0,0)부터 탐색을 시작한다. 만약 (0,0)이 T(그림 상 흰색)라면 카운트 (안전영역) 갯수를 올리고, dx dy로 상하좌우에 방문해본다. 만약 경계선이거나 F라면은 그냥 놔두고, T인 곳을 방문한다. (재귀함수 실행) 그런데 여기는 카운트를 올리면 안되지 않는가? (이어진 곳이기 때문에) 이를 어떻게 처리할 것인가. 시작은 이중 for문으로 돌리고 탐색만 bfs로 처리할 것인가? 일단 시작해보자. 시작은.. 2020. 12. 15.
OX퀴즈 보호되어 있는 글 입니다. 2020. 12. 11.
직사각형에서 탈출 보호되어 있는 글 입니다. 2020. 12. 11.

티스토리툴바