내일은 알고리즘

문제풀이 루틴에 관한 글은
https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

https://www.acmicpc.net/problem/18858

1. 이해 (5분) - 3분

문제 자체는 길지 않았지만, 이해하는데는 시간이 필요했습니다.

non-산 이라는 처음 보는 단어가 있어 머릿속으로 그려보는데 조금 어려움이 있었습니다.

몇 번을 다시 읽고 문제에서 주어진 '산'이라는 개념이 잡혀 풀이를 구상했습니다.

2. 계획 (5분) - 1분

풀이방법은 간단했습니다. non-산 이 되려면, 즉 산이 없으려면 문제에서 설명하듯 A1<A2>A3 형태의 부분수열이 없어야합니다. 이 말은 즉 A1 -> A2로 갈때 가능한 3가지 경우 (A2가 A1보다 크거나, 같거나 작거나)를 두번 거치며 생기는 9가지 경우의 수 중에서 하나의 경우가 막힌다는 뜻입니다.

가능한 방법의 갯수를 구해야하므로 DP형태로 이전 단계에서 가능한 방법의 수를 가지고 다음 단계를 구합니다.

이때 초기 데이터는 이전 턴에서 변화가 없었다를 1씩 넣어주고 이 후 상승이 가능한 경우, 하강이 가능한 경우를 계산해서 다음 데이터에 넣어주는 식으로 구현했습니다.

3. 검증 (5분) - 1분

제가 구상한 풀이방법에서는 가능한 이전 상태의 수 M개의 데이터를 기억하고 이를 토대로 N번 가능한 경우의 수를 계산합니다. 따라서 연산은 대력 MN번 일어날 것이고, 문제에서 입력의 범위가 100과 1000으로 주어졌기때문에 10만번이면 충분히 시간안에 정답이 나올것이라고 생각했습니다.

메모리적인 측면에서도 딱히 문제가 생길 부분이 보이지 않았습니다.

4. 풀이 (30분) - 19분

구상한 풀이방법을 토대로 코드를 작성했습니다.

5. 채점, 디버깅 (+30여분)

풀이자체는 시간이 많이 걸리지 않았지만... 

구현 과정에서 반대방향으로 돌아가는 반복문과 입력 데이터가 1,2인 경우 등의 예외처리 그리고 초기 구상에서 잘못생각한 부분등을 고치면서 디버깅에 시간이 꽤나 걸렸습니다.

다행히 예제로 주어진 데이터에서 오류를 발견할 수 있어서 수정해 제출했지만 예제 데이터로 알 수 없는 오류였다면 오답인지도 모른채로 제출할 뻔 했습니다...

추가로 디버깅을 통해 코드를 수정하다보니 + 초기에 풀이 형태를 대충 구상

이 두가지 허술함의 콤보로 코드가 상당히 난해하고 더러워졌습니다.

추후 수정하게되면 재업로드하겠습니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;
	static final long div = 998_244_353;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		long[][] before = new long[M + 1][3];
		long[][] now = new long[M + 1][3];

		for (int m = 1; m <= M; m++) {
			before[m][1] = 1;
		}

		long sum = 0;

		for (int n = 1; n < N; n++) {
			
			sum = 0;
			for (int m = M; m > 0; m--) {
				sum = (sum + before[m][0] + before[m][1]) % div;
				now[m-1][0] = sum;
			}
			
			sum = 0;
			now[1][1] = (before[1][0] + before[1][1] + before[1][2]) % div;
			sum = (sum + now[1][1]) % div;
			for (int m = 2; m <= M; m++) {
				now[m][2] = sum;
				now[m][1] = (before[m][0] + before[m][1] + before[m][2]) % div;
				sum = (sum + now[m][1]) % div;
			}
			
			before = now.clone();
			now = new long[M+1][3];
		}

		long answer = 0;

		for (int m = 1; m <= M; m++) {
			answer = (answer + before[m][0] + before[m][1] + before[m][2]) % div;
		}

		System.out.println(answer);
	}
}

루틴에 맞춰 풀어본 첫 문제입니다.

몸풀기를 할 생각으로 실버 문제를 골랐는데... 너무 빨리 끝나서 생각처럼 잘 되진 않았습니다 ㅋㅋ

문제풀이 루틴에 관한 글은

https://nodingco.tistory.com/23  <- 여기를 참고해주세요!

https://www.acmicpc.net/problem/12849

숭실대학교 교내 대회에서 사용된 문제입니다.

