algorithm

백준 17471 브루트 포스

백준 7662 c++ set

백준 1005 ACM Craft

백준 1939 중량제한

2660 회장뽑기

overflow 검사 방법 ■ num1 + num2 num1+num2 >INT_MAX => if(num1 > INT_MAX-num2) ■ num1 * num2 num1*num2 > INT_MAX => if(num1 > INT_MAX/num2) 가끔씩 long long 범위를 넘어가는 수에 대해서는 overflow를 어떻게 검사하나 싶었는데 굉장히 간단...

백준 16137 견우와 직녀

백준 1477

백준 1377

백준 13168

백준 7570

백준 11505

백준 1022

문제링크 https://www.acmicpc.net/problem/2638 문제 키포인트 가장자리는 치즈가 놓이지 않으므로 가장자리에서 부터 BFS나 DFS를 실행해줍니다. (아래 코드는 bfs 이용) 0인 부분(치즈가 없는 영역)은 방문하지 않았다면 큐에 넣어주고 1인 부분(치즈가 있는 영역) 은 큐에 넣지 않고 해당 좌표의 값을 1증가 시켜줍니다. 큐...

문제링크 https://www.acmicpc.net/problem/16986 문제 키포인트 N이 1~9의 값을 가지므로 지우가 내는 가위바위보 순서는 최대 9!= 362880 가지 입니다. 따라서 브루트 포스로 해결이 가능합니다. 시행착오 처음에 문제에서 자신이 참여할 20경기에서 낼 손동작 수가 주어진다고 하여 각 사람이 참여하는 경우에만 각 사람의 ...

문제링크 https://www.acmicpc.net/problem/2786 문제 풀이 하나의 음식을 A로 내고나면 나머지는 전부 B로 내야 하기 때문에 먼저 B를 기준으로 오름차순으로 정렬을 한다음 0~(i-1) 음식의 B의 합을 계산해주었습니다. 이제 앞에서 더한 i개의 B중 하나를 버리고 A의 값으로 낼 음식을 정해야 합니다. 이를 위해 두가지 경...

문제링크 https://www.acmicpc.net/problem/2146 문제 풀이 섬과 섬의 구분을 위해 각 섬에서 bfs를 이용해 넘버링을 해주었습니다. 모든 섬에 대해 다시 bfs를 실행해 다른 섬에 도착하는 최단 거리를 측정 하였습니다. 시행착오 없었습니다. 코드 후기

문제링크 https://www.acmicpc.net/problem/2650 문제 풀이 점이 최대 50개 이므로 O(N^2)의 풀이로 풀어주었습니다. 사각형을 원으로 치환해주었습니다. 점의 각 좌표는 원의 한 기준점에서 해당 좌표까지의 거리로 치환해주었습니다. 이렇게 바꿔주었을 때 선분 ab를 기준으로 if(a<c && c<b && b<d) 인 경...

문제링크 https://www.acmicpc.net/problem/2533 문제 풀이 어떤 노드를 얼리어 답터로 지정해야 할까? => 가장 끝 노드인 리프노드부터 생각 리프 노드에 아이디어가 전파되기 위해서 리프 노드의 부모 노드는 반드시 얼리어 답터가 되어야 함 => 리프노드가 얼리어 답터가 될수도 있지만 그것보다 리프노드의 부모노드가 얼리어 답터가...

문제링크 https://www.acmicpc.net/problem/1407 문제 풀이 범위가 1 ceil(9/2) = 5개 존재합니다. 나머지 수에 대해 2 4 6 8 4로 나누어 떨어지지 않는수는 => ceil(4/2) => 2개 존재합니다. 다시 나머지 수에 대해 4 8 8로 나누어 떨어지지 않는수는 => ceil(2/2) => 1개 존재합니...

문제링크 https://www.acmicpc.net/problem/1670 문제 풀이 어느 한 사람을 기준으로 잡고 각 사람들과 악수하는 경우를 나눠서 생각해보자. 1. 시계방향으로 한 칸 떨어진 사람과 악수하는 경우 직선을 기준으로 두영역으로 나누어 지는데 한쪽 영역은 사람이 0명이고 다른쪽은 6명이다. 경우의 수 : dp[0] x dp[6] 2. ...

문제링크 https://www.acmicpc.net/problem/14391 문제 풀이 재귀로 모든 경우를 탐색하며 해결했다. 각 위치에서 아래쪽으로 뻗는 경우와 오른쪽으로 뻗는 경우 두가지 경우에 대해 값을 탐색하였다. 시행착오 2중 반복문 안쪽에 재귀 진입하도록 작성했다가 시간 초과가 나서 다시 생각하고 더 효율적으로 재작성 하였다. 코드 후기 ...

