BOJ

문제https://www.acmicpc.net/problem/14496 풀이 주어진 문자를 얼마나 적은 횟수로 변환시켜서 원하는 문자로 변환할 수 있는지 최소 변환 횟수를 구하는 문제이다. 문제 이해가 조금 난해할 뿐이지 실제로는 굉장히 간단한 BFS 문제이다. 입력은 모두 숫자로 주어지므로 단순 정수 기본 아이디어는 다음과 같다. 1. 변환 횟수를 저장할 int 타입의 dis 배열, 방문 여부를 저장할 boolean 타입의 visit 배열 선언2. 연결 리스트 형태로 그래프를 저장하기 위해 list 선언3. BFS는 a에서 시작 (문자 변환을 a부터 시작하기 때문)4. BFS 종료 후, b를 방문하였다면 dis[b]를 출력. 방문하지 않았다면 -1을 출력 추가로, 입력되는 a와 b가 같다면 변환할 필요..

문제https://www.acmicpc.net/problem/25418 풀이 문제를 간단히 요약하면 입력받은 정수 값 A에 두 가지 연산을 적용해 정수 K로 만드는 것이다. 연산 1은 정수 A에 1을 더하기, 연산 2는 정수 A를 2로 곱하기이다. 처음에는 문제 해결을 위한 아이디어를 다음과 같이 잡았다. 먼저 방문 여부를 체크할 visit 배열과 해당 인덱스까지 몇 번만에 도달할 수 있는지를 저장할 arr를 선언한다. 이후 bfs 메소드를 만들어 인자로 정수 n을 받아, arr[n * 2]가 방문하지 않은 상태라면 arr[n] + 1의 값을 저장한다. 그리고 n * 2에 bfs를 다시 걸어 n * 2를 기준으로 bfs를 또 실행한다. 마찬가지로 arr[n+1]이 방문하지 않은 상태라면 arr[n] + ..

문제오늘도 서준이는 삽입 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 삽입 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.크기가 N인 배열에 대한 삽입 정렬 의사 코드는 다음과 같다.insertion_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다. for i 입력첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 저장 횟수 K(1 ≤ K ≤ N2)가 주어진다.다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)출력K 번째 저장 되는 수를 출력한다. 저장 ..

문제오늘도 서준이는 선택 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 선택 정렬로 배열 A를 오름차순 정렬할 경우 K 번 교환이 발생한 직후의 배열 A를 출력해 보자.크기가 N인 배열에 대한 선택 정렬 의사 코드는 다음과 같다.selection_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다. for last A[i] # last와 i가 서로 다르면 A[last]와 A[i]를 교환 }}입력첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 교환 횟수 K(1 ≤ K ≤ N)가 주어진다.다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어..

문제오늘도 서준이는 선택 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 선택 정렬로 배열 A를 오름차순 정렬할 경우 K 번째 교환되는 수를 구해서 우리 서준이를 도와주자.크기가 N인 배열에 대한 선택 정렬 의사 코드는 다음과 같다.selection_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다. for last A[i] # last와 i가 서로 다르면 A[last]와 A[i]를 교환 }}입력첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 교환 횟수 K(1 ≤ K ≤ N)가 주어진다.다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주..

문제심심한 승현이는 너무 심심한 나머지 올바른 괄호열을 가지고 놀고 있었습니다.(()(()))()()그러다가 어쩌다 보니 괄호열을 부러뜨렸습니다.(() (( )))() ()크게 낙담한 승현이는 노력해 보았지만, 대부분이 부러져 버려 단 한 부분만 재사용할 수 있다는 것을 깨닫게 되었습니다.)))()승현이는 이 괄호열을 가지고 놀려고 했으나 올바른 괄호열이 아니기 때문에 행복하지 않았습니다. 이를 보던 지학이는 승현이에게 “그러면 앞과 뒤에 적절하게 괄호를 붙이면 올바른 괄호열이 되지 않을까?”라고 했고, 승현이는 조금 생각한 뒤 그렇게 하기로 했습니다. 예를 들어, 위의 올바르지 않은 괄호열의 경우 앞에 여는 괄호 3개를 붙이면 올바른 괄호열이 됩니다.((()))()그러나 괄호열을 사서 ..

문제세준이는 1×1크기의 그림으로 모자이크한 100×100크기의 그림을 가지고 있다. 어느 날 이 모자이크 중 일부 그림이 너무 보기 싫어서 N개의 불투명한 종이로 그림을 가리기 시작했다. 불투명한 종이로 가린다고 항상 그 그림이 안 보이는 것은 아니다. 그 그림의 현재 부분 위에 M개 이하의 종이가 올려져 있으면 그림은 그 부분에서 보이게 된다.그림의 크기는 100×100이고, N개의 종이는 왼쪽 아래 모서리 좌표와 오른쪽 위 모서리 좌표가 입력으로 들어온다. 또, 종이가 가리는 영역에는 두 모서리의 좌표도 포함된다. 예를 들어, (1,1)부터 (2,2)를 가린다면, 총 4개의 그림이 가려진다. (1,1), (1,2), (2,1), (2,2).100×100크기의 모자이크 중에 보이지 않는 그림의 개수를..

문제수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.출력총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.제한1 ≤ N ≤ 100,0001 ≤ M ≤ 100,0001 ≤ i ≤ j ≤ N 풀이배열의 구간 합을 구하면 되는 단순한 문제처럼 보이지만 N, M의 범위에 의해 이중 반복문을 사용한다면 시간 초과가 발생하게 된다.따라서 이중 반복문이 아닌 다른 방법을 사용해야 하는데, 누적 합 개념을 이용해야 한다.누적 합은 기존의 ..