0. 문제 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 1. 문제 이해 4가지 방향으로 같은 색의 돌을 센다. 단, 같은 방향이면 한 번만 센다. 돌이 5개 있으면 … 가장 왼쪽에 있는 돌을 출력. 세로로 돌이 위치하면 가장 위에 있는 돌 출력. 2. 제출 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class M..

종류 설명 기호 시간복잡도 순열 N개의 원소 중 R개의 원소로 순서를 가진 부분집합을 만드는 경우의 수 nPr O(N!) 조합 N개의 원소 중 R개의 원소로 부분집합을 만드는 경우의 수 nCr O(n! / (r! x (n-r)!)) 부분집합 N개의 원소로 부분집합을 만드는 모든 경우의 수 nHr O(2^N) 1. 순열 가. 반복문 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Permutation { static int N, R=3; static int[] m..

15650. N과 M (2) 재귀함수를 사용해서 조합 구현. 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15652. N과 M (4) 재귀함수를 사용해서 조합 구현. (비내림차순, 중복 가능) 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 6603. 로또 조합 6603번: 로또 입력은 여러 개의 테스트 케이스..

17478. 재귀함수가 뭔가요? 재귀함수 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 1208. Flatten 완전탐색 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1210. Ladder1 완전탐색 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2805. 농작물 수확하기 완전탐색 SW Expert Academy S..

0. 문제 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1. 문제 이해 2개의 돌을 뺄 수 없다는 조건 때문에 수학적 규칙을 찾기 어려웠다. N=1000이고 제한시간은 1초다. 1초를 1억으로 가정하면 시간복잡도는 O(n^2)쯤이다. 모든 경우의 수를 다 구해서 풀면 O(n^3)이다. DP로 풀어야 한다. 상근이가 이기는지 지는지 알아내는 방법은 다음과 같다. 돌의 개수가 1 ~ 5까지는 비교적 쉽게 구할 수 있다. 돌의 개수가 6일 때는 6에서 1, 3, 4개를 빼본다. 6 - 1 = 5, 6 - 3 = 3 그리고 6 - 4 = 2에서 단 한 번이라도 상근이가 이기면 6에서도 상근이가 이긴다. (= 모든 경우에서 창영이가..

1. 입력 입력 속도 비교 여러가지 언어와 입력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다. 방법: 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일 www.acmicpc.net 가. Scanner import java.util.Scanner; public class Test1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); String[] foods = new String[num]; for(int i=0; i

0. 문제  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 1. 문제 이해 최장 증가 부분 수열에 관한 문제이다. 별다른 접근 방법이 생각나지 않기 때문에 모든 경우의 수를 실행하고 그 결괏값을 비교하기로 했다. a1, a2, a3, a4, a5, …, an 수열이 주어진다면 수열의 크기는 n이다. 수열에서 파생될 수 있는 순서가 바뀌지 않는 모든 부분 순열은 수는 2^n이다. 2. 시간 초과import java.io.*;import java.util.StringTokenizer;class Solution { static int n; static int ret; public static void ..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 메모리 bit 중 하나를 골라 0인지 1인지 결정하면 해당 값이 메모리의 끝까지 덮어씌우는 것이다. 예를 들어 지금 메모리 값이 0100이고, 3번째 bit를 골라 1로 설정하면 0111이 된다. 원래 상태가 주어질 때 초기화 상태 (모든 bit가 0) 에서 원래 상태로 돌아가는데 최소 몇 번이나 고쳐야 하는지 계산해 보자. 1. C++ #include #include #include using namespace std; int solve(vector& input){ int cnt = 0; char before = '0'; for(int i = 0; i..