개발일지

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 이 문제는 적록색약인 사람과 아닌사람이 보는 구간의 개수를 각각 출력해야 하므로 방문 처리할 배열이 2개가 필요하다. 그러나 배열만 다르고 실제 수행하는 탐색은 같은 bfs를 사용하므로 객체로 만들어 문제에 접근하도록 하겠다. 상하좌우로 인접하며 같은 색깔인 경우에 탐색을 진행하면 되므로 dx, dy 배열 그리고 BFS 알고리즘을 사용할것이므로 큐에대한 자원을 선언해주겠다. int n,fr..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제는 수빈이와 동생사이의 최단거리를 찾는 문제이므로 BFS 로 접근하는것이 푸는것에 용이하다. 수빈이가 한번에 이동한 범위는 현재위치 + 1 , 현재 위치 - 1 , 현재위치 * 2 이므로 해당 3가지 경우를 인접한 정점으로 생각해서 너비우선탐색으로 풀면된다. 전체 범위는 0 ~ 100,000 이므로 탐색할 배열의 길이를 정적으로 할당하겠다. static final..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 그리 어렵진 않은 탐색문제이다. DFS를 사용해 풀이해보겠다. 먼저 문제 분석을 하자면, 좌표에서 1에 해당하는 좌표에 인접한 1인 좌표가 있을 경우엔 같은 단지로 취급하고 아닌경우는 다른 단지로 취급하고 0일땐 집으로 취급하지 않는다. 이때 단지의 수, 그리고 각 단지의 집의수를 오름차순으로 출력해주면 되는 문제이다. 우선 DFS로 구현을 하기위해 재귀 호출수를 저장할 변수, 그리고 NxN의 형태..

트랜잭션은 다음과 같이 4가지 특성을 갖는다. 1) 원자성 트랜잭션에서 정의된 연산들은 모두 성공적으로 실행되던지 아니면 전혀 실행되지 않아야 한다. 2) 일관성 트랜잭션이 실행되기전에 데이터베이스 내용이 잘못되어있지 않다면 트랜잭션이 실행된 후에도 데이터베이스의 내용에 잘못이 있으면 안된다. 3) 고립성 트랜잭션이 실행되는 도중에 다른 트랜잭션의 영향을 받아 잘못된 결과가 만들어져서는 안된다. 4) 지속성 트랜잭션이 성공적으로 수행되면 그 트랜잭션이 갱신한 데이터베이스의 내용은 영구적으로 저장된다. 이런 트랜잭션 처리에서 빠질수 없는 부분은 Lock 이다 Lock은 트랜잭션 처리에서 순차성을 보장하기 위한 방법으로 공유락과 베타락으로 나뉘어진다. 먼저 공유락은 데이터 검색만 가능한것을 의미한다. 즉 데..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 이름에서부터 알수 있듯 단순한 탐색문제이다. 여러 탐색 알고리즘 중 BFS를 적용해서 풀어보도록 하겠다. 우선 문제 분석을 해보자면 0과 1로만 이루어진 행렬로 미로의 구조가 주어진다. 1일때만 진행이 가능하고 0일때는 진행이 불가할때 왼쪽 최상단 지점에서 오른쪽 최하단까지의 최단거리를 구하는 문제이다. 한번에 한칸씩 이동이 가능하고 상하좌우로 이동이 가능하며, 총 이동 칸수 == 최단거리 를 구하면 되는것이다. 우선 한번..