본문 바로가기

전체 글

 (351)
[BOJ] 9663. N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 체스판 위의 퀸은 같은 열과 행에 두개의 퀸이 존재할 수 없고, 왼쪽 및 오른쪽 대각선에 다른 퀸이 존재하는 경우가 되면 안된다. - 2차원 배열을 이용할 경우, 퀸을 놓은 자리를 기준으로 열과 행, 대각선의 값을 1로 처리하고 방문기록도 체크한다. -> 2차원 배열을 사용하면 시간복잡도가 엄청나게 커짐. - 열을 기준으로 한 리스트를 만들고 리스트 열 값에 퀸이 위치한 행..
[BOJ] 1012. 유기농 배추 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - BFS를 돌면서 배추가 심어진, 즉 그래프 상에서 1로 연결된 지점을 돌면서 끝나면 +1을 해준다. - 방문기록을 체크하면서 이중 for문을 돈다. 2. 시간복잡도 - O(V + E) 3. 자료구조 - BFS - 2중 for문 """ 2. 정답코드 입력 예제(1) 2 10 8 17 0 0 1 0 1 1 4 2 4 3 4 5 2 4 3 4 7 4 8 4 9 4 7 5 8 ..
[BOJ] 6603. 로또 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 집합 S 원소 중에서 6개를 선택한 모든 경우의 수를 출력해야함. - while문을 돌려서 입력 리스트를 받고 0이 입력되면 break - 백트래킹을 이용해서 6개의 원소가 되도록 모든 경우의 수를 구함 2. 시간복잡도 - O(2^k * (k - 6)) 3. 자료구조 - 백트래킹 : 재귀 """ 2. 정답코드 입력 예제(1) 7 1 2 3 4 5 ..
[BOJ] 1182. 부분수열의 합 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 입력받은 정수 S가 되기 위해 모든 경우의 수를 구함. - 원소 하나씩 추가시키는 재귀랑 추가시키지 않는 재귀 두개를 구현해서 모든 경우의 수를 확인. - 결과 리스트에 들어간 원소 값의 합들이 S가 되면 종료, print 2. 시간복잡도 - O(2^N) 3. 자료구조 - 백트래킹 : 재귀 """ 2. 정답코드 입력 예제(..
[BOJ] 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. 해결방법 """ 1. 아이디어 - 각 팀을 n // 2로 나누어서 처리한다. - 2중 for문을 사용해서 선수를 추출한다. 방문기록 체크 - 먼저 Start Team을 n // 2만큼 append하고, 재귀 종료 지점으로 이동한다. - Start Team에 append된 팀을 제외한 나머지 팀을 Link Team에 append 한다. - 각 팀의 시너지 합을 구하고 최소값이 되도록 비교한다. 2. 시간복잡도 - ..
[BOJ] 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. 해결방법 """ 1. 아이디어 - 입력 받은 연산자를 리스트로 넣고 각 연산자의 수 만큼 재귀 - 재귀에서 n개를 선택 후 연산 결과가 크커나 작으면 변수 값 변경 한 다음 종료, print - 백트래킹 for문을 돌면서 입력 숫자 원소와 연산자를 순차적으로 선책해서 모든 경우의 수를 연산 2. 시간복잡도 - O(N) 3. 자료구조 - ..
[리눅스] 24. 첫 번째 쉘 스크립트 1. 쉘 스크립트 쉘 스크립트란 ? 쉘 스크립트는 명령어들이 나열되어 있는 파일이다. 쉘은 이 파일을 읽어서 마치 커맨드라인에 직접 명령어를 입력하여 실행하는 것처럼 수행한다. 2. 쉘 스크립트 작성 방법 1. 스크림트 작성하기. 쉘 스크립트는 일반적인 텍스트 파일이다. 따라서 텍스트 편집기가 필요하다. 2. 스크립트를 실행파일로 설정하기. 시스템은 여러 이류들로 예전 텍스트 파일들을 프로그램으로 처리하지 않는다. 따라서 스크립트 파일에 실행 권한을 주어야 한다. 3. 쉘이 접근할 수 있는 장소에 저장하기. 쉘은 경로명이 명시되어 있지 않아도 실행 가능한 파일들이 존재하는 특정 디렉토리를 자동으로 검색한다. ! 스크립트 파일 포맥 ! 간단한 예를 만들어 볼 것이다. "hello world" 프로그램을 작..
[리눅스] 23. 프로그램 컴파일 1. 컴파일링이란? 소스 코드(프로그래머에 의해 작성된, 사람이 읽을 수 있는 형태의 프로그램 서술)를 컴퓨터 프로세서의 언어로 번역하는 절차이다. 컴퓨터 프로세서(또는 CPU)는 기본적인 단게에서 동작을 하는데, 이 것을 기계어로 프로그램들을 실행하는 것이다. 기계어는 "바이트 더하기", "메모리 위치 가리키기" , "바이트 복사하기" 등와 같이 간단한 명령들을 설명하는 숫자코드이다. 각각의 명령어들은 2진법으로 표현되고 하나의 명령어를 해석하는데 상당히 많은 크기의 기계어를 차지한다. 크기도 상당하고 2진법으로 이루어져 있기 때문에 어떤 명령어로 해석되는지 설명이 어렵고 해석하기도 난해하다. 이러한 문제는 어셈블리어의 출현으로 해결되었다. 숫자 코드를 대신하기 위해 CPY(copy), MOV(move..

티스토리툴바