본문 바로가기

분류 전체보기

 (126)
[BOJ] 백준 17471. 게리맨더링 ▶문제설명[BOJ] 백준 17471. 게리맨더링 https://www.acmicpc.net/problem/17471 ▶Hint 조합과 DFS를 이용한 부르트포스 문제이다. 문제 해결에 핵심이 되는 두 부분에 대해 설명하고자 한다. 1. 구역 번호 1~N을 두 개의 선거구로 나눈다.[구역 번호를 두 개의 선거구로 나누는 모든 경우의 수]구역 번호 1~N에서 1개를 선택해서 선거구 A라고 하고 나머지 구역 번호 N-1개를 선거구 B라고 한다. (nC1가지 경우) 구역 번호 1~N에서 2개를 선택해서 선거구 A라고 하고 나머지 구역 번호 N-2개를 선거구 B라고 한다. (nC2가지 경우) 구역 번호 1~N에서 3개를 선택해서 선거구 A라고 하고 나머지 구역 번호 N-3개를 선거구 B라고 한다. (nC3가지 경..
[BOJ] 백준 16234. 인구 이동 ▶문제설명[BOJ] 백준 16234. 인구 이동 https://www.acmicpc.net/problem/16234 ▶Hint DFS, 시뮬레이션 문제이다. 인구 이동이 일어났다는 것은 한 시점에 인구 수 변동이 한 번 이상 있었다는 것을 의미한다. 한 번에 모든 연합이 동시에 인구이동을 실시하기 때문에 순차적으로 인구이동을 시키지 않도록 주의한다. [입력]3 5 10 10 15 20 20 30 25 40 22 10이런 입력이 들어왔다고 했을 때 인구 이동이 한 번 일어난 뒤의 상태는 아래와 같다. 20 20 20 20 20 20 40 20 10 ▶SolutionDFS 알고리즘을 이용해 각 연합의 전체 인구 수와 연합을 이룬 칸의 개수를 구해서 평균 값을 구한다. DFS를 수행하면서 좌표 값을 저장해두면..
[BOJ] 백준 1722. 순열의 순서 ▶문제설명[BOJ] 백준 1722. 순열의 순서 https://www.acmicpc.net/problem/1722 ▶Hint 조합론 & DP 문제이다. 입력으로 주어지는 N의 범위가 최대 20이다. 20! = 2,432,902,008,176,640,000 따라서 브루트포스로 접근할 경우 TLE가 발생하며, 결과 값이 int 자료형 범위를 넘어간다. 문제를 해결함에 있어서 중요하게 봐야 할 조건은 순열이 사전 순으로 정렬되어 있다는 것이다. 이 조건 덕분에 우리는 모든 경우를 확인해보지 않고도 K번째 순열을 찾아내거나 주어진 순열이 몇 번째 순열인지를 알아낼 수 있다. N이 4인 경우를 예로 들어보겠다. 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2..
지레짐작하지 말 것 ▶문제 ( [BOJ] 백준. 2891 카약과 광풍 )2890번을 보면 알겠지만, 상근이는 카약 대회를 개최했다. 그런데, 갑자기 엄청난 강풍이 경기장에 불었고, 일부 카약이 부서졌다. 경기는 5분 안에 시작해야 하는 상황이다. 다행히 일부 팀은 혹시 모를 사태에 대비해서 카약을 하나 더 경기장에 들고 왔다. 카약은 매우 무겁고 운반하기 어렵다. 따라서, 자신의 바로 다음이나 전에 경기하는 팀에게만 카약을 빌려주려고 한다. 즉, 팀 4는 여분의 카약을 3이나 5에게만 빌려줄 수 있다. 또, 카약을 하나 더 가져온 팀의 카약이 손상되었다면, 여분의 카약으로 경기에 출전하게되고, 이 카약은 다른 팀에게 빌려줄 수 없다. 카약이 부서진 팀과 하나 더 가져온 팀이 주어진다. 카약을 적절히 빌렸을 때 출발하지 못하..
GitHub와 Visual Studio 연동하기 ▶목표GitHub와 Visual Studio 2017을 연동해서 두 대 이상의 PC에서 소스 코드를 관리한다.Visual Studio IDE를 활용해 GitHub로 버전 관리를 하며 협업하는 개발자 혹은 공부하는 학생/취준생들에게 도움이 될만한 글이다. 해당 글을 읽으며 연동을 진행하기 전에 GitHub에 가입되어 있어야 하고, git에 대해 어느정도 이해하고 있다면 간단히 적용할 수 있는 내용이 될 것이다. ▶상황 노트북과 데스크탑을 왔다 갔다 하며 두 대의 PC에서 Visual Studio를 사용해 알고리즘 공부를 하는 편이다.기존에는 Visual Studio에서 코딩을 한 뒤 소스 파일(.cpp)을 일일이 복사해서 Git 프로그램을 통해 직접 명령어를 입력하여 나의 GitHub 원격 reposito..
[BOJ] 백준 2056. 작업 ▶문제설명[BOJ] 백준 2056. 작업 https://www.acmicpc.net/problem/2056 ▶Hint 위상 정렬 문제이다. 주어진 입력을 이용해 DAG를 만들고, 각 작업들의 Indegree 값을 구한다. 각 작업들에 소요 되는 시간도 저장한다. 처음에 Indegree가 0인 정점들을 queue에 push한 뒤 위상 정렬을 수행한다. 주의할 점이 있는데, queue에서 pop된 작업과 연결되어 수행될 작업을 끝내기 위해 소요되는 시간은 최대 값이 되도록 해야한다. 즉, '처음부터 현재 작업까지를 끝내기 위해 소요되는 시간 + 다음 작업 하나를 끝내기 위해 필요한 시간' 값이 최대가 되어야 한다. 예를 들어 작업 A를 수행하기 위해 B와 C를 선행해야 한다고 했을 때, MAX(처음부터 B까..
[BOJ] 백준 2252. 줄 세우기 ▶문제설명[BOJ] 백준 2252. 줄 세우기 https://www.acmicpc.net/problem/2252 ▶Hint 위상 정렬(Topological sort) 문제이다. 위상 정렬은 DAG(Directed Acyclic Graph : 방향성 비 사이클 그래프)에서 쓸 수 있는 알고리즘이다. 학생 N명을 줄 세우려 하는데, 일부 학생들의 키를 비교하여 누가 누구 앞에 있는지에 대한 정보를 입력으로 주고, 그에 맞추어 줄 세운 결과를 출력해야한다. 위상 정렬은 여러 개의 답이 나올 수 있고, 주어진 출력 결과와 다르더라도 위상 정렬이 제대로 되었다면 정답으로 인정된다. DFS를 이용한 방법과 각 정정의 Indegree 값을 이용한 방법이 있는데, Indegree 값을 이용해 풀어보았다. 정점이 3개이..
[BOJ] 백준 3190. 뱀 ▶문제설명[BOJ] 3190. 뱀 https://www.acmicpc.net/problem/3190 ▶Hint 뱀이 사과를 먹었을 경우 꼬리가 길어져서 꼬리 끝의 좌표를 그대로 두면 되지만, 사과를 먹지 못 했을 경우 꼬리 끝의 좌표가 머리를 따라서 한 칸 이동해야한다. 사과를 먹지 못했을 경우를 잘 처리해 주는 게 관건이다. 이차원 배열 map을 만들고, 시간의 흐름에 따라서 1부터 시작해 1씩 증가된 값을 저장하여 뱀을 나타내도록 구현했다. 그리고 꼬리 끝의 좌표와 머리의 좌표를 따로 저장하여 활용했다. 사과를 먹지 못했을 경우 꼬리 끝의 좌표에서 상/하/좌/우를 탐색해 가장 큰 값을 찾고 그 값의 위치로 꼬리의 끝이 이동하도록 구현하면 사과를 먹지 못했을 경우를 적절히 처리할 수 있다. (더 간단한..

티스토리툴바