지구정복

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..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net -문제해설 문제는 듣도못한 사람과 보도못한 사람이 겹치는 사람의 수와 이름을 출력하는 것이다. 듣도못한 사람이 3 홍길동 김길동 박길동 보도못한 사람이 4 홍길동 박길동 이길동 정길동 이라고하면 이름은 사전순으로 출력해야 하므로 2 박길동 홍길동 이 된다. 이를 위해 처음에 해시맵 hs1에 ( 키: 이름, 값: 1 ) 로 듣도못한 사람들을 삽입한다. 그리고 arr ArrayList를 만들고 보도..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net -문제해설 처음에 팩토리얼 재귀함수로 하려니깐 값이 너무 커져서 틀렸다고 나왔다. 뭔가 굳이 n!을 다 구하지 않고 0의 개수만 알 수 있는 방법이 없나 생각하다가 그냥 노가다로 인터넷에 팩토리얼 계산기를 이용해서 규칙이 있는 지 확인했는데 신기하게도 규칙이 있었다. ㅎ 1~4 : 0 5~9 : 1 10~14 : 2 15~19 : 3 20~24 : 4 ㅡㅡㅡㅡㅡ25의 배수일 때는 + 2 25~29 : 6 . . . 45~49 : 10 ㅡㅡㅡㅡㅡ 50~54 : 12 . . . 70~7..