솔브드 플레찍기 1일차

골딱이의 플레찍기 일기

실버 골드들 복습이랑 플레 문제들 위주로 재밌어보이는 거 풀 것 같음

 

16975 수열과 쿼리 21

https://www.acmicpc.net/blog/view/88

펜윅 트리 200% 활용하기

https://blog.naver.com/jh05013/221475142152

BOJ 16975부터 16979까지

이 두 개 글을 보면 펜윅으로 풀 수 있다

근데 200퍼 활용하기에서 나온 일반식으로 나름 구현했다고 생각했는데 왠지 다른 값이 나오더라

ps뉴비라 제대로 구현하는 방법을 잘 모르겠네

 

그래서 1번에서 이런 방법이 있구나 이해하고 2번 방법으로 풀었음

[a,b]에 x를 더하는 쿼리를 2개의 쿼리로 나눔

즉 update를 하는데 a에 x를 더하는 쿼리/b+1에 -x를 더하는 쿼리 두 번 해준다

입력 받을 때도 i에 x를 더함/i+1에 -t를 더함 이렇게 두 번의 쿼리로 처리해주고

출력은 처음~b까지 출력해주면 된다

 

관련 설명: https://foxtrotin.tistory.com/140

펜윅트리로 '세그먼트 트리 느리게 업데이트 하기(Lazy Propagation)' 구현하기(2934 LRH식물 펜윅트리)

문제 코드: 

https://github.com/proqk/Algorithm/blob/master/Segment%20Tree/16975%20%EC%88%98%EC%97%B4%EA%B3%BC%20%EC%BF%BC%EB%A6%AC%2021(%ED%8E%9C%EC%9C%85%20%ED%8A%B8%EB%A6%AC)_2.cpp

 

11725 트리의 부모 찾기

현재 노드의 자식이 존재해서 재귀에 들어가게 된다면

현재 노드는 부모라서 부모 배열에 저장해둔다

https://github.com/proqk/Algorithm/blob/master/Tree/11725%20%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EB%B6%80%EB%AA%A8%20%EC%B0%BE%EA%B8%B0.cpp

 

 

1068 트리

실버1에 완전 쉬운 문제라고 하던데 더럽게 많이 틀렸다;;

97퍼에서 틀려서 미칠 것 같았는데

놓친 반례로는 '루트만 남았을 때는 루트가 리프'라서

2

-1 0

1

인 경우 1을 출력해야 한다

그리고 루트를 지우는 경우는 0인 것도 확인해줘야 한다

https://github.com/proqk/Algorithm/blob/master/Tree/1068%20%ED%8A%B8%EB%A6%AC.cpp

 

 

1991 트리 순회

전위 후위 중위 순회를 한 함수에서 할 수 있다

먼저 전위면 출력 후 왼쪽으로 재귀 출발

중위면 전위 출발 이후 출력한 뒤 오른쪽으로 재귀 출발

후위면 전후위가 다 출발하고 출력한다

https://github.com/proqk/Algorithm/blob/master/Tree/1991%20%ED%8A%B8%EB%A6%AC%20%EC%88%9C%ED%9A%8C.cpp

 

 

5567 결혼식

처음에는 1번의 친구들을 파악하며 cnt세서 2까지만 자르는 식으로 접근했는데

재귀를 돌다보니까 당연히 꼬여버림

 

그래서 그냥 나눠버렸다

1) 1번의 친구들은 파악해서 재귀 돌리고

2) 그 친구들의 친구들을 파악해서 친구 배열 체크

void find(int now) {
	for (int i = 0; i < tree[now].size(); i++) { //now의 친구 파악
		int next = tree[now][i];
		friends[next] = true;
	}

	if (now == 1) { //1번의 친구 파악
		for (int i = 0; i < tree[now].size(); i++) {
			int next = tree[now][i];
			find(next);
		}
	}
}

그러면 재귀는 1번의 친구와, 친구의 친구까지만 for문을 돌기 때문에

자연스럽게 친구의 친구까지만 카운트하게 된다

 

이사람은 인접행렬로 풀었지만 그림은 참고하기 좋았음 https://itadventure.tistory.com/27

https://github.com/proqk/Algorithm/blob/master/Tree/5567%20%EA%B2%B0%ED%98%BC%EC%8B%9D.cpp

 

 

2667 단지 번호 붙이기

이거 진짜 제일 간과하기 쉬운 게

입력값 사이에 띄어쓰기가 없음

그냥 map[i][j]이런 식으로 받으면 입력만 계속 해야 할 거임

 

C에서는 %1d 로 받으면 1칸씩 입력 받을 수 있고

C++에서는 한 문장을 string으로 받은 뒤 for문을 돌면서

string의 한 문자마다 -'0'해줘서 정수로 만드는 과정을 거쳐야 함

 

그리고ㅋㅋ 사실 string으로 끊기 귀찮아서 stdio.h랑 iostream 다 불러와서

입력만 scanf로 했는데 백준에 들어가자마자 바로 틀렸다고 뜸ㅋㅋ

알고보니 ios::sync_with_stdio(false); 를 한 이후에는 C랑 C++의 입출력 방식을 섞어 쓰면 안 되더라 딱 걸려버림

(https://www.acmicpc.net/board/view/49670)

 

https://github.com/proqk/Algorithm/blob/master/dfs/2667%20%EB%8B%A8%EC%A7%80%EB%B2%88%ED%98%B8%20%EB%B6%99%EC%9D%B4%EA%B8%B0_%EC%94%A8%ED%94%8C.cpp

 

 

 

1012 유기농 배추

사소하지만 n과 m 잘 썼는지 확인해야 하고

map배열을 테케마다 재사용하니까 memset을 꼭 돌려줍시다

memset은 memory.h에 있다

https://github.com/proqk/Algorithm/blob/master/dfs/1012%20%EC%9C%A0%EA%B8%B0%EB%86%8D%20%EB%B0%B0%EC%B6%94_%EC%94%A8%ED%94%8C.cpp

 

 

2606 바이러스

dfs로도 할 수 있지만 생긴 게 그래프처럼 생겼다

근데 위에서 마침 트리를 풀고 왔으니까 1번 컴퓨터를 루트로 하는 트리처럼 풀어봤는데 풀리더라

5567 결혼식이랑 비슷했던 문제

 

dfs

https://github.com/proqk/Algorithm/blob/master/dfs/2606%20%EB%B0%94%EC%9D%B4%EB%9F%AC%EC%8A%A4_dfs.cpp

트리

https://github.com/proqk/Algorithm/blob/master/dfs/2606%20%EB%B0%94%EC%9D%B4%EB%9F%AC%EC%8A%A4_%ED%8A%B8%EB%A6%AC.cpp