본문 바로가기

전체 글

 (45)
백준 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 지점을 큐에 넣는다...
백준 - 2667 단지 번호 붙이기 www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 본문제는 전형적인 섬찾기 알고리즘 문제이며 bfs 를 반복하면서 답을 쉽게 찾을 수 있다. 문제의 전략은 아래와 같다. 1. 맵의 시작부터 각각 순회 하면서 방문하지 않은 곳을 선택한다. 2. 선택된 위치에서 bfs 로 방문하면서 방문한 총 가구수를 계산한다. 3. 모든 가구를 순회하면서 1~2단계를 반복한다. 4. 계산된 각각의 숫자들의 개수와 숫자들을 오름차순 정렬하여 출력한다. 구현된 코드는 아래와 같다...

티스토리툴바