SW 공부노트

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N퀸 문제는 N x N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. 주로 8퀸 문제로 불리는 이 문제는 재귀 알고리즘을 이해하기 위한 예제로 자주 사용된다. N퀸 문제를 해결하기 위한 조건은 다음과 같다. 각 열에 퀸을 1개만 배치한다. 퀸 배치 함수의 인수 겹치지 않는 수(i: 열)을 넣는다. 각 행에 퀸을 1개만 배치한다. for문의 변수가 행 번호(j)로 flag 조건에 따라 알맞는 값을 넣..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 하노이의 탑은 쌓아 놓은 원반을 최소 횟수로 옮기기 위한 알고리즘이다. 처음에 모든 원반이 크기가 큰 순서대로 첫 번째 기둥에 쌓여 있고, 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기는 문제이다. '하노이의 탑' 문제는 대표적인 재귀 알고리즘 문제이다. '하노이의 탑' 알고리즘은 크게 3단계로 나눌 수 있다. 바닥의 원반을 제외한 그룹을 시작 기둥에서 중간 기둥으로 이동 바닥의 ..

https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 스택을 이용하면 쉽게 구현할 수 있는 문제이다. 자바에서 스택을 사용할 수 있는 방법은 두 가지가 있다. 직접 구현 Util 패키지 Stack 클래스 1. 직접 구현 스택을 직접 구현할 땐 데이터를 담을 배열(stk)과 마지막 원소 위치를 가리키는 변수(ptr)을 사용하면 된다. import java.io.*; import java.util.*; public cl..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이 문제를 처음 보고 든 생각난 풀이는 그냥 배열을 리스트로 변환한 후 contains를 사용하는 것이었다. 되게 간단한 문제같은데 정답률이 30%도 안되는 걸 보고 "이렇게 푸는건 아니구나" 싶었다. 처음 작성한 코드는 다음과 같다. import java.io.*; import java.util.*; public class Boj_1920 { pu..