메이쁘

https://www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 문제 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다. 여 www.acmicpc.net 직관적으로 보는 문제. 쉽다. 여러 방식은 있겠지만 내가 사용한 방식은 k = 3이라고 하면 (여학생 인턴 수, 남학생 인턴 수)..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지 www.acmicpc.net 시간을 너무 오래 잡아먹은 문제입니다. BFS와 DFS를 활용해야 합니다... 제가 푼 것보다 등수가 높으신 분의 코드를 보고 그 분의 알..

https://www.acmicpc.net/problem/11057https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net DP(동적 프로그래밍) 문제이다. 길이 N에 해당하는 오르막 수를 구하는 문제인데, 오르막 수란 무조건 오름차순 인데, 중복된 숫자만 있어도 가능(인접한 수가 같아도 가능) 한 수 매커니즘 ..

https://www.acmicpc.net/problem/3023 3023번: 마술사 이민혁 문제 유명한 마술사인 이민혁이 사용하는 카드의 뒷 면은 모두 자신이 디자인한 카드이다. 민혁이는 카드 뒷 면 전체를 디자인하지 않고, 왼쪽 위 1/4만 디자인한다. 그 다음 대칭시켜 오른쪽 위를 만들고, 다시 대칭시켜서 아래 부분을 모두 만든다. 이렇게 대칭시켜서 전체를 디자인 한 이후에는, 마술하는데 사용하기 위한 의도된 에러를 넣는다. 에러는 원래 '#'이어야 하는 칸을 '.'로 바꾸거나 '.'이어야 하는 칸을 '#'로 바꾸는 것이다. 왼쪽 위의 디자 www.acmicpc.net 간단하다. 이중 for문으로 카드 문자 하나씩 받기 전 입력하는 Y, X 크기의 2배 만큼 char 배열을 생성해놓고 카드 문자를 ..

https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 www.acmicpc.net 에라토스테네스의 체는 유명한 알고리즘으로 일정 숫자까지(N) 숫자들 중 소수를 찾아내는 알고리즘이다. 이 문제는 난이도가 상당..

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 후.. 백트래킹 문제인데 백트래킹의 개념을 잘 숙지하지 못해서 시간 한참 걸렸다.. 백트래킹은 한마디로 정의하자면 하나씩 짚어가다가 조건에 일치하면 거기서 종료. 다시 돌아와서 짚어가던거 마저 짚어가는 것 이다. 주어진 문제의 조건은 체스의 퀸의 성격을 이해해야 한다. 퀸은 상하좌우 + 좌우대각선을 이동할 수 있다. 그렇기 때문에 하나의 퀸을 놓게 되면 그 퀸의 상하좌우 + 좌우대각선에는 퀸을 놓을 수 없다는 뜻..