본문 바로가기

C++105

[C++] 백준 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 문제 풀이 1. 능력치를 나타내는 2차원 배열 board에 값을 입력받고 팀원의 소속을 나타내는 배열 team을 초기화해준다. 2. 입력받은 총 인원 n의 반만큼 set_teams로 팀을 나누어주고 맞게 떨어진다면 함수 get_ability_of_team을 호출한다. 3. 함수 get_ability_of_team으로 나눠진 두 팀의 능력치를 연산하고, 뺀 값을 반환한다. 중복 없이 n의 반의 크기인 팀을 나누는 함수... 2021. 5. 26.
[C++] 백준 14888번 : 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 풀이 1. 피연산자와 연산자의 개수를 배열에 담는다. 2. 연산자를 끼워넣는 함수를 실행한다. 함수 getans는 변수 cnt(피연산자의 index)와 변수 result(연산 결과)를 매개변수로 가진다. 변수 cnt 가 n의 값과 일치하면 최대, 최소를 비교하여 값을 최신화한다. 피연산자의 순서는 고정이 되어있기 때문에 다음에 올 연산자.. 2021. 5. 26.
[C++] 백준 2580번 : 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 풀이 스도쿠의 특성상 전체 행, 열 그리고 9 분할된 3x3 박스 모두 값이 겹치지 않는지 확인해야 한다. 이 부분은 함수로 구현해서 따진다. 3x3 박스 영역은 입력받은 좌표를 3으로 나눈 값으로 따질 수 있다. 이후 1~9까지 값들을 빈 영역에다가 대입해보고 구현한 함수로 중복 여부를 따져본다. 중복이 없다면 다시 호출한다. 계속 값을 차례차례 확인하고 넘어가도 어떤 특정 좌표에서 어떤 .. 2021. 5. 24.
[C++] 백준 9663번 : N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 같은 열, 행, 그리고 대각선에 위치하면 안 되기 때문에 함수로 위치할 수 있는지 체크한다. 좌표에 놓여있을 때, (A, B)와 (X, Y)가 같은 대각선 상에 위치한다면 A - X = B - Y이다. 그리고 col 배열의 값은 x 축, col 배열의 인덱스는 y축을 나타내는 점을 이용해서 배열에 값이 입력됐다면 해당 인덱스에 값이 위치할 수 있는지 여부를 함수로 체크하고 재귀 함수를 다시 불러온다. .. 2021. 5. 24.
[C++] 백준 17103번 : 골드바흐 파티션 https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 문제 풀이 에라토스테네스의 체를 이용해서 소수들을 정의하고 2부터 입력받은 값(N)의 반까지 경우를 모두 따진다. 느낀 점 예전의 소수 문제들과 비슷해서 바로 풀어봤는데 그 당시에는 시간제한이 널널해서 에라토스테네스의 체를 사용하지 않았는데 이번엔 0.5초 제한으로 안 쓸 수가 없었다. 이번 기회로 알고리즘을 다시 정리한 계기가 되었다. 에라토스테네스의 체 시간복잡도 : O(NloglogN) / 2.. 2021. 5. 24.
[C++] 프로그래머스 : 소수 만들기 (LvL 1) https://programmers.co.kr/learn/courses/30/lessons/12977 코딩테스트 연습 - 소수 만들기 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 programmers.co.kr 문제 풀이 입력받은 값들 중 3개만 뽑아서 더해서 소수인지 따지고 소수가 맞다면 리턴할 값에 1을 더한다. isPrime로 소수를 따지는데 1 이하의 경우는 제외하고, 2 이상의 숫자만 따진다. 어떤 숫자의 루트 값은 중간값이 되기 때문에 2부터 √N만 따져도 이후 값은 확인할 필요가 없기 때문에 i × i > num; v.push_back(.. 2021. 5. 24.

티스토리툴바