1%

문제 https://www.acmicpc.net/problem/2292 풀이 위의 그림에서 빨간 동그라미를 보면 제일 가운데에 있는 빨간 동그라미 안에는 1번 벌집 1개, 그 다음 빨간 테두리 안에는 2번에서 7번까지 6개, 그 다음은 12개, 18개, ... 벌집이 바깥으로 갈수록 6의 배수로 늘어나는 것을 확인할 수 있다. 반복문으로 1+6+12+...를 하면서 이 값이 주어진 n 보다 커질 때를 잘 캐치하면 된다. 결과 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/2292.cpp

문제 https://www.acmicpc.net/problem/1316 풀이 현재 문자(i)와 다음 문자(i+1)을 비교하여 둘이 같을때는 신경쓰지 않고 달라질때 현재 문자(i)가 이미 방문했던 문자인지 알파벳 개수 만큼 있는 check배열을 확인하여 이미 방문했던 문자였으면(true이면) 현재 문자(i)는 떨어져 있는 문자이므로 그룹 문자가 아니다. 결과 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1316.cpp

출처 위키백과

문제 https://www.acmicpc.net/problem/1167 풀이 1. 루트(1번정점)에서 제일 거리가 먼 정점을 찾는다. 2. 찾은 그 정점에서 다시 제일 먼 정점을 찾는다. 그게 바로 트리의 지름이다! bfs탐색을 2번 하여 진행한다. 거리를 저장하는 배열을 만들어서 시작정점에서부터 모든 정점까지 각 정점과의 거리 를 저장한다. 결과 처음엔 트리의 지름 문제를 이해를 못해서 탐색을 한번만 했다가 틀렸다. 질문검색을 통해 문제를 먼저 이해했다ㅠㅠ (+ 트리의 지름 다른 문제도 있다. 이걸 먼저 풀어보는 것이 더 좋았을뻔했다. https://www.acmicpc.net/problem/1967 ) 탐색을 두번해야한다는 것을 깨닫고 진행하는데 두번째 탐색할때 거리배열이랑 체크배열을 비우지 않고 해서 런타임에러나고.. memset으로 비워야되는구나 하고 했는데 #include <cstring>안해줘서 컴파일에러.. 반성하고있다ㅠㅠ 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1167.cpp

문제 https://www.acmicpc.net/problem/1717 풀이 이 문제는 disjoint-set문제로서 union-find로 풀었다. disjoint-set(서로소 집합) : 교집합이 공집합인 집합 Union(a, b) : a가 속한 집합과 b가 속한 집합을 합집합 Find(a) : a가 속한 집합의 번호를 반환 i 1 2 3 4 5 6 7 arr[i] 1 2 3 4 5 6 7 입력 n = 7일때, 서로소 집합의 초기값은 위의 표와 같이 되어있다. Find(1)을 하면 arr[1]==1이므로 1을 return한다. 만약에 같지 않을 경우, 재귀적으로 원소의 부모를 쫓아 올라간다. Union(1, 3)을 하면 먼저 Find를 각각한다. 그러면 pa=1, pb=3이 된다. 둘은 다른 그룹에 있기 때문에 arr[1]=3으로 그룹 번호를 업데이트 해준다. i 1 2 3 4 5 6 7 arr[i] 3 2 3 4 5 6 7 이런 식으로 쭉 진행한다. union-find를 이용하여 kruskal algorithm으로 mst찾는데 쓰인다. 결과 Union연산에서 if(pa != pb) 면 그룹번호를 갱신하도록 조건이 있는데 시간을 단축시키기 위함이다. 이 문제에서는 없어도 맞았다고 한다! 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1

문제 https://www.acmicpc.net/problem/10815 풀이 1920 번과 똑같은 문제라고 할 수 있다. 이분탐색이다. 결과 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/10815.cpp

문제 https://www.acmicpc.net/problem/1920 풀이 이분탐색(Binary Search)로 풀었다. 이분탐색은 정렬되어있는 데이터를 반으로 나누어 탐색하는 방법으로서 오름차순으로 정렬되어있어야한다. sort함수(퀵소트)로 O(nlogn) 시간에 정렬을 해주고 이분탐색으로 O(logn) 시간으로 수를 찾는다. 근데 어차피 입력받을때 O(n+m) 시간이 걸린다.ㅜ 이분탐색은 유용하게 잘쓰이고 중요하니까 자유자재로 쓸 수 있을때까지 연습많이 해야겠다. 결과 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1920.cpp