설명도 직관적이고 DP의 개념을 잡기 좋은 문제인 것 같습니다. 

제가 짜 놓은 루틴대로 문제를 풀어보도록 하겠습니다.

1. 이해 (5분) - 1분

설명이 워낙 간단명료한 터라 이해에는 긴 시간이 걸리지 않았습니다. 

캠퍼스를 산책하고 주어진 시간에 시작점인 정보과학관에 도착하는 경로가 몇 개인지 알아내면 됩니다.

2. 계획 (5분) - 1분

우선 문제의 캠퍼스는 생긴 것 부터 그래프와 유사합니다. 시간이 정해져 있고 경로의 개수를 찾는 것이니 BFS를 생각해 볼만도 하지만 10만 분이라는 시간 후에 무시무시하게 많은 경로를 고려하면 안 될 것 같습니다.

대신 우리는 경로의 갯수만을 구하면 되고, 경로를 알 필요는 없다는 점에 착안해서 DP를 사용해 간단하게 구현이 가능할 것 같습니다. 

비슷한 느낌의 DP 문제로는 https://www.acmicpc.net/problem/2579  [계단오르기 (실버 3)]가 있을 것 같네요.

DP가 진행되는 기준이 시간과 계단으로 다르고 이 문제 같은 경우는 순환이 가능하단 차이가 있지만... 느낌이 비슷하다고 봐주시면 될 것 같습니다. 

특정 시간에 8개의 건물에 위치하는 경로의 갯수를 각각 저장하도록 [입력받은 시간][8]의 2차원 배열을 선언해 앞 시간의 정보를 토대로 풀이해보겠습니다.

그림처럼 건물들에 번호를 매기고

처음 시간 D=0일때 가능한 경로는 0번 건물이 1

D=1일 때 가능한 경로는 1,2번 건물이 각각 1

... 이런식으로 진행해나가려고 합니다.

3. 검증 (5분) - 1분

시간의 최대치는 10만, 제 계획에선 시간 1 당 8번의 덧셈 연산만 진행되면 되니 주어진 시간 1 초안에 무난하게 통과할 것 같습니다. (시간제한 1초를 대략 1억 번의 연산으로 생각하면 됩니다.)

문제에선 정답을 10억7로 나눈 나머지를 출력하라고 했는데, 풀이 도중에 int의 크기를 넘어서는 오버플로우가 발생하기 때문입니다.

매 연산마다 나누기를 진행해주면 되지만, 제가 구상한 풀이에선 신양관, 한경직기념관이 각각 4개의 값이 더해집니다.

그럼 최대 40억의 값이 나오므로 오버플로우를 방지하기 위해 아예 long 타입으로 배열을 선언해줍시다.

주어지는 입력으로 가능한 최대 80만개의 long타입 배열이 있다면 long타입의 크기는 16Byte로 사용하는 메모리는 1280만 Byte입니다.

1MB가 약 100만 Byte이므로 12MB가량의 메모리가 필요하고, JVM을 감안해도 문제에서 주어진 512MB의 메모리 안에서 충분히 동작할 것 같습니다.

4. 풀이 (30분) - 8분

여기까지 구상한 내용으로 풀어봅니다!

코드를 작성 한 뒤 주어진 예제를 넣어 확인합니다.

입력의 최솟값인 1과 10만을 넣어 출력이 정상적으로 되는 것을 확인합니다.

(움직이지 않고 머무르는 것이 불가능하므로 입력이 1인 경우 0이 나오는 것이 당연합니다. 10만을 입력한 경우의 정답은 지금 상황에서 확신할 수 없으므로 에러가 발생하지 않는지만 확인했습니다. )

5. 채점, 디버깅 (+@)

다행히 한번에 정답으로 통과되었습니다. 

이 문제를 푸는데는 총 11분이 걸렸습니다. 

실버 1의 난이도면 코딩 테스트에서 1,2번의 앞 순위로 나오는 문제니 스타트로 나쁘지 않았습니다!