문제링크 https://www.acmicpc.net/problem/1565 문제 풀이 D에 있는 모든 수의 배수 이면서 M에 있는 모든 수의 약수인 수를 구하면 되므로 먼저 D의 최소공배수와 M의 최대공약수를 구해주었다. 최대공약수의 모든 약수는 M에 있는 모든 수의 약수가 되므로 결국 M의 최대공약수의 약수인 수 중에서 D의 최소공배수의 배수인 수를 ...

문제링크 https://www.acmicpc.net/problem/1071 문제 풀이 배열을 오름차순으로 정렬시켜준다. v[i]+1 == v[i+1] 인 경우 auto it = lower_bound로 v[i]+2가 존재한다면 위치를 찾아준다. v[i]+2가 존재한다면 v[i]와 v[i+2] 의 위치를 바꿔준다. it가 v.end()라면 v[i]+2가 존재...

문제링크 https://www.acmicpc.net/problem/16971 문제 풀이 배열 B의 배열의 값을 위해 배열 A의 원소가 몇번 사용되는지를 카운트 해주었다. 이 표를 통해 배열 A의 중간에 있는 행 또는 열끼리는 아무리 교환하더라도 배열 B의 배열의 값은 변하지 않는것을 확인할 수 있다. 따라서 배열 A의 첫번째 or 마지막 행열과 두번째~...

문제링크 https://www.acmicpc.net/submit/20440/28843659 문제 풀이 벡터에 시작시간과 끝시간을 모두 push 한 후 시작시간을 기준으로 오름차순으로 정렬한다. 끝나는 시간을 기준으로 먼저 끝나는것이 높은 우선순위를 가지도록 우선순위 큐를 선언한다. 벡터원소의 시작시간이 top() 원소의 끝나는 시간보다 작아질때까지 pop...

문제링크 https://www.acmicpc.net/problem/3980 문제 풀이 최대 5개의 포지션에 배치가 가능하다는 조건을 보고 백트래킹으로 전부 탐색하며 풀 수 있을것이라 생각하였다. 자세한 풀이는 코드 참조 시행착오 개행문자 생략으로 인한 오답제출 코드 후기 백트래킹의 기본적인 형태

문제링크 https://www.acmicpc.net/problem/2268 문제 풀이 기본적인 세그먼트 트리 문제이다. 시행착오 if (bb < cc) cout << sum(tree, 1, 1, n, bb, cc) << '\n'; else cout << sum(tree, 1, 1, n, cc, bb) << '\n'; sum 호출시에 left < ...

문제링크 https://www.acmicpc.net/problem/2230 문제 풀이 이분탐색을 이용하여 풀었다. (다른 풀이를 보니 투 포인터로 좀 더 간단히 풀린다.) 먼저 정렬 후 배열의 첫 원소를 기준으로 잡는다. 기준 원소보다 큰 원소들에 대해 이분 탐색으로 기준원소와의 차이가 m 이상이면서 그 크기가 가장 작은 원소를 찾아준다. 기준 원소와의...

문제링크 https://www.acmicpc.net/problem/5373 문제 풀이 그냥 무식하게 구현했다. 코드 후기 이런 문제 나오면 시간안에 풀 수 있을지 모르겠다.

문제링크 https://www.acmicpc.net/problem/20010 문제 풀이 크루스칼 알고리즘을 통해 최소신장 트리 만들기 최소신장 트리를 만들면서 최소 신장트리의 연결정보를 linked 배열에 저장 최소신장트리 완성 후 마을 간 연결 정보 중에서 가장 큰 비용을 구하기 위해 dfs를 통해 linked 배열을 탐색 dfs 탐색시 각 단말노드를...

문제링크 https://www.acmicpc.net/problem/10993 문제 시행착오 재귀를 통한 별찍기 문제 오른쪽 맨 끝에 있는 별 뒤에 공백 출력으로 인한 오답제출 처음에 삼각형의 크기를 미리 계산한 뒤에 풀이를 하였으나 n 에 따른 삼각형의 크기는 row = pow(2,n+1)-3; col = pow(2,n)-1; 로 계산할 수 있어 좀 ...

문제링크 https://www.acmicpc.net/problem/10096 문제 풀이 n%2==0 이라면 NOT POSSIBLE n이 홀수라면 문자열 s의 길이 l = n/2 **문자열을 나누어서 비교한다 ** fir = 0 ~ (l-1) , sec = l ~ (n-1) fir = 0 ~ l , sec = (l+1) ~ (n-1) 두가지...

문제링크 https://www.acmicpc.net/problem/16988 문제 풀이 모든 경우의 수를 생각하여 bfs를 돌려주며 풀었다. 크게 해야하는 작업은 다음의 두가지 이다. 내 돌을 놓은 두 자리를 찾아서 돌을 놓아보기 백트래킹과 next_permutation 알고리즘을 이용하여 놓을 두 자리를 골라낼 수 있다. 아래 코드에서는 n...

