문제https://www.acmicpc.net/problem/1707풀이 이분 그래프를 판별하는 문제이다. 이분 그래프는 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프를 말한다. 풀이는 간단한데, 방문 시 1과 -1의 값으로 번갈아가며 방문 배열을 채워나가고, 만약 이전 방문 배열 값과 다음 방문 배열 값이 같으면 NO를 출력하면 끝이다. 그런데 여기서 주의해야할 것은 이분 그래프의 정의인데, 연결되지 않은 정점도 독립적인 그룹으로 이분 그래프의 조건을 만족한다. 그래서 탐색을 시작할 시작점은 방문되지 않은 점이 대상이 된다. (즉 모든 정점이 연결되어 있다고는 가정되어있지 않다! 이것땜에 43프로에서 틀렸다.) 다음은 소스 코드이다.소스 코드import..
분류 전체보기
문제https://www.acmicpc.net/problem/11559 풀이bfs가 포함된 빡 구현 문제이다. 제거할 뿌요를 bfs로 찾고, 삭제하고, 중력을 통해 재 정렬을 해야한다. 여러 그룹의 삭제될 뿌요가 한 텀에 있어도 연쇄는 한 번이라는 것을 잊으면 안된다. 여기서 연속된 4개 이상이 연결된 뿌요를 찾아 제거해야하는데, 그냥 BFS를 사용해 탐색하면, ㅓ ㅏ ㅗ ㅜ 모양의 탐색은 visited에 걸려 탐색을 할 수가 없다. 이것은 단순하게 해결 가능한데, 최대 2번까지 방문을 허용하기만 하면 ㅓ ㅏ ㅗ ㅜ 탐색이 가능하게 된다. 중력에 의한 재정렬은 stack을 이용해 구현했다. 제거할 뿌요를 제외한 값을 stack에 push하고, 다시 map[][]의 아래부터 stack에서 pop을 하며 값..
문제https://www.acmicpc.net/problem/1461풀이정렬을 포함한 구현 문제이다. 처음에는 방문 배열을 적용해 탐색을 해야하나 싶었지만, 다시금 아이디어를 떠올려보니 단순 구현으로 해결될 것 같았다. "세준이가 한 번에 들 수 있는 책"을 보고, 가지고 있는 책의 매개변수를 관리해야하나 싶었는데, 여기서 책의 숫자는 배열상 인덱스 거리와 같기 때문에 단순 배열에서의 거리 이동으로 구현했다. 아이디어는 우선 center를 구한다. center는 세준이가 돌아오는 기점이면서 책을 충전하는 곳이다. 그러기 위해 배열을 입력받을 때 0 인덱스 위치를 포함시켰다. 배열을 정렬하고 값이 0인 인덱스 위치를 저장한다. 그리고 책을 놓으러 다닌다. 여기서 핵심 아이디어는 0에서 가장 멀리 떨어진..
프로세스 동기화 도구에는 크게 뮤텍스 락과 세마포어가 있다. 둘 차이를 간단하게만 말해보면, 뮤텍스 락은 공유 자원에 하나의 스레드가 접근가능하고 세마포어는 공유자원에 여러 스레드가 접근 가능하다는 것이다. 지금까지 너무 얕게만 이해하고 있었다는 생각을 했다. 세마포어는 여러 스레드도 접근 가능하고, 뮤텍스 락을 대체할 수도 있기 때문에, 세마포어가 좋은 거 아닌가 라는 생각을 막연하게 해왔었다. 하지만 내부 동작 방식을 살펴보면 이야기는 달라진다. 문맥 교환이라는 오버헤드를 배제한 설명이기 때문이다. 이게 무슨 말인지 한번 살펴보자. 1. 뮤텍스락 뮤텍스락은 공유 자원에 접근하기 위해 뮤텍스를 획득해야하고, 자원 사용이 끝나면 뮤텍스를 해제하는 방식이다. 그리고 하나의 스레드만 뮤텍스를 획..
[Git] Git의 내부 구조와 동작 원리를 알아보자git 명령어는 자주 사용했지만, 실제 동작 원리에 대한 이해는 부족했던 것 같다. 특히 깃 충돌을 겪을 때, 부족한 개념지식으로 해결이 꼬이는 경우가 간혹가다 있었는데 오늘도 작은 규모의 커dcloud.tistory.com 깃의 내부 구성요소에 대해서는 지난 포스팅에서 다루었다. 하지만 개념만 이해하고, 내부 요소가 구체적으로 어떻게 동작하는지는 이해하지 못했다는 것을 느꼈다. 그래서 이번 포스팅에서는 실제로 깃 파일을 만들고 각 동작마다 어떻게 내부 요소가 변경되는지를 살펴보겠다. 1. git init()GitTest라는 디렉토리를 만들고 명령을 수행했다.그리고 이전 포스팅에서 살펴보았듯이, git init 명령어를 실행하면, .git 파일이 해..
자바스크립트에서 비동기 처리와 비동기를 어떻게 처리하는지 정리해보자. 비동기 처리 동기와 비동기는 상반된 개념이다. 동기는 순차적으로 코드가 실행되는 것을 말한다. 동기 처리 방식은 순차적으로 코드가 실행되어서 이해하기가 직관적이지만 한 가지 문제가 있다. 이전 코드가 끝나기 전까지는 아무것도 하지못해서 다음 코드로 넘어갈 수 없다는 것인데, 아주 쉬운 예로는 자장면을 배달하시는 배달부가 짜장면을 배달하고, 손님이 짜장면을 전부 먹을 때까지 다른 일도하지못하고, 계속해서 대기해야하는 것과 비슷하다. 그래서 비동기 처리 방식이 등장한다. 비동기 처리는 꼭 순차적으로 동작하지 않는다. 위의 예시로 보자면, 배달부가 자장면을 배달하고 손님이 식사할 동안 다음 장소로 이동할 수 있는 것이다. 여기서 한 가..
