일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- BOJ
- 연결요소
- 이분탐색
- OFFSET
- BFS
- upper_bound
- Kafka
- 성적평가
- 6987
- 13908
- Docker
- msSQL
- @P0
- 소프티어
- boj #19237 #어른 상어
- 오퍼레터
- 백준
- compose
- 경력
- 처우협의
- 기술면접
- 처우산정
- softeer
- 퇴사통보
- incr
- 물채우기
- 파라메트릭
- 매개변수탐색
- dfs
- 백트래킹
- Today
- Total
목록알고리즘 문제/BOJ (413)
기술 블로그
https://www.acmicpc.net/problem/17471 공부겸 오랜만에 풀어본 문제다. #include using namespace std; /* 1. 두 선거구로 나누기 - 백트래킹 2. 각 선거구 내 구역들이 인접한지 check - bfs 3. 모두 인접해있다면, 두 선거구의 총인구합 구하기 - 구현 */ int N, person[11]; // person[i] : i번째 구역 인구 수 int ans = 2e9; vector v[11]; bool used[11], num[11]; bool chk(vector a, vector b) { memset(used, false, sizeof(used)); queue q; used[a[0]] = true; q.push(a[0]); // a선거구 내에..
https://www.acmicpc.net/problem/9935 stack을 활용한다. 1. 입력받은 문자열을 활용하여, for문을 수행한다. 입력받은 문자열의 문자를 stack에 push한다. 2. 현재 for문의 문자가 폭발 문자열의 마지막 문자와 같은지 비교한다. 3. 같으면, 위의 1번 stack에 담긴 문자를 하나씩 비교한다. #include using namespace std; int len; string s, t; stack st; int main() { cin.tie(0); cin >> s >> t; len = t.length(); for (auto c : s) { st.push(c); // 입력받은 문자열을 for문 돌려준다 // 현재 문자와 폭발문자열의 마지막 문자가 같으면 if (c..
https://www.acmicpc.net/problem/15683 오랜만에 풀어본 대표적인 구현 및 시뮬레이션 문제이다. #include using namespace std; #define MAX 10 int Map[MAX][MAX]; int R, C, m[MAX][MAX], ans = INT32_MAX; int loop[6] = { 0, 4, 2, 4, 4, 1 }; int dy[4] = { 0, 1, 0, -1 }; int dx[4] = { 1, 0, -1, 0 }; vector v; bool chk(int Y, int X) { return (0
https://www.acmicpc.net/problem/2660 INF를 처음에 2e9로 했는데 계속 fw[i][j]의 값이 쓰레기 값으로 출력됐다. 1000으로 수정하니 해결됨. #include using namespace std; #define MAX 55 #define INF 1000 int fw[MAX][MAX]; int score[MAX]; int n, a, b; vector v; int main() { cin.tie(0); for (int i = 1; i < MAX; i++) { for (int j = 1; j < MAX; j++) { fw[i][j] = i == j ? 0 : INF; } } scanf("%d", &n); while (true) { scanf("%d %d", &a, &b);..
※ 아래 문제도 풀어보자.(회의실 개수 최댓값 구하기) https://www.acmicpc.net/problem/1931 https://www.acmicpc.net/problem/11000 강의실 개수 최솟값을 구하는 문제이다. 시작시간 기준으로 오름차순 정렬한다. 우선순위 큐를 활용하여, 종료시간을 넣어주면서 시작시간을 활용한다. #include using namespace std; int N; vector v; int main() { //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin); cin.tie(0); scanf("%d", &N); int S, T; for (int i = 0; i < N; i++) { scanf("%d %..
※ 이 문제는 1차원 배열에 대한 문제이고, 2차원 배열로 확장시킨 문제가 2021년 9월 11일 토요일 2022 카카오 블라인드 코딩테스트 6번에 출제됐다. ※ 이 글은 안즈님의 카카오 6번 문제 해설(누적합을 이용한 연산)을 참고하여 작성하였고, 제가 다시 편히 보기 위해 정리하였습니다. https://www.acmicpc.net/problem/19951 배열이 주어지고, 배열의 구간에 수를 더하고 빼는 쿼리가 있다. 세그먼트 트리를 이용해도 되지만, 우리는 연산 중간에 배열의 값을 알 필요가 없고, 모든 쿼리(연산) 이후에 마지막 단 한 번만 구하면 되기 때문에, 누적합을 이용할 수 있다. 문제에 대한 정답 코드는 맨 아래에 있다. 이 문제를 풀기 위한 누적합 연산 개념 설명(아래 사진)을 추가한다..
https://www.acmicpc.net/problem/1113 핵심은 높이를 2부터 입력된 최대 높이까지 각각 하나씩 채워주는 것이다. main() 함수 내의 for문 h의 의미는 "h보다 작은 곳을 찾아 높이를 딱 h까지 채우겠다."라는 의미로 해석하면 된다. 또한, dfs가 수행될 때, 바깥 쪽(행과 열이 0 또는 R - 1 또는 C - 1)일 때는 바깥 쪽으로 흘러내리므로, 이때는 답 구하는 연산에 셈하지 않는다.(bool형 변수인 stop 활용하였음) 1. 입력된 값들 중 최댓값 구하기(최대 높이 = H) 2. 2 ~ H 각각 수행 → h 3. h보다 미만인 곳을 찾아 vector에 넣어준다. 4. vector를 활용하여, dfs 수행 5. 바깥 쪽일 경우 답 구하는 연산에서 제외 6. 바깥 ..
https://www.acmicpc.net/problem/2665 처음에는 단순 queue로 구현했다가, 예제 1번의 답이 계속 5로 나왔다. 문제를 잘 읽어보면 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오. 라고 쓰여있는데, 이는 '검은 방'은 최대한 피해서 가야한다는 의미이다. 즉, 검은 방과 흰 방 중 우선순위가 더 높은 방은 흰 방이다. 이 부분에서 힌트를 얻어, queue말고 deque로 구현한다. 다음에 이동할 방이 검은 방 → deque의 맨 뒤(우선순위가 낮으므로) 다음에 이동할 방이 흰 방 → deque의 맨 앞(우선순위가 높으므로) #include using namespace std; #define MAX 55 int n, m[MAX][MAX]; int ..