본문 바로가기

CS

 (138)
공유 락/배타 락과 데드락 공유 락(Shared Lock)과 배타 락(Exclusive Lock) 공유 락(읽기 락) 공유 락이 걸린 데이터는 다른 트랜잭션에서 읽기만 가능하고 쓰기는 불가능하다. 즉, 공유 락이 걸린 데이터에 대해서 다른 트랜잭션도 똑같이 공유 락을 획득할 수 있다. 단, 배타 락은 획득할 수 없다. 따라서 공유 락을 사용하여 조회한 데이터는 트랜잭션 내내 변경되지 않음이 보장된다. 배타 락(쓰기 락) 배타 락이 걸린 데이터는 다른 트랜잭션에서 읽기와 쓰기 모두 불가능하다. 즉, 배타 락이 걸린 데이터에 대해서 다른 트랜잭션은 공유 락, 배타 락 둘 다 획득할 수 없다. 즉, 배타 락을 획득한 트랜잭션은 해당 데이터에 대한 독점권을 갖는 것이다. 정리해보면 아래 표와 같이 배타 락이 개입하는 경우 양립이 불가능해..
[백준] 2212. 센서 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 그리디 문제로, 2가지 방법으로 풀 수 있다. 방법 1: N = 6, K = 2일 때 각 센서 간의 거리들 중 4(N - K)개가 수신 영역이다. 이때 최소한의 수신 영역을 구해야하므로 센서 간의 거리를 오름차순해서 앞에 4개를 더한 것이 답이 된다. import java.io.BufferedReader; import java.io.IOException; import ja..
MySQL의 MVCC(Multi Version Concurrency Control) MVCC의 가장 큰 목적은 잠금(락)을 사용하지 않는 일관된 읽기를 제공하는 데 있다. 그리고 InnoDB는 언두 로그(Undo log)를 통해 이 기능을 구현한다. 예제를 통해 MVCC가 어떻게 동작하는지 알아보자. 만약 트랜잭션 1이 데이터를 조회해와서 값을 변경("서울" -> "경기")했으며 아직 커밋하지 않은 상태라고 가정하자. 데이터를 변경하면, 커밋 여부와 상관없이 InnoDB 버퍼 풀에 변경된 데이터가 반영된다. 그리고 변경 전의 데이터는 언두 영역에 보관된다. 이때 트랜잭션 2가 해당 데이터를 조회하면 어떤 데이터가 조회될까? 이는 설정한 트랜잭션 격리 수준에 따라 다르다. READ_UNCOMMITTED: InnoDB 버퍼 풀이 현재 가지고 있는 변경된 데이터("경기")를 반환한다. REA..
[백준] 1525. 퍼즐 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 퍼즐에서 0의 위치를 찾아서 4방향(위, 아래, 왼쪽, 오른쪽)으로 bfs를 진행하면 된다. 그런데 해당 퍼즐을 이미 만들었다면 패스하는 로직을 작성해야 한다. 이때 이차원 배열로 비교하면 복잡하기 때문에 다음과 같이 문자열로 변경해서 생각하면 된다. 1 2 3 4 5 6 7 8 0 ➡️ 123456780 그리고 방문 여부뿐만 아니라 몇 번만에 해당 퍼즐을 만들었는지 저장해주어야 하는데 map을 사용하면 방문 여부와 횟수를 간편하게 저장할 수 있다. map의 key는 중복이..
[백준] 5014. 스타트링크 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 평소 많이 풀던 BFS 문제에서 4방향 탐색을 2방향 탐색으로 바꾸기만 하면 된다. 그런데 다음과 같은 치명적인 실수를 해서 틀렸다. BFS를 풀 때 다음과 같이 그래프 범위 밖을 벗어나거나 이미 방문했으면 continue해버렸다. while (!que.isEmpty()) { Integer num = que.poll(); // 도착한 경우 if (num == G) { System.out.println(map[..
[백준] 1987. 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 처음에는 set을 사용해서 매 경우마다 set을 clone하고 새로운 알파벳을 넣어주는 식으로 풀었다. 그런데 시간초과가 났다. 아무래도 매번 컬렉션을 복제하는 것이 시간이 많이 소요되는 거 같다. 따라서 set이 아니라, 알파벳을 담는 일차원 배열을 두면 된다. 즉, visited[] 배열을 두어서 A를 방문했으면 visited[0] = true로 값을 넣어주는 식으로 하면 된다. ..
[백준] 11403. 경로 찾기 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 DFS와 플로이드 두 가지 방법으로 풀 수 있다. DFS로 푸는 방법은 다음과 같다. 각 정점을 시작으로 이동할 수 있는 다른 정점을 구한다. 이때 dfs를 사용한다. dfs의 결과로 visited[] 배열에 값이 채워지는데, 이때 true이면 이동할 수 있는 것이고, false이면 이동할 수 없는 것이다. 시간 복잡도는 각 정점을 시작으로 dfs를 시작하므로, O(N * (V + E))이다. import java..
[백준] 11724. 연결 요소의 개수 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 처음에는 dfs 부분을 다음과 같이 작성했다. private static void dfs(int start) { for (int i = start + 1; i

티스토리툴바