profile
안녕하세요.
post-thumbnail

백준 11779 최소비용 구하기 2

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

약 8시간 전
·
0개의 댓글
post-thumbnail

백준 16988

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

2일 전
·
0개의 댓글
post-thumbnail

10096 세 친구

문제링크 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) 두가지...

6일 전
·
0개의 댓글
post-thumbnail

백준 10993

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

2021년 5월 7일
·
0개의 댓글
post-thumbnail

백준 20010 악덕 영주 혜유

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

2021년 5월 6일
·
0개의 댓글
post-thumbnail

백준 5373 큐빙

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

2021년 5월 6일
·
0개의 댓글
post-thumbnail

백준 2230 수 고르기

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

2021년 5월 4일
·
0개의 댓글
post-thumbnail

백준 2268 수들의 합

문제링크 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 < ...

2021년 4월 30일
·
0개의 댓글
post-thumbnail

백준 3980 선발명단

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

2021년 4월 30일
·
0개의 댓글

백준 20440

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

2021년 4월 30일
·
0개의 댓글
post-thumbnail

백준 16971 배열 B의 값

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

2021년 4월 26일
·
0개의 댓글
post-thumbnail

백준 1071 소트

문제링크 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가 존재...

2021년 4월 17일
·
0개의 댓글
post-thumbnail

백준 1565 수학

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

2021년 4월 16일
·
0개의 댓글
post-thumbnail

백준 14391

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

2021년 4월 15일
·
0개의 댓글
post-thumbnail

백준 1670 정상회담2

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

2021년 4월 14일
·
0개의 댓글
post-thumbnail

백준 1407 2로 몇 번 나누어질까

문제링크 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개 존재합니...

2021년 4월 14일
·
0개의 댓글
post-thumbnail

백준 2533 사회망 서비스

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

2021년 4월 13일
·
0개의 댓글
post-thumbnail

백준 2650 교차점 개수

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

2021년 4월 12일
·
0개의 댓글
post-thumbnail

백준 2146 다리만들기

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

2021년 4월 12일
·
0개의 댓글
post-thumbnail

백준 2786 상근이의 레스토랑

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

2021년 4월 10일
·
0개의 댓글