본문 바로가기

분류 전체보기

 (115)
[BOJ][Python] 백준 2460번 - 지능형 기차 2 문제 링크: https://www.acmicpc.net/problem/2460 2460번: 지능형 기차 2 최근에 개발된 지능형 기차가 1번역(출발역)부터 10번역(종착역)까지 10개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. www.acmicpc.net 문제 풀이 간단한 구현 문제이다. 내린 사람 수를 빼고 탄 사람 수를 더하고 max()를 써서 최댓값을 갱신했다. 코드
[BOJ][Python] 백준 1547번 - 공 문제 링크: https://www.acmicpc.net/problem/1547 1547번: 공 첫째 줄에 컵의 위치를 바꾼 횟수 M이 주어지며, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 컵의 위치를 바꾼 방법 X와 Y가 주어지며, X번 컵과 Y번 컵의 위치를 서로 바꾸는 것 www.acmicpc.net 문제 풀이 간단한 구현 문제이고, 스왑을 이용했다. 공을 1로 생각하고 index()로 출력했다. 그리고 -1은 함정이다. 공이 없을리가 없다. 코드
[BOJ][Python] 백준 2101번 - 플러그 문제 링크: https://www.acmicpc.net/problem/2010 2010번: 플러그 첫째 줄에 멀티탭의 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 이어서 둘째 줄부터 N개의 줄에 걸쳐 각 멀티탭이 몇 개의 플러그를 꽂을 수 있도록 되어 있는지를 나타내는 자연수가 주어진다. 이 자연 www.acmicpc.net 문제 풀이 멀티탭에서 멀티탭을 연결하려면 한 멀티탭에 있는 플러그를 하나 써야한다. 그리고 마지막 멀티탭은 연결할 게 없으므로 멀티탭에 있는 모든 플러그를 사용 가능하다. 즉, 멀티탭의 플러그 수를 모두 더하고 멀티탭 하나 당 -1이니, (N-1)개의 플러그를 못쓴다. 그래서 합에서 (N-1)을 빼주면 된다. N이 최대 500,000이므로 빠른 입출력을 쓰거나 pypy로 돌..
[BOJ][Python] 백준 2254번 - 감옥 건설 문제 링크: https://www.acmicpc.net/problem/2254 2254번: 감옥 건설 첫째 줄에 N(1≤N≤1,000), Px, Py (-100,000≤Px, Py≤100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 문제 풀이 볼록 껍질 문제이다. 모노톤 체인 기법으로 풀었으며, 다각형 내부의 점 판정은 CCW로 간단하게 구할 수 있다. 볼록 껍질에 대한 자세한 내용은 나중에 직접 다룰 예정이다. 볼록 껍질을 만들 수 있을 때까지 반복문을 돌려주고, 먼저 가장 먼 외각의 볼록 껍질이 완성된다. Px, Py의 좌표(점을 $P_{xy}$라고 하자.)와 만들어진 볼록 껍질로..
[BOJ][Python] 백준 18870번 - 좌표 압축 문제 링크: https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 풀이 set()과 딕셔너리로 풀었다. 먼저 집합으로 만들어서 중복된 숫자들을 지워주고 다시 리스트로 변환했다. 이후 다시 오름차순으로 정렬했는데, 꼭 정렬해줘야 한다. set()은 정렬을 고려하지 않기 때문에 정렬된 상태로 입력을 줘도 정렬이 안 되어 있을 수 있다. 어짜피 그렇게 안줄때도 있어서 하긴 해야한다. 이후 딕셔너리를 ..
[BOJ][Python] 백준 14621번 - 나만 안되는 연애 문제 링크: https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 문제 풀이 최소 스패닝 트리를 이용하는 문제이다. 하지만 조건이 하나 추가 되었는데, 연결되어 있지 않은 간선을 유니온 시킬 때 둘다 남초 대학교 혹은 여초 대학교라면 유니온 시키지 않는다. 남자 - 여자 - 여자 - 남자 이렇게 연결 될 수도 있다 생각할 수 있는데 1번 조건에 따르면 불가능하다. 그 외에는 기본 최소 스패닝 트리이고 간선이 ..
[BOJ][Python] 백준 2903번 - 중앙 이동 알고리즘 문제 링크: https://www.acmicpc.net/problem/2903 2903번: 중앙 이동 알고리즘 상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다. www.acmicpc.net 문제 풀이 한 변에는 점이 총 $2^{N}+1$개 있다. 점을 제곱해주면 원하는 답이 나온다. 1번 과정에서 반으로 나누는 과정이 $2^{N}$이고, 2번 과정이 $+1$이라고 생각하면 된다. 코드
[BOJ][Python] 백준 10822번 - 더하기 문제 링크: https://www.acmicpc.net/problem/10822 10822번: 더하기 첫째 줄에 문자열 S가 주어진다. S의 길이는 최대 100이다. 포함되어있는 정수는 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 문제 풀이랄께 있나... split()을 이용해서 파싱으로 구했다. 코드

티스토리툴바