DP를 구상하고 정답이 자료형의 크기를 넘치는것만 주의하면 크게 어려울 것이 없는 문제였습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static final long div = 1_000_000_007;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int D = Integer.parseInt(br.readLine());
		long[][] map = new long[D + 1][8];
		map[0][0] = 1;

		for (int d = 0; d < D; d++) {
			map[d + 1][0] = (map[d][1] + map[d][2]) % div;
			map[d + 1][1] = (map[d][0] + map[d][2] + map[d][3]) % div;
			map[d + 1][2] = (map[d][0] + map[d][1] + map[d][3] + map[d][5]) % div;
			map[d + 1][3] = (map[d][1] + map[d][2] + map[d][4] + map[d][5]) % div;
			map[d + 1][4] = (map[d][3] + map[d][5] + map[d][6]) % div;
			map[d + 1][5] = (map[d][2] + map[d][3] + map[d][4] + map[d][7]) % div;
			map[d + 1][6] = (map[d][4] + map[d][7]) % div;
			map[d + 1][7] = (map[d][5] + map[d][6]) % div;
		}

		System.out.println(map[D][0]);
	}
}

감사합니다!

저는 코딩 테스트를 그럭저럭 잘 푸는 편입니다.

어... 자뻑이 아니라, 객관적으로 그럴 겁니다!! 아마!

올해 치른 코테에서 대부분 합격했으니까요.

1차를 기껏 통과해놓고 2차 코딩 테스트나 면접에서 잘렸습니다만...

아무튼, 여태까지는 그냥 코테 문제를 보고 생각 없이 열심히 풀면 풀렸습니다.

하지만 실력면에서나 프로그래머로서의 커리어에 있어서나 좋지 않은 습관이 생기고 있는 것 같아
문제풀이 루틴을 정리하고 습관화해보려고 합니다.

코딩 테스트는 작게는 취직을 위한 테스트일 뿐이지만 문제풀이 루틴은 앞으로의 어떤 문제에도 적용 가능하니까요.

45분에 하나의 문제를 푼다고 가정해 보겠습니다.

보통 코딩 테스트가 4~7문제를 2~4시간 동안 풀고

앞의 몇 개의 문제는 비교적 쉽기 때문에 시간을 절약할 수 있으니

이 시간에 페이스를 맞추어 풀면 1,2개의 킬러 문제를 제외하면 대부분 풀 수 있는 시간입니다.

그리고 제 경험에 의하면 킬러 문제의 풀이는 합격에 크게 영향을 끼치지 않습니다.

(코딩 테스트가 4문제로 이루어진 경우 합격 라인은 2.5~3문제, 7문제의 경우 4.5~6문제 정도였습니다.)

1. 이해 (5분)

문제에 대한 이해를 진행합니다. 

2. 계획 (5분)

문제의 내용을 토대로 어떤 알고리즘을 써서 풀이하거나 구현할지 생각합니다.

- 간단한구현/복잡한구현(시뮬레이션)/DFS/BFS/DP/브루트포스/그리디/기타 알고리즘 (다익스트라,MST 등등) 

3. 검증 (5분)

내가 떠올린 알고리즘이나 풀이가 문제를 풀 수 있는지를 생각해 봅니다.

- 내가 구상한 방법을 사용하면 실행시간 안에 답을 구할 수 있을지 생각합니다.

풀이에 적합한 자료구조를 떠올립니다.

- Array/ArrayList/LinkedList/Queue/PriorityQueue/Stack/Map/Set

시간이나 메모리를 줄일 방법이나 풀이를 좀 더 수월하게 할 수 있는 기법이 있는지 확인합니다.

- 정렬/비트마스킹/가지치기/메모이제이션/투포인터/슬라이딩윈도우/기타 등등

또 문제의 입력, 조건, 범위 등을 체크합니다.

- 테스트 케이스의 갯수 -> 테스트케이스의 형태 -> 입력의 범위 -> 출력의 범위 -> 자료구조의 크기

4. 풀이 (30분)

그리고 대망의 풀이!입니다.

가능하면 여유 부리지 않고 빠르게 풀이하는 게 좋습니다.

풀이가 틀릴 수도 있고, 디버깅 등을 통해 예외를 체크할 시간이 필요하기 때문입니다.

음... 여기는 딱히 드릴 팁이 없습니다.

풀이 시간이 부족하시다면 더 많은 노력과 연습!! 을 하셔야 합니다. 

코딩은 운동처럼 머슬 메모리로 하는 겁니다.

5. 채점, 디버깅 (+@)

코딩 테스트에서 주어진 예제를 모두 맞추더라도 내부 채점에선 틀리는 경우가 생깁니다.

제가 겪은 자주 발생하는 예외는 다음과 같았습니다.

- 입력이 0개, 혹은 1개인 경우

- 특정 상황에서 답이 없는 경우 (정답 변수의 초기화를 체크)

- 정답의 형식이 맞지 않는 경우 (대소문자, 개행 문자, 띄어쓰기 예외적인 경우 등 체크)