문제 https://www.acmicpc.net/problem/1427 풀이 정수 n을 입력받고 자리수별로 나눠가면서 벡터에 하나하나 넣어주었다. 그리고 그 벡터를 정렬한다. sort(v.begin(), v.end(), greater<int>()); greater<int>() 를 안쓰면 오름차순으로 정렬이된다. 벡터 출력은 for (int i = 0; i < v.size(); i++) cout << v.at(i);    또는   cout << v[i]; 결과 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1427.cpp

문제 https://www.acmicpc.net/problem/1850 어떻게 했냐면... 처음 딱 생각했을때는 3을 111로 바꾸고 4를 1111로 바꿔서 111과 1111의 최대공약수를 구하려고 했는데, 그렇게 하는게 아니고! 3과 4의 최대공약수가 1이면 답은 1, 3과 6의 최대공약수가 3이면 답은 111이다. 그래서 먼저 입력받은 두수의 최대공약수를 구하고 그 값만큼 반복문으로 printf("1") 해주었다. (직접 정수값으로 1+10+100 이런식으로 구할려고 했는데 시간초과가 떴다.)입력되는 값이  2 63 이므로 long long 타입으로 했다. 결과 입력범위 생각못하고 int형으로 했다가 많이 틀렸다ㅜ 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1850.cpp

문제 https://www.acmicpc.net/problem/2609 어떻게 했냐면... 최대공약수(GCD)를 구하는 방법에는 두가지가 있다. 1. 2부터 min(a, b)까지의 정수를 모두 나눠보는 것과 2. 유클리드 호제법이 있다. gcd(a, b)=gcd(b, a%b)이다. 이 식을 이용해서 재귀적으로 gcd를 구한다. a%b=0이 될때까지 구하면 된다 최소공약수(LCM)을 구하는 방법은 GCD를 이용하면 된다. lcm = a * b / gcd(a, b)이다. 이 공식을 이용하여 lcm을 구한다. 결과 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/2609.cpp

문제 https://www.acmicpc.net/problem/7576 어떻게 했냐면... 토마토를 입력받으면서 익은 토마토(값이 1)는 큐에 넣고 거리값을 0으로 저장한다. 나머지의 거리값은 -1로 한다. 그리고 미로탐색처럼 큐가 비어질 때까지 안익은 토마토가 있으면 그걸 따라가면서 전 거리값보다+1하면서 bfs탐색한다. 결과 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/7576.cpp

문제 https://www.acmicpc.net/problem/2178 어떻게 했냐면... bfs로 풀었다. 거리를 저장해놓는 d[i][j]를 선언해놓고 네 방향에 대하여 갈 수 있는 길이면 d[i][j]를 1씩 증가시켜주었다. 방문했다는 체크배열을 따로 만들어도되지만 나는 거리배열(d[i][j]) 하나로 했다. 결과 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/2178.cpp

문제 https://www.acmicpc.net/problem/4963 어떻게 했냐면... bfs로 탐색했다. 상하좌우 뿐만아니라 대각선까지도 이어져있으면 섬으로 치기 때문에 총 8방향에 대하여 확인하였다. 결과 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/4963.cpp

https://www.acmicpc.net/problem/10451 순열의 크기 n은 그래프의 정점의 개수이자 간선의 개수라고 할 수 있다. 이 그래프는 방향그래프이고 한 점정당 out degree가 1이다. 그래서 연결 요소의 개수를 구하는 방법과 마찬가지로 dfs탐색을 한 횟수를 출력하면된다. 코드↓ https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/10451.cpp

https://www.acmicpc.net/problem/1707 인접리스트로 그래프를 표현하고 dfs로 탐색했다. 이 그래프가 이분 그래프라는 가정하에 A쪽과 B쪽이 있으면 체크배열엔 아직 방문하지 않았으면 0,  A에 방문했으면 1, B에 방문했으면 2를 표시했다. 방문하지않은 노드에 방문했다는 표시는 1또는 2이므로 dfs의 파라미터로 c값을 추가하여 재귀적으로 함수를 부를 때 3-c를 넘기도록 했다. (처음에 c=1이면 다음번엔 c=3-c=2, 그 다음번엔 c=3-c=1 ...) dfs가 끝나고나면 이 그래프가 이분그래프인지 확인하는 절차를 가지는데, 인접리스트로 표현되어있는 그래프이므로 이분그래프라면 해당 정점에 연결되어있는 정점들과는 다른 체크 값을 가져야한다. 만약 같은 값을 가졌다면 이분 그래프가 아니다! + 그래프를 저장한 벡터배열과 체크배열을 초기화(clear)하는 것에 유의해야한다! 코드↓ https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/1707.cpp