문제 설명https://www.acmicpc.net/problem/9663 성능 요약메모리: 14468 KB, 시간: 6084 ms 분류백트래킹, 브루트포스 알고리즘 문제 설명N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. (1 ≤ N 출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 문제 풀이보드가 이차원 배열이기 때문에 배열을 받을 때 2차원 배열로 해도 되지만, 1차원 배열로도 가능하다.각 원소의 index를 행이라고 생각하고, 원소값을 열이라고 생각하면 1차원 배열로도 가능하다.예를 들어, arr = [1, 3, 0..
알고리즘
백트래킹현재 상태에서 가능한 모든 선택지를 따라 들어가며 탐색하는 알고리즘 DFS와 헷갈릴 수도 있지만, 백트래킹 = DFS가 아니라 백트래킹 방법 중의 하나가 DFS인 것이다. DFS는 깊이 우선 탐색으로 모든 경우의 수를 다 탐색하지만,백트래킹은 조건에 맞지 않는다면 그 부분은 탐색하지 않고 탐색을 중지한 다음 그 이전으로 돌아가서 다른 경우를 탐색한다.연습 문제[백준`15649] N과 M (1)문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되..
문제 설명https://www.acmicpc.net/problem/2660 성능 요약메모리: 34088 KB, 시간: 56 ms분류너비 우선 탐색, 플로이드–워셜, 그래프 이론, 그래프 탐색, 최단 경로제출 일자2024년 11월 14일 19:57:54문제 설명월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면..
알고리즘 언어를 파이썬에서 자바로 바꾸기로 결정하면서입출력 받는 방법을 계속 까먹어서 정리 Scanner보다 BufferedReader가 속도가 더 빠르기 때문에속도가 중요한 코딩테스트에서는 BufferedReader 사용하기! 입력1. 한 줄에 하나씩 정수 입력 받기// 예제 입력1 2import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new..
https://www.acmicpc.net/problem/13251 문제 설명성능 요약메모리: 31120 KB, 시간: 36 ms분류조합론, 수학, 확률론제출 일자2024년 10월 7일 18:26:05문제 설명효빈이의 비밀 박스에는 조약돌이 N개 들어있다. 조약돌의 색상은 1부터 M까지 중의 하나이다.비밀 박스에서 조약돌을 랜덤하게 K개 뽑았을 때, 뽑은 조약돌이 모두 같은 색일 확률을 구하는 프로그램을 작성하시오.입력첫째 줄에 M (1 ≤ M ≤ 50)이 주어진다.둘째 줄에는 각 색상의 조약돌이 몇 개 있는지 주어진다. 각 색상의 조약돌 개수는 1보다 크거나 같고 50보다 작거나 같은 자연수이다.셋째 줄에는 K가 주어진다. (1 ≤ K ≤ N)출력첫째 줄에 뽑은 조약돌이 모두 같은 색일 확률을 출력한..
순열서로 다른 n개의 원소에서 r개를 중복 없이 선택하여 순서대로 나열선택하는 순서가 다르면 서로 다른 것 (즉, AB와 BA가 다르다)cards = ['A', 'B', 'C', 'D']k = 3visited = [False] * len(cards)answer = []def dfs(count, arr): if count == k: answer.append(arr[:]) return for i, card in enumerate(cards): if not visited[i]: arr.append(card) visited[i] = True dfs(count + 1, arr) arr.p..
문제 설명https://www.acmicpc.net/problem/3190 성능 요약메모리: 34116 KB, 시간: 104 ms분류자료 구조, 덱, 구현, 큐, 시뮬레이션제출 일자2024년 4월 28일 18:17:43문제 설명'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.먼저 뱀은 몸길이를 늘려 머리를 ..
문제 설명https://www.acmicpc.net/problem/1938 성능 요약메모리: 34216 KB, 시간: 72 ms 분류너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현 제출 일자2024년 4월 23일 00:47:02 문제 설명가로와 세로의 길이가 같은 평지에서 벌목을 한다. 그 지형은 0과 1로 나타나 있다. 1은 아직 잘려지지 않은 나무를 나타내고 0은 아무 것도 없음을 나타낸다. 다음 지형을 보자.B 0 0 1 1B 0 0 0 0B 0 0 0 01 1 0 0 0E E E 0 0위의 지형에서 길이 3인 통나무 BBB를 밀거나 회전시켜 EEE의 위치로 옮기는 작업을 하는 문제를 생각해 보자. BBB와 EEE의 위치는 임의로 주어진다. 단 문제에서 통나무의 길이는 항상 3이며 B의 개수와 ..
문제 설명 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 성능 요약 메모리: 31120 KB, 시간: 44 ms 분류 구현, 시뮬레이션 제출 일자 2024년 4월 22일 00:41:09 문제 설명 2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까? 입력 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ ..
문제 설명 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 성능 요약 메모리: 39868 KB, 시간: 1488 ms 분류 덱, 파싱, 구현, 문자열, 자료 구조 제출 일자 2024년 4월 19일 02:26:14 문제 설명 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어..
