컴퓨터 프로그래밍을 공부하다보면 우리 말로 번역하면 1급 시민 정도로 번역이 되는 first class citizen이라는 용어를 접하게 된다.
first라는 단어에서 추측해볼 수 있게 second class citizen, third class citizen이라는 용어도 존재하지만 일반적으로 사용되지 않는다.
(개인적으로 우리 사회의 주류, 비주류 시민을 나타내는 용어로 느껴져서 썩 긍정적인 단어로 안 느껴진다.)
first class citizen은 robin popplestone에 의해 정의 되어 졌는데, 다음과 같은 조건을 만족시키는 객체, 함수, 데이터형 등이 해당 프로그래밍 언어의 first class citizen이 된다.
1. 함수의 매개변수로 전달할 수 있어야 한다. (All items can be the actual parameters of functions.)
2. 함수의 결과값으로 반환될 수 있어야 한다. (All items can be returned as results of functions.)
3. 할당문의 대상이 될 수 있어야 한다. (All items can be the subject of assignment statements.)
4. 동등성 비교가 가능해야 한다. (All items can be tested for equality.)
만약 프로그래밍 언어에서 위의 조건을 function이 만족하면 해당 언어는 function이 1급 시민이고, object이면 object가 1급 시민이다.
이것을 각각 first class function, first class object라고 한다. 물론 한 언어가 여러개의 경우를 만족하기도 한다.
자바스크립트는 object와 function 모두 1급 시민으로 가지기 때문에 예시를 찾기 쉬우므로 자바스크립트로 예시를 만들었다.
언어의 1급 시민을 만족시키는 조건의 예시는 다음과 같다.
1. 자바스크립트의 first class object
var obj = {property : "property"} //3. 할당문의 대상이 된다.
var obj2 = obj;
function returnObject(object) {
return object;
}
console.log(returnObject(obj)); //1. 함수의 매개변수로 전달된다. 2. 함수의 결과 값으로 반환된다.
console.log(obj === obj2); //4. 동등성 비교가 가능해야 한다.
2. 자바스크립트의 first class function
var f = function returnNumber(number) {
return number;
} //3. 할당문의 대상이 된다.
var f2 = f;
function add(num1, num2) {
return f(num1 + num2); //2. 함수의 결과 값으로 반환된다.
}
console.log(add(f(1), f(2))); //1. 함수의 매개변수로 전달된다.
console.log(f === f2); //4. 동등성 비교가 가능해야 한다.
애너그램은 단어 A가 주어졌을 때 문장을 이루는 알파벳을 바꿔서 다른 단어 B를 만들 수 있으면 A와 B를 애너그램이라고 한다.
예를 들어 A = abc라고 하면 B = abc, acb, bac, bca, cab, cba가 될 수 있다.
문제의 요점은 A와 B는 모두 같은 길이로 되어있는 구성이 같은 알파벳의 나열이라는 것이다. 그렇다면 순서와 상관없이 알파벳의 갯수만 체크하면 간단히 풀릴 것이다.
알파벳의 총 개수는 52개이며 아스키코드값에 의해 A = 65, B = 65, ... ,Z = 90, a = 97, b = 98, ..., z = 122가 된다.
해당 숫자들을 0~52까지 매핑 시킨 후, 갯수를 체크하면 된다.
다음은 전체 소스 코드이다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
while (n-- > 0) {
int[] ana = new int[52];
StringTokenizer st = new StringTokenizer(br.readLine());
String s1 = st.nextToken();
String s2 = st.nextToken();
boolean result = true;
if (s1.length() != s2.length()) {
bw.write(s1 + " & " + s2 + " are NOT anagrams.\n");
continue;
}
for (int i = 0; i < s1.length(); i++) {
int c = s1.charAt(i);
if (c >= 65 && c <= 90) {
ana[c - 65]++;
} else if (c >= 97 && c <= 122) {
ana[c - 71]++;
}
}
for (int i = 0; i < s2.length(); i++) {
int c = s2.charAt(i);
if (c >= 65 && c <= 90) {
ana[c - 65]--;
} else if (c >= 97 && c <= 122) {
ana[c - 71]--;
}
}
for (int i = 0; i < 52; i++) {
if (ana[i] != 0) {
result = false;
break;
}
}
if (result == true) {
bw.write(s1 + " & " + s2 + " are anagrams.\n");
} else {
bw.write(s1 + " & " + s2 + " are NOT anagrams.\n");
}
}
bw.flush();
bw.close();
}
}
계단 오르기는 마지막 계단까지 올라 갔을때 밟은 계단의 값을 합하였을 때 최대가 되는 값을 구하는 문제이다.
계단을 오를 때의 규칙은 다음과 같다.
규칙1. 계단은 한 번에 한 계단 씩 혹은 두 계단씩 오를 수 있다.
규칙2. 연속된 세 개의 계단을 밟아서는 안 된다. 단, 시작점은 포함되지 않는다.
규칙3. 마지막 도착 계단은 반드시 밟아야 한다.
이 규칙에 의해 각각의 계단들에 대한 가능한 경로들을 구해보았다.
4번째 계단(배열상 s[3])의 경우의 수를 보면 s[0] + s[2] + s[3] 혹은 s[0] + s[1] + s[3] 혹은 s[1] + s[3]의 경우가 가능하다.
전 단계의 계단을 보면 s[0] + s[1] + s[3] 혹은 s[1] + s[3]에 대한 경우의 수는 2번째 계단에서 구하였으며 해당 경우는 2칸을 건너 뛰어 왔을 경우에 해당 됩니다. 그렇다면 한칸 직전에서 올라온 것은 s[0] + s[2] + s[3]가 될텐데 이 경우는 규칙2에 의해서 s[0] (2칸 + 1칸의 경우에 해당)에 대한 경우를 구하면 된다.
해당 식을 정리해보면
s[i] + (2칸전의 최대값) or s[i] + s[i-1] + (3칸전의 최대값) 이 될 것이다.
다음은 위의 식을 정리하여 소스코드를 만들면 다음과 같다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] stairs = new int[n + 1];
for (int i = 0; i < n; i++) {
stairs[i] = Integer.parseInt(br.readLine());
}
int[] memo = new int[n + 1];
memo[0] = stairs[0];
memo[1] = Math.max(stairs[0] + stairs[1], stairs[1]);
memo[2] = Math.max(stairs[0] + stairs[2], stairs[1] + stairs[2]);
for (int i = 3 ; i < n; i++) {
memo[i] = Math.max(memo[i - 3] + stairs[i - 1], memo[i - 2]) + stairs[i];
}
bw.write(memo[n - 1] + "\n");
bw.flush();
bw.close();
}
}
Abbreviation은 주어진 A 문자열에서 B문자열을 만들어 낼 수 있는지 판단하는 문제이다.
규칙은 다음과 같다.
규칙 1. A 문자열 중 소문자는 지울 수 있다.
규칙 2. A 문자열 중 소문자는 대문자로 변환 시킬 수 있다.
소문자는 없는 문자로 취급해도 되니, 순서에 맞게 B문자열이 나올 수만 있으면 정답이 될 것이다.
위의 규칙을 소스코드로 만들어 보면 다음과 같을 것이다.
public static void abbreviation(String a, String b) {
if (b.length() == 0) { #3
if (hasUpperCase(a) == false) {
result = true;
}
return;
}
char aLetter = a.charAt(0);
if (Character.isLowerCase(aLetter) == true) { #1
abbreviation(a.substring(1), b);
}
if (Character.toUpperCase(aLetter) == b.charAt(0)) { #2
abbreviation(a.substring(1), b.substring(1));
}
return;
}
static boolean hasUpperCase(String a) {
for (int i = 0; i < a.length(); i++) {
if (Character.isUpperCase(a.charAt(i))) {
return true;
}
}
return false;
}
#1 if 문 : 소문자는 지울 수 있다.
#2 if문 : 소문자를 대문자로 바꿀 수 있다.
재귀를 통해 쉽게 구현을 할 수 있다. 항상 재귀는 탈출 조건을 가지고 있어야하는데 위의 문제 탈출 조건은 변환이 가능할 때와 그렇지 않을 때이다. #3에서 B 문자열이 존재하지 않을 때(#2에 의해서 지워진다.), A 문자열의 남은 문자열에 대문자가 있으면 답이 아닌 것으로 간주(#1의 조건 문에 의하여)한다.
예를 들어 A 문자열이 ABCdfgh이고 B 문자열이 ABC이면 ABC가 #2에 의해 맞아 떨어지고 A문자열이 dfgh가 남았을 경우 dfgh는 지울 수 있는 문자이므로 답이라고 본다.
하지만 위의 코드를 정답에 넣어보면 타임아웃이 나올 것이다.
한가지 예시가 있다. dd라는 문자열이 A 문자열로 들어 왔을 때이다. 왼쪽으로 가면 규칙 1에 의해 소문자를 지우고 오른쪽으로 가면 규칙 2에 의해 대문자로 만든다. 만약 dd뒤에 더 많은 문자열이 있다면 리프 노드의 D는 중복이다. 문자열이 길어질 수록 이런 중복된 계산은 더 비효율적인 계산이 될 것이다. (마치 피보나치에서 중복 계산을 하는 것 처럼)
이러한 중복된 계산을 지우기 위해 미리 계산해 놓을 필요가 있다.
public static void abbreviation(String a, String b) {
if (b.length() == 0) {
if (hasUpperCase(a) == false) {
result = true;
}
return;
}
char aLetter = a.charAt(0);
if (memo.containsKey(a) == true) {
String memoB = memo.get(a);
if (memoB.equals(b) == true) {
return;
}
}
memo.put(a, b);
if (Character.isLowerCase(aLetter) == true) {
abbreviation(a.substring(1), b);
}
if (Character.toUpperCase(aLetter) == b.charAt(0)) {
abbreviation(a.substring(1), b.substring(1));
}
return;
}
동적계획법을 활용하여 미리 계산된 값이 있는지 확인하는 코드 이다.
A 문자열이 ddA이고 B문자열이 DC라고 가정하면 경우의 수는 비교 가능한 경우의 수는
["ddA", "DC"], ["dA", "DC"], ["A", "C"], ["DdA", "DC"], ["dA", "C"], ["A", "C"] 이고 ["A", "C"]가 2번 나오는 계산을 한다. 만약 A뒤의 문자열이 더 길어지면 어떨까? 문자열 A와 문자열 B의 키, 밸류 값으로 중복 계산을 막는 코드를 넣으므로 시간 복잡도는 훨씬 나아질 것으로 기대된다.
public class Main {
public static void abbreviation(String a, String b) {
if (result == true) return;
if (a.length() < b.length()) return;
if (b.length() == 0) {
if (hasUpperCase(a) == false) {
result = true;
}
return;
}
char aLetter = a.charAt(0);
if (memo.containsKey(a) == true) {
String memoB = memo.get(a);
if (memoB.equals(b) == true) {
return;
}
}
memo.put(a, b);
if (Character.isLowerCase(aLetter) == true) {
abbreviation(a.substring(1), b);
}
if (Character.toUpperCase(aLetter) == b.charAt(0)) {
abbreviation(a.substring(1), b.substring(1));
}
return;
}
static boolean hasUpperCase(String a) {
for (int i = 0; i < a.length(); i++) {
if (Character.isUpperCase(a.charAt(i))) {
return true;
}
}
return false;
}
private static final Scanner scanner = new Scanner(System.in);
private static boolean result = false;
private static Map<String, String> memo = new HashMap<>();
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
int q = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int qItr = 0; qItr < q; qItr++) {
String a = scanner.nextLine();
String b = scanner.nextLine();
abbreviation(a, b);
bufferedWriter.write(result == true ? "YES" : "NO");
result = false;
memo = new HashMap<>();
bufferedWriter.newLine();
}
bufferedWriter.close();
scanner.close();
}
}
에라토스테네스의 체는 특정 제한된 범위 내의 소수(prime number)를 찾는 고대 수학 알고리즘이다.
이 알고리즘의 동작 방식은 다음과 같다.
20까지의 수 중 소수를 찾는다고 하면,
1. 2를 소수에 적는다. (2는 가장 작은 소수이다.)
2. 20까지의 소수 중 2의 배수를 지운다.
3. 지워지지 않은 가장 작은 수를 찾아 소수에 적는다.
4. 20까지의 해당 수의 배수를 지운다.
5. 3~4를 20까지 반복한다.
2의 배수를 지웠을 때 (1~2단계)3의 배수를 지웠을 때(3~4단계)
이런 식으로 5단계까지 완료하면 남는 수가 제한된 범위까지의 소수이다.
위의 과정이 체처럼 소수들을 거른다는 느낌이 들어서 이 알고리즘의 이름을 에라토스테네스의 체라고 정말 잘 지은 것 같다는 생각이 든다.
백준 2960번 에라토스테네스의 체는 이 알고리즘을 이용하여 푸는 문제이다. 단순히 에라토스테네스의 체 순서에 따라 지워지는 수를 구하면 되는 문제이다.
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
boolean[] seive = new boolean[n + 1];
for (int i = 2; i <= n; i++) {
seive[i] = true;
}
int step = 0;
int result = -1;
for (int i = 2; i <= n; i++) {
if (result != -1) break;
for (int j = 1; i * j <= n; j++) {
if (seive[i * j] == false) {
continue;
} else {
seive[i * j] = false;
step++;
if (step == k) {
result = i * j;
break;
}
}
}
}
bw.write(result + "\n");
bw.flush();
bw.close();
}
}