문제링크 https://www.acmicpc.net/problem/11779 문제 풀이 기본적인 다익스트라 + 경로찾기 문제 비용은 우선순위큐를 이용한 다익스트라 알고리즘으로 구해주었다. 경로찾기는 int route[1001] 배열을 두어 다익스트라 알고리즘에서 dist 갱신시 route 배열에 해당 정점이 어떤 정점으로 부터 왔는지에 대한 기록도 갱신...

문제링크 https://www.acmicpc.net/problem/11437 문제 코드 후기 LCA알고리즘은 처음 접해봐서 공부하며 풀었다. https://seongjuk.tistory.com/entry/BOJ-%EB%B0%B1%EC%A4%80-11437%EB%B2%88-LCA https://www.crocus.co.kr/660#recentComm...

문제링크 https://www.acmicpc.net/problem/17299 문제 풀이 각 숫자가 몇번 등장하는지 cnt 배열을 통해 카운트를 해준다. for문을 통해 arr 배열의 뒤에 있는 숫자부터 접근을 한다. 먼저 배열의 가장 뒤에있는 숫자를 스택에 담아준다. 이후에는 반복문을 돌며 스택에 있는 숫자중 현재 배열에 있는 숫자보다 등장 횟수가 적...

문제링크 https://www.acmicpc.net/problem/2339 문제 풀이 분할정복 + 구현력이 필요한 문제이다. for 문으로 map을 돌면서 불순물이 있는 인덱스에서 분할정복으로 가로와 세로로 잘라가면서 풀어주었다. 이때 자르는 방법은 따로 인덱스에 표시하지 않고 자른 석판의 왼쪽 위, 오른쪽 아래 좌표를 넘기며 불순물이 섞여 있는지 체...

문제링크 https://www.acmicpc.net/problem/1167 문제 풀이 처음에는 그냥 모든 단말노드에서 DFS를 돌려주어 트리의 지름을 찾으려 했다. 정점의 개수가 2<=V<=100000이니 당연히 시간 초과가 났다. DP로 접근하려고도 생각해 보았는데 저 범위에서는 어차피 메모리 초과가 날것이므로 따로 시도는 안했다. 고민하던중 .. 임의...

문제링크 https://www.acmicpc.net/problem/14003 문제 풀이 가장 긴 증가하는 부분 수열 O(NlogN) + 경로추적 문제 기존의 LIS O(NlogN) 풀이에서 한 가지를 더 생각하면 된다. **값을 교체할 때 해당 index에서 가장 긴 증가하는 부분 수열의 길이 dp[i] = distance(v.begin(),arr[i...

문제링크 https://www.acmicpc.net/problem/20924 문제 풀이 두 번의 dfs를 이용해 풀이했다. 첫 번째 dfs에서 기둥의 길이와 기가 노드를 찾아주었다. 두 번째 dfs의 시작점을 기가 노드로 지정하여 가장 긴 가지를 찾아주었다. 방문한 노드는 visit 배열을 통해 표시하여 두 번째 dfs 실행 시 기둥 노드에 방문하지 않...

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42587 문제 풀이 문제의 프린터가 작동하는 흐름 그대로 짰다. 벡터의 맨 앞 요소를 뽑아냄 우선순위가 더 높은 요소가 뒤에 있으면 벡터의 뒤에 push (algorithm 헤더의 max_element를 이용하면 간단하게 작성 가능) 그렇지 않으면 ord...

문제링크 https://programmers.co.kr/learn/courses/30/lessons/12899?language=cpp 문제 풀이 share가 3으로 나누어 떨어지면 4를 추가, share-- share를 3으로 나눈 나머지가 1이면 1을 추가 share를 3으로 나눈 나머지가 2이면 2를 추가 시행착오 3진수로 변환하는 과정에서 일반...

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42577 문제 풀이 해시를 이용한 풀이 1-1 phonebook을 정렬 1-2 단, 해시에 삽입하기 전에 문자를 하나씩 더해 문자열을 만들어가며 접두어가 존재하는지 확인 1-3 접두어가 존재하지 않으면 해시에 삽입 간단하나 시간복잡도 측면에서 비효율적...

문제링크 https://www.acmicpc.net/problem/16964 문제 풀이 주어진 dfs방문 순서에 따라 방문 우선순위 정하기. 이를 기준으로 sort정렬 알고리즘에 적용. 각 정점에서 인접 정점들을 정렬. ![](https://images.velog.io/im

문제링크 https://www.acmicpc.net/problem/15711 문제 풀이 S = A+B 에서 S를 두 소수의 합으로 나타낼 수 있는지 판별하는 문제이다. S가 짝수인 경우 : 1-1 S가 2라면 두 소수의 합으로 나타낼 수 없다. 1-2 S가 2가 아니라면 골드바흐의 추측에 의해 두 소수의 합으로 나타낼 수 있다. S가 홀수인 경...

