ultrawave   9달 전

퍼온 문제입니다! 알고리즘문제 연습중인데 잘 해결이 안되네요...

풀어주시면 감사하겠습니다.
======================== 문제1 ==========================
프로그램이 실행되면 문자열을 입력받는다.(O)
문자열에서 2번 이상 반복된 같은 문자 혹은 문자열를 찾는다.(O)
M = (반복문자열의 문자수) X (반복수) 이며 M이 최대가 되는 반복문자열을 찾는다.(O)
M이 같다면 반복횟수가 더 많은 반복문자열을 출력한다.
M이 같고 반복횟수가 동일하다면 앞에 나온 문자열을 출력한다.(O)
만약 반복되는 문자열이 없다면 NULL을 출력한다.
입력되는 문자는 a~z, A~Z, 0~9 까지로 제한한다.(O)
만약 유효하지 않은 문자나 빈문자가 입력된다면 프로그램을 종료한다.(O)
표준 입출력만 이용해야하며 차후 커맨드라인으로 파이프라인을 써서 입출력을 할 수도 있어야한다. (O) (예를 들어, test.exe < input.txt > output.txt 이렇게 사용가능해야함)
출력형식은 예제출력값의 형식과 동일해야한다.(O)
입력되는 문자열의 길이는 100만개 이하라고 가정한다.(O)
============================================================================
=== 출력 결과값 ===
입력 -> abcde 출력 -> NULL (O) 입력 -> 12aaaaaa 출력 -> 12a:6 (O) 입력 -> ab12ab12abab1212 출력 -> ab12:3
위 경우처럼 나와야한다. ‘반복문자열:반복횟수’ 식으로 나와야한다는 것이다.

============================================================================

============================================================================

========================문제2 ==========================

?1?2?3.....?n (K=입력값)
K라는 입력값을 받았을 때 최단의 n을 구하는 문제였던 것 같습니다.
?에는 + 또는 - 이 2가지의 기호만 들어갈 수 있는 것 입니다.
1문제 예를 들어드리겠습니다.
만약에 K가 2라면은 다른말로 한다면 입력창에 2를 입력했을경우!!!
(실제로는 txt파일에 쓰여진 3개의 숫자를 리드한 후)
?1?2?3?4?5.....?n 의 최단 기호를 결정한다 했을때
+1-2+3 = 2 (k=2)
K=2 일때 n=3
그렇기때문에 n은 3을 출력해주는 문제 인 것 같았습니다.
(문제자체도 제대로 이해못해서 엄청 해맸다는...)
위에도 써놓았지만
TXT파일에 숫자를 리드해서 그 숫자를 하나씩 대입해보고 결과값이 나오도록 만들라는것 같더군요~;
텍스트 파일에는 아래처럼 숫자가 적혀있고 한줄 띄어서 또 숫자가 적혀있었습니다.
(아래 숫자는 제가 임의로 넣었습니다. 실제 시험에서 숫자 뭐 나왔는지 기억이 안나서.. ㅡㅡa;)
12
845
-12000
============================================================================

============================================================================

