목록지구정복과정 (466)
지구정복
https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net -문제해설 풀다가 어려워서 이 분의 코드를 참고했다. https://st-lab.tistory.com/227 먼저 문제와 나와있는 대로 정사각형에 모든 값이 1이 아니거나 0이 아니면 현재 정사각형을 2등분해서 각 사분면에 대해서 다시 전체 값이 1인지 0인지를 검사한다. 이때 전체값이 1이거나 0이면 재귀함수를 빠져나오고 아닐 경우 재귀함수를 계속 호출한다. 아직 분할..
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net -문제해설 먼저 입력 좌표값들을 배열에 저장하고 이 배열을 복사한다. 복사된 배열을 오름차순으로 정렬한다. 그리고 정렬된 배열을 순회하면서 해시맵에 넣어준다. 이때 키는 정렬된 배열의 값이 들어가고 값으로는 좌표압축값인 idx가 들어간다. 또한 무작정 집어넣는 것이 아니라 해시맵에 똑같은 키가 있을 경우엔 건너뛰게 된다. -자바 package so..
https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net -문제해설 DP의 기본적인 문제인 것 같다. 단순히 피보나치 값을 구하는 것이 아니라 특정 피보나치 수의 1의 개수와 0의 개수를 구하는 문제이다. 2차원배열을 선언해서 0번 인덱스에는 0의 개수, 1번 인덱스에는 1의 개수를 집어넣고 dp[i][0] = dp[i-1][0] + dp[i-2][0] dp[i][1] = dp[i-1][1] + dp[i-2][1] 점화식을 통해 n행의 배열값을 출력하면 정답이다. -자바 package dp; import java.io.BufferedReader; i..
https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net -문제해설 해시맵을 이용하면 간단하게 풀 수 있는 문제이다. 키에 사이트주소, 값에 비밀번호를 삽입하고 비밀번호를 알고 싶은 사이트 주소가 입력되면 StringBuffer에 키인 사이트 주소에 해당되는 비밀번호를 저장해주고 마지막에 StringBuffer를 출력하면 정답이다. 파이썬의 경우 딕셔너리 구조를 이용해서 키, 값을 삽입했다. -자바 package dataS..