코딩공부

전체 글 검색 결과

해당 글 130건

CS 1일차

Array VS Linked List Bubble Sort HTTP - GET vs POST 스케줄러 Array 논리적 저장 순서와 물리적 저장 순서가 일치. 특정 자료형들이 메모리 공간에 연속적으로 존재. 인덱스를 통해 .Random Access 가능 -> O(1) 삽입, 삭제 시에는 해당 인덱스 이후의 자료들이 Shift 됨 -> O(n) 일반적으로 Array 선언 시, Compile Time 에 정적 메모리 할당. + 가변 배열이 아닌 이상, 선언시의 Array Size 는 immuable. => 메모리 공간 활용 제약, 크기 초과시, 변경 시에 다른 주소에 재할당 필요! Linked List 저장 공간상에 자료들이 흩어져 있고, 각 노드가 자신의 다음 노드의 주소를 지닌다 -> 자료 외에 별도의 ..

CS 공부/CS Study 원본 2020. 12. 28. 22:37

백준 02178 - 미로 탐색

출처 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 고려사항 BFS 를 활용 - BFS를 활용하면 레벨 (몇 번 움직였는지)가 작은 순서대로 탐색하기 때문에 먼저 (N, M) 에 도달하면 더이상 탐색 없이 return 해줄 수 있다. DFS를 사용하면 현재 움직인 cnt 값을 인자로 넘겨주며 값을 구할 수 있지만 N, M 에 도달해도 다른 가지까지 탐색을 진행해야 최소값인지를 알 수 있다. ( 가지치기를 이용하면, 연산을 줄일 수 있긴 하지만.. ) #include #i..

BOJ 백준/DFS + BFS 2020. 12. 20. 02:43

백준 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 백준/기타 2020. 12. 19. 23:48

백준 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 백준/기타 2020. 12. 18. 23:57

백준 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 백준/기타 2020. 11. 27. 03:19

백준 04195 - 친구 네트워크

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

BOJ 백준/기타 2020. 11. 26. 11:42

백준 11438 - LCA 2

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

BOJ 백준/기타 2020. 11. 25. 01:53

백준 01976 - 여행 가자

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

BOJ 백준/기타 2020. 11. 23. 17:27