본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 1715번 : 카드 정렬하기 www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net min heap을 사용해 푼 문제였습니다. 풀이방법 1. 카드 묶음을 입력 받고 minHeap에 push해줍니다. 2. 카드 두장을 뽑고 답 변수 ans에 더해준 다음 합쳐진 카드를 다시 minHeap에 push합니다. Code #include using namespace std; int n, card; int main(){ int ans = 0; cin >> n; priority_queue mi..
(C++) - 백준(BOJ) 1963번 : 소수경로 www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net bfs로 푼 문제였습니다. 풀이방법 1. 에라토스테네스의 체를 이용해 9999까지의 소수를 모두 구합니다. primt[index]이 0이라면 index는 소수입니다. 2. bfs 시행 : 체크가 안되어 있고 소수인 모든 수를 queue에 push합니다. push할 때는 원래 소수경로의 거리 + 1을 다음 수의 check배열에 저장해줍니다. string으로 수를 변환하면 코드를 더 깔끔하게 할 수 있습니다. 이 후 한 번..
(C++) - 백준(BOJ) 12886번 : 돌 그룹 www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net bfs로 푼 문제였습니다. 풀이방법 1. 두 그룹씩 선택하는 방식이 6가지입니다. 2. 이 6가지에 대해 bfs를 수행하면 됩니다. Code #include using namespace std; int ck[2001][2001]; int bfs(int a,int b, int c){ queue q; q.push({a,b,c}); ck[a][b] = 1; ck[b][a] = 1; ck[a][c] = 1; ck[..
(C++) - 백준(BOJ) 17609번 : 회문 www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 재쉬를 이용해 푼 문제였습니다. 풀이방법 1. 분류기 함수를 만듭니다. 펠린드롬이면 0, 유사 펠린드롬이면 1, 이외의 경우엔 2를 반환하는 함수입니다. 2. 유사 펠린드롬인지 확인합니다 : left, right번째 문자를 확인하며 펠린드롬 여부를 결정합니다. left번째 right번째 문자열이 같다면 left +1, right -1 문자를 확인합니다. 아닌 경우 : 지울 문자열을 선택합니다. left번째 문자를 지우거나 right번째 문자..
(C++) - 백준(BOJ) 16953번 : A → B www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net bfs 문제였습니다. 풀이방법 1. 원하는 수 b에 도착했을 때 지나온 길을 세주기 위해 queue를 pair로 선언합니다. 이 때 int 범위를 *10 + 1 연산을 하거나 *2를 했을 때 초과할 수 있으므로 long long자료형으로 선언하도록 합니다. 2. bfs를 실행합니다. 매번 pop을 하여 횟수와 값을 봅니다. x*2 b; cout
(C++) - 백준(BOJ) 18352번 : 특정 거리의 도시 찾기 www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 기본 다익스트라 문제였습니다. 풀이방법 1. 입력 및 초기화 : 단방향 그래프입니다. 도시 u,v가 있을 때 u -> v로 간다면 가중치가 1이라고 생각합니다. 또한 최단거리를 구해야 하므로 dist배열을 선언한뒤 n까지의 도시까지 나올 수 없는 큰 값으로 초기화해줍니다. * 도시의 번호가 1부터 시작하므로 index와 헷갈리지 않도록 잘..
(C++) - 백준(BOJ) 1926번 : 수 정렬하기 5 www.acmicpc.net/problem/15688 15688번: 수 정렬하기 5 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이며, 같은 수가 여러 번 중복될 수도 있다. www.acmicpc.net counting sort를 사용하는 문제였습니다. 풀이방법 1. 입력받은 수를 세줍니다. x라는 수의 개수는 num이라는 배열의 x번째 index의 값이 됩니다. *음수 입력이 들어올 수 있으니 index를 100만만큼 더한 후 해당 index 값을 1씩 증가하도록 합니다. 이런식으로 입력이 들어왔다고 가정했을 때 배열의 index로는 음수를 표현할 수 없으므로 오른쪽으로 100..
(C++) - 백준(BOJ) 1926번 : 그림 www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net bfs문제였습니다. 풀이방법 인접한 그림들은 모두 그림 하나의 일부입니다. 방문하지 않은 곳, 그림이 칠해져있는(1인) 곳에 대해 bfs를 실행합니다. 이 때, bfs가 호출되는 수가 곧 영역의 개수가 됩니다. 또한 bfs함수가 호출된 후 실행시 한 영역에 대해 1의 개수를 센 후 반환합니다. 이 때 반환값이 곧 한 영역의 그림 넓이가 됩니다. Code #include using namespace std; using..

티스토리툴바