https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14geLqABQCFAYD&categoryId=AV14geLqABQCFAYD&categoryType=CODE

오랜만에 푸는 관계로, 쉬운 문제를 선택하였습니다. 탐색 기본 문제입니다.

풀이

https://github.com/KoJunHee/algorithm/blob/master/src/swa_1219/Solution.java

1. 그래프 그리기

   주어진 그래프를 두 개의 배열로 표현합니다. 한 지점에서 최대 두 개의 길이 있기 때문입니다.

   예를 들어, 1번 지점에서 3번과 4번의 길로 갈 수 있다면 다음과 같이 배열에 저장합니다.

   arr01[1] =3 , arr02[1] =4

   마찬가지로 3번 지점에서 7번 길로만 갈 수 있다면 다음과 같이 배열에 저장합니다.

   arr01[3] = 7, arr02[3] = 0

2. 경로 유무 찾기

   DFS를 사용합니다. 최대한 깊게 들어가다가 99번 위치에 도착하면 탐색을 종료합니다.

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

오답 풀이

https://github.com/KoJunHee/algorithm/blob/master/src/bj_2668/Main.java

완전 탐색으로 풀었다. 가능한 모든 경우를 조사하였다. 깊이 들어갈 때 마다, 두 집합이 일치하는지, 깊이는 몇인지 체크한다. 시간 초과가 났다. 모든 경우를 완전 탐색으로 찾으며 푸는것이 아니란 것이다.

정답 풀이

https://github.com/KoJunHee/algorithm/blob/master/src/bj_2668_02/Main.java

사이클 여부를 조사한다. 다음 이동할 지점이 시작점이면 사이클을 이룬 것이다. 문제에서 주어진 예시를 그림으로 그려보자.

1을 시작으로 dfs를 시작하자. 1 방문 체크를 한다. 다음 위치는 3이다. 3 방문 체크를 한다. 다음 위치는 1이다. 이미 방문한 곳이다. 시작점으로 돌아왔으니 싸이클을 이루었다. 시작점인 1을 리스트에 저장한다. 이번 dfs는 끝났다.

2를 시작으로 dfs를 시작하자. 2 방문 체크를 한다. 다음 위치는 1이다. 1 방문 체크를 한다. 다음 위치는 3이다. 3 방문 체크를 한다. 다음 위치는 1이다. 이미 방문한 곳이다. 이미 방문 한곳이 시작점이 아니기 때문에 사이클을 이루지 않는다. 이번 dfs는 끝났다.

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWGsV8IaAXsDFAVW

오답 풀이

https://github.com/KoJunHee/algorithm/blob/master/src/swa_3503/Solution.java

정렬해서 나올 수 있는 모든 경우를 탐색하기 위해 DFS를 하였다. 원형이기 때문에, 시작점을 하나로 DFS 탐색을 시작해도 모든 경우가 커버 가능하다. 예를 들어, 2 4 5 7 9 의 경우에 2를 시작으로 DFS를 탐색한다. 탐색을 하며 높이 차를 계산한다. 시간 초과가 났다. 탐색으로 모든 케이스를 따져보는 것이 아닌 문제라는 것이다.

정답 풀이

https://github.com/KoJunHee/algorithm/blob/master/src/swa_3503_02/Solution.java

1. 오름 차순으로 정렬한다.
2. 가장 작은 값을 가운데에 둔다.
3. 맨 앞에, 다음으로 작은 값을 둔다.
4. 맨 뒤에, 다음으로 작은 값을 둔다.
5. 3,4를 반복한다.

이와 같이 하면, 가장 큰 높이 차가 최소가 되도록 정렬된다. 구현을 위해서, 두개의 큐를 사용하였다.

다음 그림을 보자.

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE

쉬웠다. 70분 소요되었다. 탐색문제이다.

풀이

selectionSort01

1. 각 row에 어떤 색으로 칠할지 DFS로 탐색하여 결정한다.

   i번째 row에 W를 칠했으면, i+1 번째에 W / B / R 색칠 가능

   i번째 row에 B를 칠했으면, i+1 번째에 B / R 색칠 가능

   i번째 row에 R를 칠했으면, i+1 번째에 R 색칠 가능

2. DFS로 깊이 들어갈때마다, 색칠할 칸을 카운트한다.

조건

1. R를 칠하려고 하면, 그 전에 B가 하나라도 나와야함

2. W만으로 칠해서는 안된다.

코드

