0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 어느 섬이던 가장 가까운 다리를 찾는 문제이다. 필자는 아래와 같은 방법으로 해결하였다. 1. dfs로 섬을 라벨링하고, 모서리 부분을 큐에 넣는다. 2. 큐에서 꺼내며 bfs로 최단 거리를 갱신한다. DFS(섬을 라벨링하고, 모서리 부분을 큐에 넣기) main문에서 처음 찾은 부분을 기점으로 dfs를 실행하고, 라벨(임의 숫자)을 붙인다. check 배열을 통해 같은 육지인지 판단..

문제 출처 : https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 풀이 껍질부터 하나씩 찾아가야 하는 문제이다. 이 문제의 핵심은 아래 부분이다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 즉, 가장자리는 치즈가 없으므로, 치즈의 바깥부분 (0, 0)부터 bfs로 탐색을 하면 된다. BFS 바깥 부분에서 공기(0)을 만나면, 큐에 추가한 후, 방문 표시를 해준다. 치즈(1)을 만나면, 녹아 없어지므로 공기(0)으로 바꿔주고, 방문 표시를 ..

문제 출처 : https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이 다익스트라로 해결하는 문제이다. 최대 아이템 개수를 구해야 하므로, 모든 지역별로 다익스트라를 돌린 후, 최대 아이템을 갱신하면 된다. 다익스트라 우선순위 큐를 이용해서 구현하였다. void dijkstra(int start) { for(int i = 1; i cost + ncost) { dist[next] = cost + ncost; pq.push({dist[next], next}..

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 최대한 많은 라운드를 진행시켜야 한다. 필자가 생각한 방법은 아래와 같다. 1. 우선 막지 못할때까지 병사를 소모한다. 2. 막지 못할 경우, 가장 많은 병사를 사용했던 곳에 무적권을 사용한다. (priority_queue) 3. 무적권을 다 쓰면 종료한다. 따라서, for문을 순회하며 priority_queue에 병사의 수를 push 하고, 무적권이 있는 경우 우선순위 큐에..

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전형적인 bfs 문제인데, 중간에 레버를 거친 후 출구로 가야한다. 따라서 시작 지점 -> 레버, 레버 -> 출구 이렇게 2번의 bfs를 돌리면 된다. bfs 함수 하나를 선언하고 재사용하는 방식으로 구현하였다. 시작 -> 레버 or 레버 -> 출구 bfs 중 가지 못하는 경우 -1 을 리턴하여 에러를 판별한다. 코드 #include #include #include #incl..

문제 출처 : https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 풀이 전형적인 배낭문제이다. 입력 받은 pair 벡터를 순회하며 값마다 dp 배열을 업데이트 하면 된다. 여기서 for문을 뒤부터 돌린 이유는, 문제 조건에 한 단원에 한 문제를 출제한다. 라고 명시되어 있기 때문이다. for문을 앞부터 돌리면 중복된 값이 계속해서 누적되기 때문에 뒤부터 돌린다. 최댓값을 구하므로, dp[j] 는 dp[j..

문제 출처 : https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 프로젝트 팀에 속하지 못한 학생의 수를 구하는 문제이다. 방문 완료 처리(done) - dfs 기존 dfs에서 check(방문)배열은 많이 사용했었지만, 이 문제는 방문 완료(done) 처리가 필요하다. 한 프로젝트에 참여하는 모든 팀원을 구하기 위해, check 되지 않았다면 dfs를 재귀호출한다. 그 후 for문을 통해 팀원의 카운트를 구한 후, 방문 완료 처리를 한다. void..

문제 출처 : https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 공장을 운영할 섬 2개가 주어지고, 물품들의 중량의 최댓값을 구하는 문제이다. 이분탐색으로 중량의 최댓값 찾기 대부분의 이분탐색 코드는 아래와 유사하다. left, right를 두고 mid 값을 찾은뒤, mid 값이 조건에 일치하면 left 값을 mid +1, 그렇지 않으면 right 값을 mid-1로 변경한다. whi..

문제 출처 : https://www.acmicpc.net/problem/1515 1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net 풀이 브루트포스로 숫자를 증가시키며 풀이하는 문제이다. 예시로 입력 - 234092 가 있다고 하자. 처음 포인터는 0번(2)를 가리킨다. 처음 숫자(num)을 0부터 시작해서 반복문을 돌려 증가시킨다. num 0 .. 1 .. 2에서 포인터가 가리키는 2와 일치하게 된다. 이 경우 포인터를 증가시킨다. 이제 포인터는 1번(3)을 가리키고, num은 3이다. 포인터의 수와 num이..

문제 출처 : https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 풀이 dfs로 장애물을 찾고 해당 경우가 조건에 맞는지 판별하는 대표적인 백트래킹 문제이다. 처음 입력을 받을때 teacher(T), none(X)를 vector에 저장해두고 none 자리의 경우의 수를 dfs로 찾는다. 이때 다른 문제와 좀 다른 점은, vector에 push와 pop을 하는대신 바로 arr에 O와 X문자열을 대입해준 점이다. 3개를 찾으면 check_av..