그건 장난감이 아니라 돌이야

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 하얀 방(1)과 검은 방(0)으로 구성된 1*1 크기의 방들이 n*n크기의 맵을 이루고 있다. 이때, (1, 1)에서 (n, n)까지 가고 싶은데 검은 방은 지나갈 수 없으므로 하얀 방으로 색을 바꾸고 지나가야 한다. 이때 검은 방의 색을 최소한의 횟수로 바꾸고 (n, n)에 도달하려면 몇 번 바꿀 수 있는지 알아보는 문제이다. 얼핏 보면 벽 부수고 지나가기 시리즈를 생각할 수 있는 문제이다. 하..

https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 공기구멍이 송송 뚫려있는 치즈가 있을 때, 바깥공기와 닿은 치즈 부분이 한 층씩 녹아내리는 상황을 시뮬레이션하는 문제이다. 일단 2차원 맵에서 탐색을 해야한다는 것을 봤을 때 직관적으로 BFS가 생각난다. 아니나 다를까 이 문제는 BFS를 사용해서 한 층씩 치즈의 겉을 녹여라! 라는 문제이다. 문제에서는 친절하게 맵의 가장자리는 무조건 공기로 채워져 있다는 제약조건을 준다. 만약 가장자리까지 치즈가 있을 ..

https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아 www.acmicpc.net W x H 크기의 맵이 있는데 맵의 (0, 0)에서 (W-1, H-1)까지 탈출할 수 있는지 없는지, 혹은 무한 루프가 존재할 수 있는지 알아내는 문제이다. 맵에는 잔디, 묘비, 귀신 구멍이 있다. 세 요소를 정리해서 문제를 단순화해서 이해해보자. - 잔디 : 빈 칸 (지나갈 수 있는 칸), 이 칸으로 올 때, 간선의 가중치는 1이다. - 묘비 : 벽 (지나갈 수 없는 칸) - 귀신 구멍 : 상하좌우론..

https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 1번부터 N번까지 번호가 붙은 노드가 있고, 양의 가중치를 가진 무방향 간선을 하나씩 그래프에 붙일 때, s노드와 t노드가 최초로 연결되는 순간이 있다. 간선들을 붙이는 순서를 마음대로 조정할 때, 이 s노드와 t노드가 최초로 연결되는 순간에 s노드와 t노드를 잇는 간선들의 가중치의 합이 최소가 되는 순간의 가중치의 합을 구하는 문제이다. 이 문제는 복잡하게 보일 수 있지만 생각해 보면 문제..

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net N개의 물건이 주어지고 그 물건들에 대한 대소관계가 M개 주어질 때 각 물건들끼리 대소 관계를 파악할 수 있는지 없는지를 파악하는 문제이다. 이 문제에서 주목해야 할 포인트는 두가지 정도이다. 1. 저울의 대소관계는 방향성 그래프의 간선으로 생각할 수 있다. 예를 들어 A B, B -> C로의 단방향 간선 두 개로 생각할 수 있다. 2. ..

삼성SDS에서는 매 방학 시즌에 대학생들을 대상으로 알고리즘 특강을 무료로 진행한다. 요즘에는 컴퓨터공학 전공뿐 아니라 전자, 기계분야도 코딩테스트가 거의 필수가 된 시대이다. 코딩테스트 하나만으로 그 사람의 사고에 대해 많은 것이 설명 가능하고, 또한 채용에 많은 돈을 들이는 기업의 입장에서 본다면 일종의 미달 기준선이 되기에 매우 좋은 시험이기 때문에 필수가 됐다고 생각한다. 이 알고리즘 특강은 알고리즘을 제대로 배워본 적이 없는 대학생이나 기존에 알고리즘을 공부했지만 플레티넘 수준의 문제는 접근하지 못해 봐서 더 깊게 알고리즘을 배우고 싶은 취준생 입장에서 매우 좋은 기회라고 생각한다. 나는 삼성SDS처럼 업계에서 좋은 입지를 가지고 있는 회사에서 이런 좋은 기회를 주는데 마다할 이유가 없다고 생각..

컴퓨터 공학에 입문한 뒤 대부분 처음으로 배우는 소수 판별 알고리즘은 에라토스테네스의 체 알고리즘이다. 에라토스테네스의 체는 소수를 판별하고 싶은 범위 안의 소수인 수의 모든 배수를 차례로 제거해서 원하는 수의 범위에서 어떤 수가 소수인지 판별 할 수 있는 알고리즘이다. 이는 꽤나 직관적인 알고리즘으로, 알고리즘이 작동하는 방식을 보면 소수라는 체로 소수가 아닌 수를 거르는 것처럼 보인다. 따라서 알고리즘의 고안자인 에라토스테네스의 이름과 체를 붙여서 에라토스테네스의 체 라는 이름을 가지고 있다. 에라토스테네스의 체는 O(N^2) 시간복잡도를 가진 알고리즘이다. 그런데 놀랍게도 에라토스테네스의 체를 가르쳐 준 후, 컴퓨터 공학 학부를 졸업할 때까지 일반적인 학부 과정상에서 소수 판별에 대한 더 효율적인 ..

어.. 왜 html 요소들이 내 마음대로 안 배치되고 뭔가 이상한 것 같지..? ㅠㅠ 라고 느낀 당신. 혹시 float 속성을 잘못 사용하지는 않았는가? html에서 block 요소들은 기본적으로 요소마다 한 줄씩 띄워진다. 개발자가 원하는대로 화면을 제어하고, 구성하기 위해서 css에서는 float와 flex 속성을 지원한다. 우리는 이 중 float 속성을 살펴보자. CSS에서는 float 속성을 요소에 적용해서 block 요소들을 상하가 아닌 좌우로 배치되게 만들 수 있다. 다음과 같이 float 를 사용할 수 있다. 다음은 section 부모 요소 안에 3개의 article 자식 요소를 넣는 html 코드이다. 이에 css를 다음과 같이 적용해보자. .floatEx section { border:..

사용법 #include int fcntl(int filedes, int cmd, struct flock *ldata); /* > filedes : lock을 설정 하려는 file의 descriptor > read-lock은 O_RDONLY/O_RDWR로 open된 file에 한해서 적용 가능 > write-lock은 O_WRONLY/O_RDWR로 open된 file에 한해서 적용 가능 > cmd : > F_GETLK : lock 정보 얻기 > 해당 정보는 세 번째 인수에 저장 > F_SETLK : non-blocking locking or unlocking > lock 설정에 관한 자세한 정보는 세 번째 인수에 지정 > F_SETLKW : blocking locking > lock 설정에 관한 자세한 정..

shared memory (공유 메모리) 둘 이상의 프로세스가 물리적 메모리의 일부를 공유 가장 효율적인 IPC기법이다. shmget 시스템 호출 #include #include #include int shmget(key_t key, size_t size, int permflag); /* > key : 공유 메모리 영역의 identifier > size : 공유 메모리 영역의 최소 크기 > permflag : access permission|IPC_CREAT|IPC_EXCL > return 값 : 공유 메모리 영역의 identifier */ 공유 메모리 생성 예 512byte의 문자를 저장 할 공유 메모리 생성 shmid1 = shmget(0111, 512, 0600|IPC_CREAT); 10개의 정수를..