메이쁘

https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 팩토리얼 리얼루 쉽다. 구현 분류지만 확장성을 위해 Dynamic Programming으로 해결했다. 구할 때 결과 배열을 문제 최대 조건까지의 크기로 먼저 만들고, 팩토리얼 결과 값 = 인덱스 * 이전 인덱스까지 계산한 결과 값 으로 해서 Bottom-Up 방식으로 계산해나갔다. n번째에 해당하는 결과를 알고 싶으면 배열 n번째 인덱스 결과 값만 꺼내면 끝! 감사합니다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import j..

https://www.acmicpc.net/problem/3967 3967번: 매직 스타 문제 매직 스타는 1부터 12까지 숫자가 헥사그램(hexagram)에 채워져 있는 모양으로 이루어져 있다. 매직 스타의 이름에 매직이 들어가는 이유는 숫자 네 개로 이루어진 줄의 숫자를 모두 합하면 26이 되기 때문이다. 위의 그림의 여섯 줄에 쓰여 있는 숫자는 다음과 같다. 1 + 4 + 10 + 11 11 + 5 + 3 + 7 7 + 6 + 12 + 1 2 + 10 + 5 + 9 9 + 3 + 6 + 8 8 + 12 + 4 + 2 매직 스타를 채우는 www.acmicpc.net 백트래킹 문제이다. 풀고 나서 제출 내역들을 보니 내가 속도가 다른 사람들에 비해 많이 느리게 나왔다. 하지만 다른 사람들의 풀이를 보는..

https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 이는 백트래킹 문제이다. 처음에 짠 알고리즘이 정답과 얼추 비슷했지만 틀렸고, 메모리 초과까지 발생하는 바람에 백트래킹 방식으로 시도해봤다. 정답과 정답을 도출하는 해설 방법만 기억하면 된다. 매커니즘 이 문제는 세 가지를 중요시하면 된다. 1) N인 수열이 존재할 때, 수열은 전부 1, 2, 3 세 개의 숫자 중 하나로 이루어져 있다. 2) 그 중, 반복된 문자열(여기선 숫자들) 이 붙어있지 않은 수열이 좋..

https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다. www.acmicpc.net 백트래킹 문제. 내 풀이법은 다른 사람들과는 조금 달랐다. 매커니즘 1. 문자열을 toCharArray() 해서 Char 배열에 저장. 2. 행복한 문자열을 만들기 위한 백트래킹 실행 ** 이 때, 첫 시작 문자를 정하기 위해 문..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 후.. 백트래킹 문제인데 백트래킹의 개념을 잘 숙지하지 못해서 시간 한참 걸렸다.. 백트래킹은 한마디로 정의하자면 하나씩 짚어가다가 조건에 일치하면 거기서 종료. 다시 돌아와서 짚어가던거 마저 짚어가는 것 이다. 주어진 문제의 조건은 체스의 퀸의 성격을 이해해야 한다. 퀸은 상하좌우 + 좌우대각선을 이동할 수 있다. 그렇기 때문에 하나의 퀸을 놓게 되면 그 퀸의 상하좌우 + 좌우대각선에는 퀸을 놓을 수 없다는 뜻..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 부분 조합을 이용하는 문제이다. 여기서 중요한 것은 1. 암호는 L 개의 알파벳으로 이루어져 있다. 2. 모음은 최소 1개, 자음은 최소 2개 가 암호에 포함되어 있어야 한다. 3. 암호 내 알파벳은 오름차순 정렬이 되어있다. 매커니즘 모음을 기준으로 만약 모음이 i개라면, 자음은 L - i 개가 되어야 한다. 예를 들어, 모음을 1개 뽑는 경우의 수 nC1 조합을 통해 원하는 모음 1개를 얻으면 자음..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30 www.acmicpc.net 그리디 알고리즘 문제이다. 처음에 HashSet 으로 모든 경우의 수를 구하는 코딩을 했더니 시간 초과가 발생했었다.. 뭔가 잘못되었다 싶어..

https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다. 세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 www.acmicpc.net 간단한 문자열 문제! String 을 사용하는 방법 StringBuilder를 사용하는 방법 이 있는데, 나는 StringBuilder를..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어 www.acmicpc.net DFS 관련 문제이다. 기존 DFS 문제와는 다른 점이 있다면 0부터 어느 특정 size까지 하나씩 count를 따진다는 것과 각 si..

https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 너무 애먹었던 문제. 보통이라면 소수를 찾는 문제들이 대거 있지만 이렇게 소수의 제곱과 나눠떨어지는 문제는 처음봤다. 그래서 그런가 정답률이 매우 낮을 뿐 아니라 생각보다 어렵고 까다로운 문제다! 몇 가지 체크해야 할 부분이 있다. 1) max - min (max와 min의 차이) 는 최소 0에서 최대 1000000(백만)까지이다. 이는 배열 최대 크기와 근접하므로 최대..