본문 바로가기

알고리즘 공부 및 문제 풀이/백준(BOJ)

 (220)
[boj] 백준 2565 전깃줄 - dp, 증가하는 수열 [문제] https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net [풀이] 왼쪽 전깃줄을 기준으로 정렬했을 때, 오른쪽 전깃줄에서도 똑같이 증가하는 번호만큼 전깃줄이 교차하지 않는다. 1 8 2 2 3 9 4 1 6 4 7 6 9 7 10 10 예를 들어, 다음과 같이 정렬을 하면, 오른쪽 전깃줄에서는 1, 4, 6, 7, 10 으로 계속 증가하는 형태를 띄므로 최대 5개의 전깃줄이 교차하지 않는다. 즉 8-5=3개의 전깃줄만 자르면 된다. 이는 곧 증가하는 ..
[boj] 백준 16234 인구 이동 - BFS [문제] https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net [풀이] BFS 문제. 각 나라를 모두 돌면서 BFS 탐색을 한다. 인접한 나라와의 인구수 차이가 l 과 r 사이인 연합이 가능한 나라에 대해서는 따로 queue를 선언해 넣어주고, 인구수의 합과 연합국의 개수를 카운트하는 변수를 선언해 갱신해준다. 탐색이 끝나 queue가 비면 연합국에 대해 인구수를 갱신해준다. 또한 인구 이동이 일어날 경우, flag를 true로 바꿔줘..
[boj] 백준 2110 공유기 설치 - 이분탐색 [문제] https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net [풀이] 문제를 이해 못해서 당황했으나... 가장 인접한 두 공유기 사이의 거리가 최대가 되게하라는 것은 결국 c개의 공유기를 적절한 거리를 두고 설치할건데, c개의 공유기를 설치할 때의 공유기가 설치된 집들 간 거리 중 최소 거리(가장 인접한)가 최대가 될 때의 거리를 출력하라는 것이다. 오랜만에 푸는 이분탐색 문제이다. 먼저 공유기가..
[boj] 백준 12856 평범한 배낭 - 동적 프로그래밍 [문제] https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net [풀이] 0/1 knapsack 문제로 잘 알려져있는 동적 프로그래밍 대표 문제이다. 물건을 쪼갤 수 있는 경우 greedy로 풀지만 0/1로 나눌 수 없다면 동적 프로그래밍으로 해결한다. dp[i][j] 배열은 i 번째만큼의 물건을 배낭에 넣을 수 있고, j 만큼의 무게를 견딜 수 있다고 할 때 배낭에 있는 물건들의 최대..
[boj] 백준 3190 뱀 - 시뮬레이션 [문제] https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net [풀이] 시뮬레이션 문제로 주어진 조건을 잘 구현해내면 된다. 앞서 풀었던 로봇청소기와 같이 방향을 다루기 때문에 dx, dy 배열을 미리 선언해 놓고 사용하는 것이 좋다. push와 pop을 front, back 모두에서 할 수 있는 자료구조인 deque을 이용해 뱀의 머리와 꼬리 위치를 저장해두는 것이 키포인트다. visited 배열을 이용해 뱀이 현재 좌표에 위치해 있는지 표시해줬다. 주의..
[boj] 백준 14503 로봇 청소기 - 시뮬레이션 [문제] https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [풀이] 문제에 나온 구현 방식 그대로 시뮬레이션 코드를 짜되, 시간 초과가 나지 않도록 리팩토링 하는 과정이 필요했다. 청소가 가능하면 바로 그 방향으로 이동하여 청소를 계속하고(2-a) 청소가 불가능하면 다시 회전하여 탐색한다.(2-b) 네 방향을 모두 탐색할 동안 청소를 하지 못하는 경우에는(2-c) 후진을 한 위치가 벽인지 확인하고, 벽일 경우 while문을 빠져나와 종료된다.(..
[boj] 백준 15686 치킨배달 - DFS, 조합 [문제] https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net [풀이] 치킨거리의 합을 가장 작게 만드는 m개의 치킨집을 선택해야 한다. 이는 곧 (1,2,3)을 선택하나 (2,1,3)을 선택하나 똑같기때문에 조합을 만든 후 비교해야 한다. 조합에 대해서는 dfs를 이용해 구현 가능하다. i 번째 치킨집이 조합에 포함되면 check[i]를 true로 바꿔주고 m개의 치킨집에 대한 조합이 완성될 때까지 반복한다. m개의 치킨집에 ..
[boj] 백준 10026 적록색약 - BFS [문제] https://www.acmicpc.net/problem/10026 [풀이] BFS 또는 DFS로 풀 수 있다. 이전 같은 유형의 문제와 비슷하게 같은 색의 약이 들어있는 구역에 대해서 queue에 집어넣어 모두 방문을 해주고, 방문하지 않은 다른 색의 약에 대해 count를 증가시켜주며 구역의 수를 구한다. 적록색 약의 경우 R과 G를 구분하지 못하므로 section 배열을 이 두 약이 같게 취급되도록 변경해준다. visited 배열 초기화하는 것 잊지 말 것! [코드] #include #include #include #include #include using namespace::std; int n; char section[100][100]; int dx[] = { 0, 0, 1, -1 }; ..

티스토리툴바