- 변수의 표현 범위를 넘어서는 경우, 시간 초과 (앞에서 체크했지만 혹시 모르니!)

다음 알고리즘 풀이부턴 이 5단계에 따라 걸린 시간을 체크하면서 작성해보도록 하겠습니다.

감사합니다!

https://www.acmicpc.net/problem/1202

보석도둑 문제입니다.

핵심 아이디어는, 가방에 담을 수 있는 가장 비싼 보석을 담자! (Greedy)입니다.

다만 고려해야할 상황이 몇 개 있습니다.

우선 큰 가방에 비싼 보석을 담는다면 작은 가방에 아무것도 담지 못하는 비효율적인 상황이 생길 수 있습니다.

그러니 작은 가방을 먼저 채우는것이 좋습니다.

둘째, 가방의 갯수가 30만개, 보석의 가격이 100만까지 가능하므로 최대 3000억의 값이 정답으로 나올 수 있습니다.

정답을 long (C계열의 경우 longlong) 타입으로 선언해 주어야 오버플로우가 발생하지 않을 것 같습니다.

셋째, 보석과 가방의 갯수를 자세히 보시면... 둘 사이에는 부등호가 없습니다.

즉 가방이 보석보다 많을 수도 있다는 뜻입니다.

저는 이 부분을 놓쳐서 NullPoint Exception을 한 번 보았네요.

풀이로 들어가겠습니다.

작은 가방부터 넣을 수 있는 최대의 보석을 담습니다. 

저는 그래서 보석과 가방의 정보를 모두 받고, 둘을 모두 오름차순으로 정렬해 주었습니다.

그리고 정렬된 가장 가벼운 가방부터 담을 수 있는 가장 비싼 보석을 찾는데,

보석의 정보가 이미 정렬되어 있으므로 한 번 순회하며 자기가 담을 수 있는 보석까지만 PriorityQueue에 넣었습니다.

PriorityQueue의 Comparator를 람다식으로 설정해서 가치가 높은 보석이 위로 올라오게 했으므로 이 PriorityQueue안에는 내가 담을 수 있고 가장 비싼 보석이 위에 존재하게 됩니다.

PriorityQueue에서 보석 하나를 꺼내어 담는 처리를 하고 (정답에 누적합하고) 다음 크기의 가방에 대해 같은 작업을 반복하면 됩니다. 

좀 더 최적화된 방법이 있을것 같은데 나중에 생각나면 포스팅을 업데이트 하도록 하겠습니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		PriorityQueue<int[]> pqueue = new PriorityQueue<int[]>((e1, e2) -> {
			return e2[1] - e1[1];
		});
		int[][] jewels = new int[N][2];
		int[] bags = new int[K];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			jewels[n][0] = Integer.parseInt(st.nextToken());
			jewels[n][1] = Integer.parseInt(st.nextToken());
		}

		for (int k = 0; k < K; k++) {
			bags[k] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(jewels, (e1, e2) -> {
			return e1[0] - e2[0];
		});
		Arrays.sort(bags);

		int index = 0;
		long answer = 0;

		for (int k = 0; k < K; k++) {
			int nowBag = bags[k];

			while (index < N) {
				if (jewels[index][0] <= nowBag) {
					pqueue.add(jewels[index].clone());
					index++;
				} else {
					break;
				}
			}
			if(!pqueue.isEmpty()) {
				answer += pqueue.poll()[1];
			}
		}

		System.out.println(answer);
	}
}

https://www.acmicpc.net/problem/20040

또 다른 웰 노운(Well Known인데 우리는 모르는) 알고리즘, 분리집합의 등장입니다. 

유니온이라고도 알려져 있습니다.

유니온은 일종의 단방향 트리라고 생각하셔도 될 것 같습니다.

데이터들을 집합들로 구분할때 어떻게 할 수 있을까요?

일일히 넘버링을 붙이거나 이름을 붙여도 되겠지만, 구현은 어떻게 하실건가요?

두개의 집합이 합쳐질때는요?

분리집합은 자신들을 대표하는 데이터를 부모로 가리킴으로서 자신이 속한 집합을 구분합니다.

이 데이터를 노드라고 생각한다면, 집합은 여러 노드들이 연결된 그래프가 되겠죠.

자신이 이미 속한 집합의 노드와 연결된다면 그 그래프는 사이클이 생긴 그래프가 됩니다.