문제링크 https://www.acmicpc.net/problem/7576 문제 풀이 유명한 bfs 알고리즘 문제인 토마토 이다. 문제가 워낙 유명하기에 깔끔하게 코딩하는것에만 신경써서 풀었다. 코딩하는 과정에서 핵심은 days count 를 위한 방법 ( sz 변수를 이용해 특정 시점의 큐의 크기를 저장) dx[4],dy[4] , 반복문을 이용한 ...

문제링크 https://www.acmicpc.net/problem/1194 문제 풀이 BFS + 비트마스킹 문제이다. 문제의 핵심은 다음과 같다. 1. 비트마스킹을 이용한 열쇠 보유 여부 체크 열쇠를 가지고 있는지 여부에 따라 방문이 가능한지 결정되기 때문에 비트마스킹을 통해 열쇠를 가지고 있는지 체크해 주었다. ex 1 ) 열쇠 얻기 현재 a...

문제링크 https://www.acmicpc.net/problem/1041 문제 풀이 백트래킹을 이용해 조합을 구해주었다. 그리고 해당 조합에서 최소의 값을 갖는 경우를 반환해 주었다. **주사위에서 1개의 면만 보일때 최소의 값 **=> 6C1 을 탐색하며 최소의 값을 반환 **주사위에서 2개의 면만 보일때 최소의 값 **=> 6C2 를 탐색하며 ...

문제링크 https://www.acmicpc.net/problem/11780 문제 풀이 플로이드 와샬 + 경로추적 문제이다. 먼저 경로를 저장할 2차원 벡터 배열을 선언한다. 그리고 플로이드 와샬 알고리즘 수행 중 mapsi+mapsk<mapsi 인 상황에서 값이 갱신 될 때, 경로도 함깨 갱신 되도록 했다. 경로는 routei : routei 경로...

문제링크 https://www.acmicpc.net/problem/1744 문제 풀이 양수와 음수를 나누어서 두 배열에 저장한다. 양수 배열에서 최대가 되기 위해서는 가장 큰 수를 두개씩 묶어가며 곱해야 한다. 즉, 1 2 3 4 5 가있다면 5 x 4 + 3 x 2 + 1 = 27 처럼 되어야 한다. 양수 배열의 길이가 짝수이고 가장 작은 수가 1인 경...

문제링크 https://programmers.co.kr/learn/courses/30/lessons/81301?language=cpp 문제 풀이 구현 문자열을 한글자씩 돌면서 숫자인 경우는 ans에 그대로 합쳐주고 알파벳인 경우는 while문을 이용해 zero~nine 이 완성될때까지 temp 변수에 저장한다. zero~nine이 완성되고 나면 ans에...

문제링크 https://www.acmicpc.net/problem/14500 문제 풀이 맵 크기가 500*500 이고 블록의 모든 경우의 수는 19가지 이므로 dfs를 이용해 완전 탐색을 하더라도 시간초과가 나지 않는다. 단, dfs로는 ㅏ ㅓ ㅗ ㅜ 모양은 탐색할

문제링크 https://www.acmicpc.net/problem/2887 문제 풀이 **어차피 두 행성간 거리는 min(Xa-Xb,Ya-Yb,Za-Zb) 이기 때문에 먼저 정렬 시킨 후 인접한 점들만 비교해주면 된다.** 따라서 x y z 값들을 각각 x벡터, y벡터, z벡터에 나눠담고 각 벡터를 정렬시켜주었다. 그 후에 인접한 값들의 차(거리)를 ...

핵심은 점을 포함하고 있는지 판단하는 함수의 구현 출발점과 도착점을 모두 포함하거나 둘다 포함하지 않는다면 우회해서 피할 수 있는 원들이기 때문에 카운트하지 않는다. 반면 둘중 하나의 점을 포함한다면 반드시 거쳐야 하는 원이므로 카운트 값을 하나 늘려준다 즉, 판별은 와 같은 코드로 할 수 있다.

내 pc에서는 밑의 환경에서 입력.txt라는 파일을 생성해 입력값을 받고, 제출할때는 위의 식으로 제출하면 된다. 또, 입력을 받을때는 split 과 map, destructuring 을 적절히 활용하면 훨씬 간편하게 입력을 받을 수 있다. ex)

카테고리 별로 map에 담아주었다. 이어서 각 카테고리별 길이를 통해 전체 경우의 수를 구해주었다. 여기서 경우의 수는 소인수분해 후 약수 개수를 구하는 방법을 생각하고 풀었다. ex) 12 = 2^2 * 3 => 약수 개수는 (2+1)x(1+1) = 6개 다만 이 문제에서는 아무것도 고르지 않는 경우는 없으므로 최종 결과에서 1을 빼주었다.