본문 바로가기

알고리즘

 (26)
백준 14889 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 총인원은 최대 20명이고(짝수만가능) 스타트팀, 링크팀 구성은 동일하게 구성된다. 각 멤버들이 같은팀일경우 해당되는 능력치가 2차원 배열로 주어지며 공정한 경기를 위해 두팀간의 능력치의 차이가 최소가 되도록 팀을 구성해야 한다. 그리고 그 최소값을 출력해야 한다. 따져야 하는 경우의 수는 모두 몇가지 일까? 이것은 중복 집한 순열의 개수를 구하는 것과 같다. 예를 들어 집합 { 1,2,3,4,5,6 } 으로 가능한 모..
백준 14888 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 본문제에 대한 풀이의 해법에 대한 힌트는 덧셈, 뻴셈, 곱셈, 나눗셈의 개수가 입력으로 주어진다는 것이다. 따라서 각 연산을 매핑할 숫자로 define 하고 개수가 정해져있기 때문에 N-1 개짜리 배열을 만들 수 있고 이숫자 배열의 가능한 모든 조합들을 순회해 가면서 최대 결과값을 업데이트 하도록 구현하면 된다. 예를들어 연산자 개수가 2 1..
백준 1339 단어수학 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 본문제는 N개의 단어(최대 10개) 의 합을 단어를 구성하는 알파벳을 어떤숫자로 매칭하였을 때 최대값이 되는지 구해야 하는 문제이다. 그런데 나열된 알파벳의 총 가지수가 10개를 넘어가지않고 두개이상의 알파벳이 같은 숫자와 매핑되지도 않기 때문에 부르트 포스로 도전해 볼 만하다. 예를들어 단어에 나열된 알파벳이 A B C D E F G H I J 이라면 0 1 2 3 4 5 6 7 8 9 로..
백준 2529 부등호 2529번: 부등호 (acmicpc.net) 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제 www.acmicpc.net 본 문제의 핵심은 등호가 N 개일 때 조건을 만족하는 N+1 의 숫자는 최소값은 0~N 까지 구성되고 최대값은 9~ (9-N) 까지로 구성된다는 것이다. 예를들면 부등식이 > 이라면 9,8,7,6 의 조합으로 최대값이 결정된다는 것이다. 최대값 도출은 다음과 같은 계산을 하면 된다. 1) 첫자리에 9를 제일 먼저넣어본다 : 9 7 > 6 좀더 쳬계적으로 생각해보면 9,8,7,6 으로 이루어진 순열 중 큰 순으로 나열하여 하나..
백준 11725 - 트리의 부모찾기 www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 본 문제의 분류는 트리이지만 그래프에 대한 자료주고를 만들고 탐색할 수 있어야 해결이 가능하다. 연결된 두 노드간 부모 자식이 누구인지 정보가 주어지지 않기 때문이다. 따라서 최초 자료구조를 만들때에는 그래프 처럼 만들어야 한다. 루트 노드가 주어졌기 때문에 BFS 순회를 하면서 부모와 자식 관계를 업데이트 한 후 순서대로 출력하면 된다. 다만 주의해야할점은 cin , cout 으로입출력을 하면 성능상 시간 초과가 발생하니 scanf 와 printf 를 사용하여야 한다. 구..
백준 1991 - 트리순회 www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 트리의 자료구조를 잘 만드는 것이 중요한데 N * 3 의 배열로 구성한다. 각 노드별 row 를 의미하고 각 row 별로 첫번째가 부모 , 두번째가 왼쪽자식, 세번째가 오른쪽 자식을 나타내게 표현한다. 불필요한 연산을 하지 않기 위해 배열크기(N) 을 'Z' + 1 이 되게 하여 알파벳 char 로 바로 해당 위치의노드를 참조할수 있도록 구성한다. 각 순회는 재귀 호출을 통해 구현할 수 있다. 구현된 코드..
백준 - 2606 바이러스 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net 본 문제는 BFS 를 통해 첫번째 노드와 인접한 모든 노드들을 세면 되는 간단한 문제 이다. 코드는 아래와 같다. #include #include #include using namespace std; int main() { int nrNode, nrEdge; cin >> nrNode >> nrEdge; vector nw(nrNode + 1, vector(nrNode + 1, 0)); int t1, t2; for (int i = 0; i < nrEdge; i++) ..
백준 - 1697 숨바꼭질 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 본 문제는 출발지에서 도착지 까지 갈수 있는 방법 ( +1, -1, *2 ) 을 각각 계산하여 BFS 방식으로 반복하여 목적지에 도달하는데 걸리는 시간을 산출할 수 있다. 알고리즘은 다음과 같다. 1. 현재위치를 시작위치로 잡고 현재 위치를 큐에 넣는다. 2. 큐에서 한 지점을 꺼내 현재 위치로 설정한다. 3. 해당 지점이 방문되지 않았다면 현재위치에서 +1 지점을 큐에 넣는다...

티스토리툴바