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 이상이면 집 개수의 최대 값을 구한다.

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

시뮬레이션 문제. 쉬운 문제이다. 어떻게 더 깔끔하게 코드를 짤까?

풀이

1. 초기 입력시, 미생물 정보를 배열에 저장한다.
2. m 시간 동안, 저장한 미생물을 이동시키고 다음 경우를 고려한다.
   • 약품 칠해져 있는 곳으로 이동한 경우
   • 이동을 했는데 겹치는 경우

출처 : 이화여자대학교 반효경 (http://www.kocw.net/home/search/kemView.do?kemId=1046323)

File and File System

• File

  • 이름을 통해 접근 (cf. 메모리는 주소를 통해 접근)
  • A named collection of related information
  • 일반적으로 비화발성의 보조기억장치에 저장
  • 운영체제는 다양한 저장 장치를 file이라는 동일한 논리적 단위로 볼 수 있게 해줌
  • 연산
    • create / read / write / reposition (lseek) / delete / open / close

• File attritbute ( or 파일의 metadata)

  • 파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보들
    • 파일 이름, 유형, 저장된 위치, 파일 사이즈
    • 접근 권한 (읽기, 쓰기, 실행), 시간 (생성, 변경, 사용), 소유자 등

• File System

  • 운영체제에서 파일을 관리하는 부분
  • 파일 및 파일의 메타데이터, 디렉토리 정보 등을 관리
  • 파일의 저장 방법 결정
  • 파일 보호 등

Directory and Logical Disk

• Directory
  • 파일의 메타데이터 중 일부를 보관하고 있는 일종의 특별한 파일
  • 그 디렉토리에 속한 파일 이름 및 파일 attribute 들
  • 연산
    • search for a file, create a file, delete a file
    • list a direcotry, rename a file, traverse the file system
• Partition (==Logical Disk)
  • 하나의 물리적 디스크 안에 여러 파티션을 두는게 일바적
  • 물리적 디스크를 파티션으로 구성한 뒤 각각의 파티션에 file system을 깔거나 swapping 등 다른 용도로 사용 가능

open()

1. open시스템 콜을 하면 운영체제에게 CPU 제어권이 넘어가

2. 운영체제는 root를 먼저 open하여 root의 content를 찾아

3. a라는 파일의 메타데이터를 찾아서 이걸 메모리에 올려

4. a의 메타데이터로부터 a의 내용을 찾아

5. a안의 b의 metadata를 메모리에 올려

각 프로세스마다 그 프로세스가 오픈한 파일들에 대한 메타데이터 포인터를 가지고 있는 일종의 배열이 있어