문제 https://www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net Algorithm 재귀호출을 이용해서 풀었다. 이동횟수는 항상 2**n-1 1 1번 기둥에 N개 원판 있고,이를 3번 기둥으로 옮길때 2 1번 기둥에 위치한 N개의 원판 중 N-1 개를 2번으로 옮김 3 나머지 1개를 3번으로 옮김 4 2번 기둥에 있는 N-1개 원판을 3번 기둥으로 옮김 f(n,a,b,c): n개 원판 1번기둥 a, 2번기둥 b, 3번기둥 c n=1이면 하나 옮기면 끝 n>1..
Koala - 10기/기초 알고리즘 스터디
문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net Algorithm n*n개의 타일에 퀸 n개를 서로 공격할 수 없게 되는 경우의 수를 출력하는 문제이다. 체스에서 퀸은 상하좌우, 대각선을 전부 이동할 수 있으므로 같은 열에는 둘 수 없다. n개의 열에 n개의 퀸을 두므로, 한 열에는 퀸이 1개만 존재해야한다. 순열을 재귀함수로 구현할때, 배열을 만들어서 선택이 가능한 경우에만 재귀함수를 돌리는 거에서 착안하여 재귀를 돌릴때마다 그 자리에 퀸을 두어도 되는..
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net Algorithm 양쪽으로 빼기 위해서 덱을 사용하였다.R의 개수가 홀수일 경우에만 뒤집기를 수행, flag 값을 통해 R의 개수를 카운트하고 짝/홀 여부를 판정한다."[]"라고 입력을 받아도 deque의 길이는 1이 되기 때문에 길이가 0인 부분에 대해서는 예외사항으로 빈 큐로 초기화를 해줘야 한다. 'R'이면,flag 변수가 1씩 증가 'D'이면, 덱 q의 길이가 0인지 확인한다. 만약 q가 비어있으면 'error'를 출력하고 반복문을 중단한다. 그..
문제 1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net Algorithm 1~n까지 숫자를 붙여서 썼는데, 일부분이 지워졌을때 최소의 n을 구하는 문제이다. 예시로 234092를 봐보자. 2는 2에서, 3은 3에서, 4는 4에서, 0은 10에서 나온다. 그다음 9는 최소의 n이 되려면 19에서 나와야하고, 2는 20에서 나와야한다. 그래서 n이 20이 된다. 숫자열의 인덱스를 나타내 줄 포인터를 설정하고, 현재숫자 i 를 정한다. while문으로 숫자를 증가시켜가면서 숫자의 자릿수가 배열에 있으면 포인터를 증..
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net CODE 처음 실패 import sys input = sys.stdin.readline n, k = map(int, input().split()) stack = [] number = list(input().rstrip()) for i in range(n): while k>0 and stack and stack[-1] < number[i]: stack.pop() k-=1 stack.append(number[i]) print(*stack,sep='') 두번째 성공 import ..
문제 https://www.acmicpc.net/problem/1124 1124번: 언더프라임 자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다. 어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, www.acmicpc.net Algorithm 자연수 X를 소인수분해를 하면 소수들의 곱이 되고, 소인수의 개수가 소수이면 자연수 X가 언더프라임이다. 범위를 입력받아 범위안에 있는 언더프라임의 개수를 찾는 문제이다. a와 b 사이가 최대 100000이고, 소인수분해하는데 루트100000정도 쓴다고 하면 31,622,776정도 나오므로 시간제한에 돌 수 있다고 생각해서 아래처럼 코드를 구성했다. 자연수의..
https://www.acmicpc.net/problem/17502 17502번: 클레어와 팰린드롬 입력으로 주어진 문자열을 팰린드롬이 되도록 '?' 문자들을 적절한 알파벳 소문자들로 바꾸어 출력합니다. 방법이 여러 가지인 경우 그 중 하나만 출력합니다. www.acmicpc.net 팰린드롬은 앞에서 읽으나 뒤에서 읽으나 일치해야 한다. 즉, 문자열의 양 끝에서 포인터의 위치를 변화시켜 두 포인터가 가르키는 문자가 전부 동일해야 한다. 1. 앞쪽의 문자가 '?', 뒤쪽은 '?'가 아님 -> 뒤의 문자를 앞쪽에 넣어준다. 2. 뒤쪽의 문자가 '?', 앞쪽은 '?'가 아님 -> 앞의 문자를 뒤에 넣어준다. 3. 둘 다 '?' -> 아무 문자나 넣어주면 된다. 내 경우엔 'a'
Problem Solution 1. 단어를 str 변수에 입력 받는다. 2. for문을 활용하여 strReverse라는 변수에 str의 글자 하나 하나를 거꾸로 저장한다. 3. str과 strReverse가 같으면 "true"를 출력하고 같지 않으면 "false"를 출력한다. Answer #include #include using namespace std; int main() { string str; cin >> str; string strReverse; for(int i = str.length()-1; i >= 0; i--) { strReverse += str[i]; } if(str==strReverse) { cout
문제 https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net Algorithm join 을 이용해 리스트 요소 연결 join은 리스트의 요소가 모두 문자열일 때만 사용 가능 위 리스트 모두 int형이므로 map을 이용해 형변환을 해준후 사용 map(변환할 자료형, 리스트명) 이 변환한걸 다시 리스트로 바꿔주려면 list(map(변환할 자료형, 리스트명) 정렬해주고 연결된 리스트 출력 Code N,M=map(int,i..
문제 https://www.acmicpc.net/problem/1895 1895번: 필터 숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10) 이미지 I는 www.acmicpc.net Algorithm 주어진 배열을 입력받아 3*3내에서의 T값보다 크거나 같은 것의 개수를 출력하면 된다. 주어진 배열이 40이하의 자연수 이므로 최대 38*38개수의 필터가 있고, 필터 내에서 중앙값을 구하는데, 이때 9개의 원소를 정렬하는 것이므로 9log9정도의 시간복잡도를 가진다. 38*38*9log9 = 약12996이므로 브루트포스로 풀 ..
Problem Solution 1. 이름 길이를 저장할 변수 len과 점수를 저장할 sum과 이름을 저장할 name을 선언한다. 2. 이름의 길이와 이름을 입력 받는다. 3. 이름의 길이만큼 for 반복문을 활용하여 반복 수행하도록 한다. 3-1. tmp라는 변수를 만들고 이름의 한 글자에서 'A'를 뺀 다음 1을 더한 값을 저장한다. 3-2. sum에 tmp값을 더한다. 4. sum값을 출력한다. Answer #include #include using namespace std; int main() { int len; int sum = 0; string name; cin >> len >> name; for(int i = 0; i < len; i++) { int tmp = name[i]-'A'+1; sum..
문제 https://www.acmicpc.net/problem/1371 1371번: 가장 많은 글자 첫째 줄부터 글의 문장이 주어진다. 글은 최대 50개의 줄로 이루어져 있고, 각 줄은 최대 50개의 글자로 이루어져 있다. 각 줄에는 공백과 알파벳 소문자만 있다. 문장에 알파벳은 적어도 하나 이 www.acmicpc.net Algorithm # 문제에서 입력을 eof 날때까지 받기 위해서 파이썬에서는 두 가지 방법이 있다. #try문이나 import sys. #import sys를 사용하여 문장을 입력받고, 한글자씩 인덱스에 카운팅하는 코드이다. #알파벳 개수만큼 배열칸 선언 #소문자거나 빈칸이거나이므로, 소문자이면 소문자의 아스키코드를 기준으로 배열에 카운팅 #소문자 26개만큼 반복하고, 가장 많이 나..
