baekjoon18 [BFS] 백준 10026 적록색약 C++ https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 : 항상 느끼지만 백준 난이도는 좀 이상하다 실버 문제 못 풀때도 많은데 골드 문제라고 잔뜩 쫄아서 문제 읽어봤는데 그냥 BFS 두번 돌리면 되는거 아니야? 생각들어서 하나는 R과 G를 구분할 때 , 하나는 R과 G를 같은 색으로 취급할 때 이렇게 두개의 map을 만들어서 bfs함수를 두번돌렸더니 결과는 맞았다. 해결전략을 간단히 설명하면 주석에도 써놓았는데 R: 1, G: 2, B:.. 2021. 8. 18. [DFS,BFS] 백준 2583 영역구하기 C++ https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 : 풀이 : bfs 문제 중에 그림(백준 1926) 문제와 유사해서 그걸 풀었던 방식과 비슷하게 풀었다. 좌표의 최대값(100)크기의 이차원 배열을 만들어서 색칠된 부분을 1 색칠이 안된 부분을 0으로 두고 bfs 탐색을 통해 0인 부분의 넓이를 구하는 방법이다. 이런 식으로 구해진 넓이는 우선순위 큐에 넣어서 오름차순으로 정렬하여 출력가능 단, 조금 주의해야 할 점이 있.. 2021. 8. 16. [그리디] 백준 13305 주유소 C++ https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 : 그리디 알고리즘을 이용하는 문제이므로 최소가격으로 이동하려면 가장 싼 기름 값으로 많이 주유하면 된다! 접근 방법 자체는 쉬운문제지만 메모리 범위 라던지 구현에서 생각보다 삽질을 많이 함.. 처음에는 city 구조체를 정의해서 vector에 넣어서 풀었는데 굳이 그렇게 할필요가 없었다. 거리와 가격이 최대 1,000,000,000 까지 입력되므로 int로 계산하면 오버플로우.. 2021. 8. 13. [그리디] 백준 1541 잃어버린 괄호 C++ https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제자체는 간단한데 포스팅하는 이유는 풀이과정에서 코드가 긴거 같아 찾아보니 코드를 줄일 수 있는 방법이 있었다 일단 접근방법은 괄호를 사용해서 최솟값이 되게하는 것이므로 -기호가 나온 이후부터 숫자를 계속 빼주면된다! 왜냐 예를 들어 10 - 20 + 30 -40 -50=? 이라는 식이 있다고 가정할 때 최솟값을 찾으려면 10 - ( 20 + 30 ) - 40 - 50 이된다. 즉, 중간의.. 2021. 8. 13. [그리디]백준 1931 회의실배정 C++ https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 동전문제와 함께 그리디알고리즘의 대표적인 문제! 문제 처음 풀 때 막 간트차트도 그리고 고민했는데 어렵게 생각하지 말고 쉽게 생각하면 금방 풀린다 회의의 갯수가 최대가 되야 하므로 내가 접근한 방법은 회의 시간이 짧은 순서대로 회의를 배정하는 것 이다. 그러기위해 시작 시간과 끝나는 시간을 담은 벡터를 회의 시간이 짧은 순서대로 먼저 정렬 해주었다. 참고로, 이때 sort함수 사용했는데 비교 함수를 정의하여 vector의 second값을 기준으로 오름차순 정렬을 해주고 second값이 같을 경우 first기준으로.. 2021. 8. 12. [DP] 백준 12865 평범한 배낭 C++ 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 처음 읽고 쉬워 보여서 2시간넘게 고민 했는데 풀지못했다.. 결국 풀이를 찾아 봤는데 knapsack알고리즘 이라고 꽤나 유명한 알고리즘이다. 나중에 알고리즘 관한 부분은 따로 정리해서 업로드 할 예정. 내가 생각하지 못한 솔루션은 무게 남을 때 어떻게 최댓값을 찾을 것인가(코드상으로 dp[i-1][j-weight])부분이었다. 천.. 2021. 8. 12. 이전 1 2 3 다음
