문제 풀이262 [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. [C++] 백준 15652번 : N과 M (4) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 N과 M(2) 번과 (3) 번을 섞은 듯한 문제이다. 재귀 호출을 할 때 이전 기준값을 시작점으로 삼으면 이전 배열 값보다 크거나 같은 값을 출력할 수 있다. 느낀 점 실은 이번 코드도 (2)번에서 한 것처럼 조건문으로 경우를 따져서 값을 대입하는 방식으로 했었다. 채점 이후 더 나은 방법이 없을까 고민하다가 (2) 번 문제처럼 시작점을 따지는 방법으로 넘어갔다. 코드 길이가 확연히 .. 2021. 5. 24. 이전 1 ··· 35 36 37 38 39 40 41 ··· 44 다음