https://github.com/KoJunHee/algorithm/blob/master/src/swa_4613/Solution.java

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

2018년 하반기 대졸 신입 삼성 코딩 테스트 오전 타임 2번 탐색 문제이다.

매우 쉬웠다. 55분 소요되었다.

풀이

1. 국경선 열기

   국가 각 지점에서 DFS을 실행하여 각 국가에 지역 번호를 매긴다.

   각 지점에서 동서남북으로 연결되어 있고, 인구 차가 l 이상 r 이하이면 같은 지역 번호가 매겨진다.

   DFS를 실행하고 리턴되었을 때, 지역 번호가 2개 이상 매겨졌으면 연합이 생성된 것이다.

   리스트에 지역번호와 함께 연합의 (인구합 / 연합을 이루는 국가수) 를 저장한다.

2. 인구 이동

   i,j 의 지역번호가 리스트에 저장되어 있는 지역 번호라면 해당 index의 리스트의 인구를 map에 저장한다.

코드

https://github.com/KoJunHee/algorithm/blob/master/src/bj_16234/Main.java

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

풀이

문장 단위로 읽어서 알파벳 개수 count.

여러 문장을 읽어오는 방법 : hasNextLine()으로 다음 문장이 있는지 체크

hasNextLine()

scanner의 input에 입력받을 line이 있다면 true를 반환한다.

https://docs.oracle.com/javase/7/docs/api/java/util/Scanner.html

코드

https://github.com/KoJunHee/algorithm/blob/master/src/bj_1371/Main.java

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

풀이

처음에 숫자 세트를 하나 갖고 있다고 시작한다. 숫자 부족할 때마다 숫자 세트를 늘려나간다.

코드

https://github.com/KoJunHee/algorithm/blob/master/src/bj_1475/Main.java

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

2018 하반기 대졸 신입 삼성 코딩 테스트 기출문제이다.

시험장에서 문제를 읽고 쉬울 것이라고 예상만 하고, 1번 문제를 푸느라 풀지는 못했다.

따로 풀어보니, 시간이 오래 걸렸지만 간단한 문제이다.

코드를 너무 복잡하게 짜서, 더 간단하고 깔끔한 풀이를 찾아봐야겠다.

풀이

BFS + Simulation

1. 먹을 수 있는 물고기 후보 찾기 : BFS
2. 후보가 한 마리면 그 물고기 위치로 이동해서 먹기
3. 후보가 두 마리 이상이면 다음 조건들을 차례대로. 두 가지 이상 나오면, 다음 조건 확인 : Simulation
   1. 가장 가까운
   2. 가장 i가 작은
   3. 가장 j가 작은

코드

https://github.com/KoJunHee/algorithm/blob/master/src/bj_16236/Main.java

응시일 : 2018.10.21 15:00-18:00

장소 : 영통 인재 개발원

시험 상황

계획은 1번 문제 90분, 2번 문제 90분 정도 잡았다. 1번 문제를 먼저 풀고 2번 문제로 넘어가려고 하였다.

1번 문제가 시뮬레이션, 2번 문제가 탐색 문제였다.

1먼 문제를 읽고, 90분 내에 충분히 풀 수 있다고 생각하였다.

하지만 90분이 다 되어가는데도 풀리지 않았다.

90분 즈음에 2번 문제를 읽었다. 충분히 풀 수 있을 것 같았지만, 조금만 더 하면 1번 문제를 풀 수 있을 것이라고 생각했다.

1번 문제를 포기 못하고, 1번 문제를 계속 풀었고 시간이 점점 흐르고 2번 문제를 아예 포기 했다.

문제점

<https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

쉬운 문제이다.

시뮬레이션 문제로 처음에 풀었다.

BFS로도 풀수 있다.

풀이 01

1. k 일 때, 전체 집 개수를 대상으로 이익이 0 이상인지 체크한다.

2. 이익이 0 이상이면, 마름모를 이동 시켜서 집 개수를 count 한다.

   마름모 이동이란, 예들 들어 k가 2일 때, 마름모의 중심에서 거리가 1이하인 지점을 체크하는 것이다.

3. 서비스 제공 받는 집 수의 최대 값 구하기.

풀이 02

1. i, j 지점에서 BFS를 시작한다. ( 모든 지점에서 BFS )
2. i, j 지점에서 지도의 영역을 넓힐 수 없을 때 까지 k를 증가시킨다.
3. 이익이 0 이상이면 집 개수의 최대 값을 구한다.