코딩테스트 연습/Baekjoon (78) 썸네일형 리스트형 [Baekjoon] 백준 9938번: 방 청소 (c++) https://www.acmicpc.net/problem/9938 9938번: 방 청소 처음 6개의 술은 규칙 1에 의해서 1, 3, 5, 7, 9, 2번 서랍에 보관할 수 있다. 7번째 술은 규칙 3을 적용할 수 있다. 1번 서랍에 들어있는 술을 2로, 2번 서랍에 들어있는 술을 3으로, 3번 서랍에 들어있 www.acmicpc.net 문제가 이해가 안가서 구글 검색으로 Union Find문제라는 걸 알아냈다... ㅠㅠ 검색 없이 솔루션 찾는걸 연습해야하는데... 예제를 봐도 이해가 잘 안갔다. 코드는 맨 아래! 아래 설명을 꼭 이해해야 문제를 풀 수 있다. 규칙 1 2 3 4 5 순서대로 실행해야 한다 1. 서랍 Ai가 비어있다면, i번 술을 그 서랍에 보관한다. 2. 서랍 Bi가 비어있다면, i번 .. [Baekjoon] 4193번: 친구 네트워크 (c++) 더보기 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net Union-Find 문제인데, 숫자가 아니라 string 형태이다보니 처음에 어떤식으로 접근해야할지 감이 잘 안잡혔다. 내가 사용한 방법은 각각 친구관계는 net에 저장하고, net과 관련되어있는 친구네트워크의 크기(길이)는 cnt에 저장해서, 주어진 입력 a, b 둘중 cnt크기가 더 큰곳에 작은것을 합쳐주는 방식으로 진행했다. 1. net 해시맵에 입력받은 문자열을 자기자신으.. [Baekjoon] 1593번: 문자 해독 (python) https://www.acmicpc.net/problem/1593 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net c++으로 풀었던 문제를 python으로도 풀어봤다 https://ggsing.tistory.com/35 [Baekjoon] 1593번: 문자 해독(c++) https://www.acmicpc.net/problem/1593 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에.. [Baekjoon] 5568번: 카드 놓기 (c++) https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net DFS로 사용했던 카드(isVisited[i] = true)는 다시 사용하지 않는 방법으로 구현했다. 1. 모든 카드를 뽑는 경우를 생각해서 for문을 카드의 개수 n만큼 반복하며 DFS 실행 2. 처음 뽑은 카드 inp[0]에 대하여 방문 표시 isVisited[0] = true - 카드를 k개만큼 뽑았을 때만 (현재 DFS의 깊이 cnt와 주어진 k(=depth)의 크기가 같을때만) unordered_map 해시맵 card에다 넣어줌 - 숫자가 같은 카드는 다시 세지 않기 위해 unord.. [Baekjoon] 10814번: 나이순 정렬 (c++) https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 1. 2차원 벡터 member 안에 나이, 이름, 입력순서를 순서대로 저장한다. 2. member를 정렬한다. - 나이가 더 작은 순서대로 앞에 세운다 a[1] < b[1] - 나이가 같은 경우 입력순서가 더 빠른것부터 세운다 if(a[1] == b[1]) return a[2] < b[2] * member는 string 배열 이므로, 나이와 인덱스를 숫자로 비교하기위해 stoi 로 감싸줘야 함 #inc.. [Baekjoon] 2606번: 바이러스 (c++) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 모든 반례를 해봤는데도 계속 틀렸다고나와서 좀 헤맸다 ㅠㅠ Union Find를 다시 공부하다보니 알게됬는데 return parent[x] = Find(parent[x]) 가 아니라 return parent[x]로 해버려서 x의 맨 위 부모(root)를 못찾아서 그런거였다..! 1717번과 비슷하게 Union Find를 사용하면 쉽게 풀 수 있는 문제였다 1. 입력받은 a b 연결 (Union) 2. .. [Baekjooin] 1717번: 집합의 표현 (c++) https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 시간초과가 떠서 왜지 싶었는데 입출력이 느려서 아랫줄을 추가해줘야 했다. ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); https://www.acmicpc.net/problem/15552 참고 합집합 연산이라는 말에 Union Find를 써야겠구나 생각했다. (0, a, b) 에서 맨앞이 0이면 .. [Baekjoon] 9465번: 스티커 / dynamic https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 예시가 50 10 100 20 40 30 50 70 10 60 일때, 맨 뒤의 열 60부터 생각해보면, 60은 그 전 대각선 20으로부터 오거나, 2칸 전 대각선 100으로 부터 온 값 중 큰것이 더해질수 있다. 40은 전 대각선 10으로부터 오거나, 2칸 전 대각선 70으로부터 온 값 중 큰것이 더해질 수 있다. 세번째 전 이후 대각선의 경우, i를 반복하며 더해지는 대각선이기 때문에.. 이전 1 2 3 4 5 ··· 10 다음
