전체 글
[BOJ/JAVA] 2580번: 스도쿠
2580번: 스도쿠 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 키워드 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다. 구현 2번을 구현하기 위해 findBase 메소드를 작성한다.EX] [4,5] → [3,3] y, x좌표가 입력되면 해당 3*3 정사각형에서 좌측 상단의 좌표를 반환한다. 현재 위치에서 될 수 ..
[BOJ/JAVA] 마법사 상어와 토네이도
20057번: 마법사 상어와 토네이도 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 키워드 다음은 토네이도의 이동 경로이다. 다음은 x→y로 이동할 때 y의 모래의 이동 비율이다. 계산에서 소수점 아래는 버린다. 구현 중요한 것은 a의 값이 55%가 아니라는 것이다. 계산에서 소수점 아래는 버리는 연산을 하므로, 흩뿌려진 모래값을 전부 뺀 뒤에 남은 값이 a가 된다는 것이다. 처음엔 토네이도를 달팽이처럼 이동시키는 알고리즘을 작성한다. 다음으로 수평, 수직에 따라 모래를 흩뿌리..
[BOJ/JAVA] 3190번: 뱀
3190번: 뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 키워드 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행 게임이 시작할때 뱀은 맨위 맨좌측에 위치 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 ..
[BOJ/JAVA] 23351번: 물주기
https://www.acmicpc.net/problem/23351 23351번: 물 주기 첫째 줄에 자연수 $N$, $K$, $A$, $B$가 공백을 사이에 두고 주어진다. ($2 \le N \le 100$, $1 \le K \le 100$, $1 \le A \times B < N$, $A$는 $N$의 약수) www.acmicpc.net 키워드 일직선으로 놓여진 N개의 화분에 캣닢이 하나씩 심어져 있다. 각 화분은 초기에 K만큼의 수분을 머금고 있고, 매일 아래와 같은 일이 순서대로 일어난다. 랑이 집사가 연속된 A개의 화분에 물을 준다. 이 때 물을 준 화분의 수분은 B만큼씩 증가한다. 모든 화분의 수분이 1씩 감소한다. 수분이 0이 된 화분에 있는 캣닢은 죽는다. 모든 캣닢이 살아 있는 기간이 최대..
[BOJ/JAVA] 10709번: 기상캐스터
10709번: 기상캐스터 10709번: 기상캐스터 출력은 H 행으로, 각 행에는 공백으로 구분된 W 개의 정수를 출력한다. 출력의 i 번째 행 j 번째 정수 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는, 지금부터 몇 분후에 처음으로 구역 (i, j) 에 구름이 뜨는지를 표시 www.acmicpc.net 키워드 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동한다. 외부에서 구름이 이동해 오는 경우는 없다. 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지 구현 결과 2차원 배열을 -1로 초기화한다. 시간이 지남에 따라(반복문) 해당하는 동작을 모듈화하여 구현한다. 각 행마다 열의 구름의 [i][0] 부터 [i][W-1] 까지 구름의 위치를 찾는다. 구름의 위치는 가장 오른쪽 구름의 위치를 저장한다..
문자열 알고리즘
용어 정리 |S| 문자열 S의 길이 S = “abcde” 라면 |S| = 5 S[i] (0 ≤ i < |S|) 문자열 S의 i번 글자 S = “abcde” 라면 S[3] = d S[i…j] 문자열 S[i] 부터 S[j] 까지 부분 문자열 S = “abcde” 라면 S[1…3] = bcd S[…a] 문자열 S[0] 부터 S[a] 까지 부분 문자열 S = “abcde” 라면 S[…3] = abcd S[b…] 문자열 S[b] 부터 S[|S|-1] 까지 부분 문자열 S = “abcde” 라면 S[3…] = de 문자열 검색 긴 문자열 H가 문자열 N을 부분 문자열로 포함하는지 확인하는 방법 H = “avava” N = “ava” 라면 N이 출현하는 모든 인덱스를 반환하는 알고리즘을 작성한다고 하자 이때 결과값은..
[BOJ/JAAVA] 1967번: 트리의 지름
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 키워드 트리의 지름 : 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다. 구현 주어진 정보를 이용하여 트리를 구현한다. 모든 노드를 돌면서 현재 노드 위치를 루트로 하는 서브트리에서 루트를 무조건 거치는 최대 길이를 구한다. 코드 import java.io.BufferedReader; import java.io.IOException; impor..
[BOJ/JAVA] 15681번: 트리와 쿼리
https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 키워드 • 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다. 구현 어떤 것이 부모노드이고 어떤 것이 자식 노드인지 알 필요가 있다. 루트번호 R을 이용하여 DFS를 사용하고, 해당 노드의 부모노드를 알아낸다. 이후 DP를 사용하여 해당 노드 번호의 서브트리에 속한 정점의 수를 저장한다. 코드 import java.io.Bu..
[BOJ/JAVA] 9934번: 완전 이진 트리
https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 키워드 가장 처음에 상근이는 트리의 루트에 있는 빌딩 앞에 서있다. 현재 빌딩의 왼쪽 자식에 있는 빌딩에 아직 들어가지 않았다면, 왼쪽 자식으로 이동한다. 현재 있는 노드가 왼쪽 자식을 가지고 있지 않거나 왼쪽 자식에 있는 빌딩을 이미 들어갔다면, 현재 노드에 있는 빌딩을 들어가고 종이에 번호를 적는다. 현재 빌딩을 이미 들어갔다 온 상태이고, 오른쪽 자식을 가지고 있는 ..
[BOJ/JAVA] 11725번: 트리의 부모 찾기
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 키워드 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 구현 중요한 점은 이진트리가 아니라는 점이다. 1번 노드부터 DFS를 하면서 부모의 정보를 넘겨주면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; impo..