======================== 문제3 ==========================
스택을 이용해서 입력한 문자열을 원하는 문자열로 얻기 위한 연산 과정을 출력하는 것입니다.
첫번째 입력한 것은 스택에 들어갈 문자열이고, 두번째 입력한 것은 스택에서 나온 문자로 구성하 고자 하는 문자열이 되겠습니다.
입력
madam
adamm
bahama
bahama
long
short
eric
rice
출력
[
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
[
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
]
[
i i o i o i o o
]
☆★☆★☆★☆★☆★☆★☆★☆★문제4☆★☆★☆★☆★☆★☆★☆★☆★
가로 세로가 N * N 의 개수로 이루어진 행렬(matrix)A가 있는데, 이 행렬A은 0 과 1이라는 값으로만 이루어져 있다. 이 행렬의 안에 값들 중 인접한 1 의 값들로 이루어진 서브행렬B가 있다고 가정했을때, 이 서브행렬B의 모양은 정사각형과 직사각형으로만 이루어져 있을때, 이 면적의 크기를 구하는데, 행렬A에 존재하는 모든 서브행렬 중 가장 큰 면적의 값을 구하여라. 단 입력은 다음 설명와 같이 한다.
가로 세로의 값인 N 의 유효범위는 1~25 까지이다. 제일 처음 테스트케이스(몇개의 행렬 셋트를 체크할 것 인지의 개수)의 값을 숫자로 입력받는다. 이 테스트케이스는 행렬A를 몇번을 입력할 것인가를 나타내고, 한줄을 띄고, 위에서 테스트케이스를 입력한 만큼의 행렬을 연속으로 입력한다. 단 테스트케이스의 행렬과 행렬의 사이는 한줄을 띈다. 결과 출력도 각 테스트케이스마다 한줄에 하나씩 출력하며, 테스트케이스마다 한줄씩 띈다.
입력 예1)
=입력화면=
1
1011010 1011111 1011100 1011101 1001101 1001100 1110111
=출력결과=
10
입력 예2)
=입력화면=
2
0110 1111 0110 0100
111 101 111
=출력결과= 6
3
☆★☆★☆★☆★☆★☆★☆★☆★문제5☆★☆★☆★☆★☆★☆★☆★☆★ Happy Number
== 문제 설명 == 양의 정수 S0 의 각 아라비아 숫자들의 제곱의 합으로 양의 정수 S1을 만든다고 하자. 동일한 방법이라면, S1으로 S2를 만들 수 있고, … 계속 만들 수 있다. 만약 어떤 i(i ≥ 1)에 대해서 Si = 1이라면, 최초의 S0를 Happy Number라고 부른다. Happy Number가 아닌 수를 Unhappy Number라고 부른다.
예를 들어, 7에서 시작하게 되면 다음과 같은 일련의 순서를 가지게 되며 7, 49(=7^2), 97(=4^2+9^2), 130(=9^2+7^2), 10(=1^2+3^2), 1(=1^2), 따라서 7은 즐거운 수이다.
그리고 4는 4, 16(4^2), 37(1^2+6^2), 58(3^2+7^2), 89(5^2+8^2), 145(8^2+9^2), 42(1^2+4^2+5^2), 20(4^2+2^2), 4(2^2) 의 순서로 반복되므로 Unhappy Number이다.
== 입력 == 첫 라인은 인풋 케이스의 수 n이 주어지며 이후 n라인의 케이스가 주어진다. 각 테스트 케이스는 한 개의 양의 정수 N으로 구성되며 N은 10^9 보다 작다.
== 출력 == 출력은 주어진 수 N이 Happy Number인지 Unhappy Number인지 여부에 따라 다음과 같이 출력한다.
N이 Happy Number라면 “Case #p: N is a Happy number.” N이 Unhappy Number라면 “Case #p: N is an Unhappy number.”
p는 1부터 시작하는 케이스의 번호이며 각각의 케이스는 한 줄에 결과를 표시한다.
== 샘플 인풋 == 3 7 4 13
== 샘플 출력 ==

 Case #1: 7 is a Happy number.

Case #2: 4 is an Unhappy number.

 Case #3: 13 is a Happy number.

baactree   9달 전

문제 5

1000이하의 숫자들에 대해서 dp맵 채워 가면서 사이클 찾으면 풀릴거 같네영

문제 4

N이 작아서 native하게 풀어도 될거같아여 BOJ에서 비슷한 문제로 11873번이 있겠네여

문제 3

이건 가능한 모든 경우를 다 구하는 건가요? 문자열 길이를 몰라서 어떻게 짜야될지 몰겠네요

하나만 구하는거면 O(n)에 가능 할것 같구요 다 구하는거면

inputstr : aaaaa

outputstr : aaaaa

이럴 때 되게 많을거같은데 몰겠네영

문제 2 

백트래킹 미니멈으로 가지치기 하는것 밖에 생각안나네영 gg

문제 1

접미사 배열구해서 반복문자열 찾을수는 있겠는데 n이 백만이라 gg치겠습니다.

ultrawave   9달 전

1번은 해시맵 이용해서 해결했고,

2번은 수학적으로 접근해서 해결했습니다!

------------


3번에서는 가능한 모든 출력을 다 구해야 합니다 ㅠ

경우의수 구하는거는 순열 이용해서 어떻게 해볼수있을거같은데 나열해야해서 다른 방법이 필요할거같아요!


4번에서는  native하게 풀라는 말씀이 어떤 말씀이신지 잘 모르겠어요 ...

연관 문제를 풀어보겠습니다만

혹시 어떤 알고리즘을 사용해야 하는지 알려주실 수 있나요??


5번에서는 dp가 혹시 다이나믹 프로그래밍 말씀하시는건가요 ?

제가 그쪽은 많이 공부를 안해서.. 맵을 채우는게 어떤건지 감이 잘 안오네요.ㅜㅜ


baactree   9달 전

4번 모든 (x1,y1)-(x2,y2)점에 대해서 사각형 면적을 구하고 그게 가능한지 확인해도 1초안에 들어올거같아여

5번은 1000이하에서 중복되서 계속 계산 되니까 한번 계산 한 값들을 저장해놓으면 시간내에 풀릴것 같네여

댓글을 작성하려면 로그인해야 합니다.