BOJ 백준기타 검색 결과

해당 글 22건

백준 11653 - 소인수분해

출처 : https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 고려사항 나누는 수를 2부터 시작해서 나눈 결과가 0이면 출력한다. 나머지가 0이 아니면 d를 1씩 증가하며 반복하고, num 이 1일 때 완료한다. 작은 소수부터 나눗셈을 하게 되는 방식이라, 증가된 d가 4와 같이 소수가 아닐 시에는 이미 4의 약수인 2로 나눗셈을 진행했었기 때문에 나눠지는 일이 없기 때문에 다시 d를 증가시키게 된다. #include using namespace std; int main() { int num, d = 2; cin>>num; while(num != 1){ if(num %..
BOJ 백준/기타 4년 전

백준 02609 - 최대공약수와 최소공배수

출처 : https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 고려사항 유클리드호제법으로 최대공약수 구하기 최소공배수 = a * b / gcd(a, b) #include using namespace std; int main() { int a, b, tmp, gcd, lcm; cin>>a>>b; lcm = a * b; if(a 0){ tmp = b; b = a % b; a = tmp; } gcd = a; lcm /= gcd; cout
BOJ 백준/기타 4년 전

백준 02252 - 줄 세우기

출처 : https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 고려사항 위상정렬 알고리즘 사용. 위상정렬 설명이나 질문 페이지에 가면, 자신에게 들어오는 간선의 수가 0인 정점이 더이상 없지만, 아직 방문 안한 정덤들이 있어 더 이상 위상정렬을 진행할 수 없을 때, 이를 순환상태로 보고 이를 찾기 위해 그래프를 dfs로 탐색하는 방식이 있는데, 굳이 왜그래야 하나 싶어서 내 생각대로 풀어보았다. edgeIn 벡터에 자..
BOJ 백준/기타 4년 전

백준 04195 - 친구 네트워크

출처 : https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 고려사항 유니온 파인드 문제. map 를 통해 각각의 이름에 idx를 부여하여 유니온 파인드 알고리즘을 적용. vector 로 union 시에 구성원 수를 같이 업데이트 해주고 그 값을 반환하면 됨. 원래 유니온 파인드에서는 같은 루트를 지닌 즉, 같은 집합에 속해 있으면 어느 곳을 업데이트 해줘도 크게 상관이 없기 때문에, 보통 23 라인부터는 else로 묶는데 이 알고리즘으..
BOJ 백준/기타 4년 전

백준 11438 - LCA 2

출처 : https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 고려사항 lca 알고리즘 문제들을 두 세개 풀어봐서 그 로직을 잘 이해하고 있었는데..... 맞왜틀의 연속으로 인해 (매우 큰 착각ㅎㅎ) 자꾸 검색하고 참조한 결과 그냥 쌩 남의 코드랑 똑같아졌다...(그런데 같은 코드가 여러개 보인다..ㅎㅎ) 확실하진 않으나 한시간 넘게 고민해본 결과... 이전의 코드는 dfs 함수 없이 간선의 노드 정보 2개가 들어오면, 보통 트리 문제에서 ..
BOJ 백준/기타 4년 전

백준 01976 - 여행 가자

출처 : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 고려사항 유니온 파인드 구현. findParent는 반복문으로도 가능. while( arr[city] != city ){ city = arr[city]; } 유니온 함수가 중요! 조사 중인 두 도시의 부모 도시를 구하고, 값이 더 작은 도시를 루트로 합친다! 이 때 중요한 것은! 조사 중인 도시의 부모 배열을 수정하는 것이 아니라, ( 해도 되긴하지만 연산 이득이 크지 않음. ) 두 도시..
BOJ 백준/기타 4년 전

백준 02108 - 통계학

출처 : https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 고려사항 머지소트로 구현을 해보았음. ( sort( ) 쓰면 편하지만 연습해보자구여~ ) 같은 수가 배열에 포함 될 수 있으니 23 번 줄처럼 부등호로 비교를 하여 i 인덱스를 먼저 소모시켜준다. ( i 는 left 부터 시작했으니 더 빠른 인덱스이며, 머지 소트는 같은 값에 대하여 순서를 보장해주는 stable sort를 만족해야 한다. ) (사실 이 문제에서 구현 안해도 큰상관은...ㅎ) 반올림은 cmath의 round..
BOJ 백준/기타 4년 전

백준 01181 - 단어 정렬

출처 : https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 고려사항 stl 들을 사용하여 쉽게 풀 수 있음. 문자열의 길이를 키로 map m 을 만들고, 문자열의 길이를 구해서 이미 m 에 있으면, 해당 set에 문자열을 넣어주고, 없으면 새로운 키와 함게 삽입해준다. 정렬은 map, set 자료구조의 이점으로 자동으로 진행. 본 문제에서 for( auto : ) 을 사용하다가 알게된 사실인데, 보통 벡터나, 맵 등에서 간편하게 사용하려고 a..
BOJ 백준/기타 4년 전