728x90
반응형

백준 33

[BOJ] 백준 2636 치즈 c++ (bfs)

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

Tech/Algorithm 2023.10.11

[프로그래머스] 서강그라운드 c++ (다익스트라)

문제 출처 : 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}..

Tech/Algorithm 2023.09.13

[BOJ] 백준 14728 벼락치기 c++ (배낭, dp)

문제 출처 : 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..

Tech/Algorithm 2023.08.01

[BOJ] 백준 9466 텀 프로젝트 c++ (dfs)

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

Tech/Algorithm 2023.07.15

[BOJ] 백준 1939 중량제한 c++ (이분탐색, bfs)

문제 출처 : 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..

Tech/Algorithm 2023.07.13

[BOJ] 백준 1515 수 이어 쓰기 c++ (문자열, 구현)

문제 출처 : 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이..

Tech/Algorithm 2023.07.06

[BOJ] 백준 18428 감시 피하기 c++ (백트래킹)

문제 출처 : 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..

Tech/Algorithm 2023.07.05

[BOJ] 백준 1021 회전하는 큐 c++ (deque)

문제 출처 : https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 이 문제는 덱을 사용하는 문제이다. 2번 방법(왼쪽으로), 3번 방법(오른쪽으로) 중 짧은 거리를 구해서 해당 방법대로 push, pop을 반복한다. 이때 주의할 점은, left < right 인 경우 이동횟수가 +1이므로 최종 cnt에 1을 더해주어야 한다. 코드 #include #include #include using namespace std; int N, M; int..

Tech/Algorithm 2023.07.05

[BOJ] 백준 2143 두 배열의 합 c++ (이분탐색, 누적 합)

문제 출처 : https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 어떻게 이분탐색을 돌려야할지 고민이 되는 문제이다. 중요한 부분은, A와 B의 누적합을 미리 저장해두는 것이다. 누적 합 A, B 배열에서 모든 부 배열의 누적합을 저장한다. vector aSum, bSum; for (int i = 0; i < N; i++) { int sum = A[i]; aSum..

Tech/Algorithm 2023.04.20
728x90
반응형