본문 바로가기

전체 글369

백준 1707 이분그래프 문제 URL : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 문제 접근법: 물감의 색이 2개만 주어졌다고 생각하고 어떤 노드에서 출발해서 그노드와 인접한 노드들간에 서로 다른색으로 색칠이 되어있다면 그것은 이분그래프라고 생각하면 됩니다. 쉽게 그림으로 설명해드리겠습니다. 간단하게 1번노드에서 먼저 초록색을 색칠한다면 1번과 인접한 2,4번 노드에 노랑색을 색칠하고 또 2,4번과 인접한 5,6번에 초록색을 색칠하고 5,6번과 인접.. 2020. 7. 26.
백준 17835 면접보는 승범이네 문제 URL : https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 문제 접근법: 다익스트라를 이용할줄 안다면 문제 접근하는건 크게어렵지 않습니다. 면접장까지의 거리가 가장 먼도시와 그거리를 구하기때문에 순방향으로 그래프를 그리셨다면 답은 구해질수 있을지 언정 시간이 굉장히 오래 걸립니다. 일일이 한집에서 면접장까지 구하기때문에 다익스트라를 여러번 돌려야하기 때문에 그렇다면 반대로 면접장까지 .. 2020. 7. 26.
백준 2812 크게만들기 문제 URL : https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K > k; cin >> s; } int main().. 2020. 7. 22.
백준 1890 점프 문제 URL : https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거�� www.acmicpc.net 문제 접근법 : 처음 백트래킹으로 메모이제이션 방법으로 풀다 메모리초과되서 백트래킹방법은 맞는데 어디서 잘못된건지 찾질 못하다 백트래킹 방법을 2중 for문으로 찾는방법으로 바꾸었더니 해결했었고 질문 현황해서 백트래킹을 사용할때 메모리 초과 원인을 찾았다 어느 중앙지점에 0 이있을때 이것이 무한 반복을 돌기때문에 스택메모리가 꽉차니 당연했던겁니다. 우선 처음위치에서 출발했을때 그게.. 2020. 7. 22.

티스토리툴바