분류 전체보기

[백준 1525] 퍼즐 (C++)

1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net BFS, 비트마스킹 3x3 크기의 퍼즐은 각 칸마다 0~8까지의 숫자가 들어간다는 것을 이용해서 하나의 숫자당 4개의 비트를 사용. long long 타입에서 총 36개의 비트를 사용해 3x3 퍼즐의 정보를 저장하도록 했다. 위 퍼즐에서 0의 위치는 3행 3열에 있다. 따라서 32번째 비트~35번째 비트 공간이 해당 칸을 저장하게된다. 그리고 특정 칸에 위치한 숫자를 알아내기 위한 mask로서 Checker배열을 설정했다. BFS를 수행하면서 매번 0의 위치를 찾아준다. 0의 위치를 찾았다면 0이 갈 수 있는 4방향을 모두 탐색해본다. 범..

[백준 17472] 다리 만들기 2 (C++)

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net BFS, 최소 스패닝 트리 BFS를 통해서 각 칸마다 섬의 번호를 지정해서 섬을 구분한다. 모든 섬과 섬 사이의 거리를 구한다. 서로 이어지지 않은 섬은 거리를 INF로 한다. 여기까지 사전작업을 마쳤으면 모든 섬을 연결하는 최소 거리를 구하면 된다. 모든 노드를 연결하는 최단거리를 구하는 알고리즘은 최소 스패닝 트리임을 알 수 있다. 2번 과정에서 얻은 섬 간의 거리는 양방향이었으므로 중복되는 구간은 제외하고 새로운 벡터에 넣어준다. 거리를..

[Docker] Docker Swarm 서비스하기

[Docker] Docker Swarm에 대해서 [Docker] docker-compose로 편하게 개발환경 구성하기 [Docker] Django 개발 환경 세팅 #1 [Docker] MariaDB - docker로 관리하기 [Docker] Nginx 웹서버 구동해보기 컨테이너에 대하여 [Container 시리즈] 00. Co.. hyeo-noo.tistory.com 지난 포스팅에서 도커 스웜의 필요성을 정리했었다. 지금까지 한 내용을 요약해보면 개별적인 이미지들을 하나씩 컨테이너로 수동으로 만들어 주고 컨테이너끼리 연결해보았다. 컨테이너 설정을 모아둘 수 있는 docker-compose를 이용해서 한 번에 필요한 모든 컨테이너를 가동시켰다. 이제 docker swarm을 시작하고 지금까지 만들었던 컨테..

동적 계획법 메모이제이션 패턴 (C++)

동적 계획법.. 다이나믹 프로그래밍과 같은 말이다. 동적 계획법은 개념 자체는 쉬워서 알고리즘의 기본 난이도는 낮은 편이다. 하지만 메모이제이션을 몸에 익히고 문제를 보고 동적계획법을 떠올리며 어떤 정보를 메모이제이션할지 바로 찾아내는 내공을 가지려면 엄청난 노력이 필요하다고 생각한다. 다른 알고리즘과는 비교가 안될정도로 많이. 이 책에는 약 25개 정도의 큼직한 알고리즘 파트가 1000페이지 조금 넘게 기술되어있다. 그 중에서 동적계획법은 160페이지 가량 되는데 비중이 정말 크다고 볼 수 있다. 쉬우면 너무 쉽지만 어려우면 말이 안나올정도로 어려운 동적계획법의 가장 기본이 되는 탑다운 메모이제이션 패턴을 알아보자. 패턴 코드 // 전부 -1로 초기화 int cache[2500][2500]; int F..

[Docker] Docker Swarm에 대해서

[Docker] docker-compose로 편하게 개발환경 구성하기 [Docker] Django 개발 환경 세팅 #1 [Docker] MariaDB - docker로 관리하기 [Docker] Nginx 웹서버 구동해보기 컨테이너에 대하여 [Container 시리즈] 00. Container/ Docker란 뭔가요? Container / Docker 컨테이.. hyeo-noo.tistory.com docker-compose를 사용해보았으면 docker-compose.yml파일에 모든 볼륨 바인딩, 포트 포워딩, 네트워크, 이미지, 환경변수 설정 등 컨테이너를 구성하는데 필요한 정보들을 기록해 놓을 수 있다는 것이 정말 편하다는 것을 느낄 수 있다. 그리고 docker-compose up -d 명령어 하나..

[백준 1395] 스위치 (C++)

1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 세그먼트 트리 오랜만의 백준 풀이다. 어저께 하루 종일 고민하면서 구현했고 방금 구현을 마무리해서 AC를 받았다. 처음엔 3653 영화 수집 문제를 풀려고 했는데 아무리 생각해도 푸는 방법이 생각이 안 나서 런하고 만난 문제가 이번 문제다. 도망쳐서 만났기 때문에 한번 더 도망칠 수가 없었다.. 전에 풀었던 구간합구하기2 문제랑 느낌이 비슷해서 레이지 세그먼트 트리로 감을 잡았다. [백준 10999] 구간 합 구하기 2 (..

[백준 15559] 내 선물을 받아줘 (C++)

15559번: 내 선물을 받아줘 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000) 둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다. 지도에 쓰여 있는대로 이동했을 www.acmicpc.net 강한 연결 요소 임의의 칸에서 출발해서 다시 자신의 칸으로 되돌아 올 수 있으면 해당 루트의 아무 지점에 선물을 놓아도 선물을 가져갈 수 있다. 따라서 각 칸의 scc번호를 구한다. scc번호를 구하고 scc그래프를 만드는데 역방향으로 만드는게 중요하다. 하나의 SCC집합 내부에선 어떤 칸에 놓던지 선물을 가져갈 수 있는 성질을 활용하면 된다. SCC의 outdegree가 0이면 해당 SCC에서 다른 SCC로 갈 수 없다..

[백준 10217] KCM Travel (C++)

10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 다익스트라, 다이나믹 프로그래밍 [백준 17182] 우주 탐사선 (C++) 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 hyeo-noo.tistory.com 위 문제와 비슷한 다익스트라+DP문제였다. (주유소_13308 도 비슷하다) 하지만 이번 KCM문제는 최단 시간을 ..

[백준 20056] 마법사 상어와 파이어볼 (C++)

20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 시뮬레이션, 구현 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다. 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다. 파이어볼은 4개의 파이어볼로 나누어진다. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다. 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋..

[백준 4354] 문자열 제곱 (C++)

4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net KMP 예를 들어 문자열 abcab가 있다고 하자 kmp알고리즘을 사용해서 주어지는 문자열마다 접두사 실패 table을 만들어 준다. -> {0, 0, 0, 1, 2} table의 마지막 수는 마지막으로 접두사와 중복되는 문자열의 길이를 의미한다. -> 2 (ab 중복) 현재 문자열(text)의 크기에서 마지막으로 중복되는 접두사의 길이를 빼준다. -> 5 - 2 = 3 위 값은 중요하다. 무엇을 의미하는 걸까? 값 '3'은 ..