간단하죠?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;
	static int[] parent;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int answer = 0;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		parent = new int[N];
		for (int n = 0; n < N; n++) {
			parent[n] = n;
		}

		for (int m = 1; m <= M; m++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int aParent = findParent(a);
			int bParent = findParent(b);

			if (aParent == bParent) {
				answer = m;
				break;
			} else {
				parent[aParent] = bParent;
			}
		}

		System.out.println(answer);
	}

	static int findParent(int a) {
		if (parent[a] == a) {
			return a;
		} else {
			parent[a] = findParent(parent[a]);
			return parent[a];
		}
	}
}

https://www.acmicpc.net/problem/1806

또 다른 투 포인터 문제입니다. 

정확히는 슬라이딩 윈도라고 할 수 있겠네요. 

기본적인 투 포인터가 데이터의 양 쪽 끝에서 좁혀 들어오면서 탐색한다면, 슬라이딩 윈도는 한쪽 끝에서 시작해서 연속된 특정 범위를 찾습니다.

조금 더 상세히 설명해 볼까요?

N길이의 수열에서 연속된 부분을 구한다는 것은, 연속된 부분합의 시작점과 끝점을 정한다는 뜻입니다.

즉 N*N개의 경우가 존재한다는 뜻입니다.

슬라이딩 윈도우는 이 시작점과 끝점을 모든 경우에 대해 계산해보지 않고, 현재 부분에서 조건보다 작으면 연속된 부분을 늘리고 크면 연속된 부분을 줄이면서 진행합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());

		int[] num = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int n = 0; n < N; n++) {
			num[n] = Integer.parseInt(st.nextToken());
		}

		int left = 0;
		int right = 1;
		int sum = num[0];
		int answer = 100_001;

		while (left < N) {
			if (sum >= S) {
				answer = Math.min(answer, right - left);
				sum -= num[left];
				left++;
			} else {
				if (right == N) {
					break;
				} else {
					sum += num[right];
					right++;
				}
			}
		}
		if(answer == 100_001) {
			System.out.println(0);
		}else {
			System.out.println(answer);
		}
	}
}

https://www.acmicpc.net/problem/2467

정석적인 투포인터 문제입니다.

투포인터 알고리즘에 대해선 나중에 포스팅을 작성해 보도록 하겠습니다.

투포인터 알고리즘을 통해 절댓값이 0에 가장 가까운 두개의 특성값을 기록하고 출력하면 간단히 풀립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[] num = new int[N];
		int value = Integer.MAX_VALUE;
		int[] answer = new int[2];

		st = new StringTokenizer(br.readLine());

		for (int n = 0; n < N; n++) {
			num[n] = Integer.parseInt(st.nextToken());
		}

		int left = 0;
		int right = N - 1;

		while (left < right) {
			int sum = num[left] + num[right];
			int abs = Math.abs(sum);

			if (abs < value) {
				value = abs;
				answer[0] = num[left];
				answer[1] = num[right];
			}

			if (sum <= 0) {
				left++;
			} else {
				right--;
			}

		}
		System.out.println(answer[0] + " " + answer[1]);
	}
}

https://www.acmicpc.net/problem/2166

신발끈 공식을 이용한 문제입니다.

고등학교때 배웠는지, 대학와서 선형대수학에서 배웠는지 모르겠지만...

워낙 간단하고 유용한 공식이라 아직 머릿속에 남아있어서 쉽게 해결했습니다.

공식에 대해 잘 모르시는 분은 아래의 킹무위키를 참고해 보셔도 될 것 같습니다! 흐흐...

https://namu.wiki/w/%EC%8B%A0%EB%B0%9C%EB%81%88%20%EA%B3%B5%EC%8B%9D

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringTokenizer st;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		long[][] points = new long[N + 1][2];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			points[n][0] = Long.parseLong(st.nextToken());
			points[n][1] = Long.parseLong(st.nextToken());
		}
		points[N] = points[0].clone();

		long sum1 = 0L;
		long sum2 = 0L;

		for (int n = 0; n < N; n++) {
			sum1 += points[n][0] * points[n + 1][1];
			sum2 += points[n][1] * points[n + 1][0];
		}

		System.out.println(String.format("%.1f", Math.abs(sum1 - sum2) / 2D));
	}
}

입력의 범위가 10만이고, 둘을 곱하면 int의 크기를 넘어가는 것만 주의하시면 쉽게 풀 수 있습니다!

저는 눈치 못채서 걸렸습니다!! 으아아악!!