Algorithm
[바킹독의 실전 알고리즘 강의] 연결 리스트
연결 리스트 정리 2021.03.07 - [Computer Science/DataStructure] - Linked List (연결 리스트) 연결 리스트 문제 BOJ 1406 에디터 BOJ 5397 키로거 손코딩 문제 1 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법? 정답 동일한 노드가 나올 때 까지 계속 다음 노드로 가면 됨 공간복잡도 O(1), 시간복잡도 O(N) 손코딩 문제 2 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때 만나는 지점을 구하는 방법? 정답 일단 두 시작점 각각에 대해 끝까지 진행시켜서 각각의 길이를 구함. 그 후 다시 두 시작점으로 돌아와서 더 긴쪽을 둘의 차이만큼 앞으로 먼저 이동시켜놓고, 두 시작점이 만날 때 까..
BOJ 3273 두 수의 합
문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] ar..
BOJ 1475 방 번호
문제 다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다. 다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.) 입력 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 필요한 세트의 개수를 출력한다. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) th..
BOJ 2577 숫자의 개수
문제 세 개의 자연수 A, B, C가 주어질 때 A × B × C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오. 예를 들어 A = 150, B = 266, C = 427 이라면 A × B × C = 150 × 266 × 427 = 17037300 이 되고, 계산한 결과 17037300 에는 0이 3번, 1이 1번, 3이 2번, 7이 2번 쓰였다. 입력 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다. 출력 첫째 줄에는 A × B × C의 결과에 0 이 몇 번 쓰였는지 출력한다. 마찬가지로 둘째 줄부터 열 번째 줄까지 A × B × C의 결과에 1부터 9까지의 숫자가 각각..
[바킹독의 실전 알고리즘 강의] 배열
배열 정리 2021.02.25 - [Computer Science/DataStructure] - Array (배열) 배열 문제 길이 N의 정수형 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을 반환, 존재하지 않으면 0을 반환하는 함수 func2 (arr[],int N)를 작성하여라. arr의 각 수는 0이상 100이하, N은 1000이하이다. O(N)으로 풀어보기 0부터 100까지 담을 수 있는 배열을 선언하고 arr를 순회하면서 현재 idx와 더해 100을 만들 수 있는 수가 있는지 찾기 int func2(int arr[], int n) { int countArr[] = new int[101]; for(int idx = 0; idx < n; idx++) { if(countAr..
BOJ 10808 알파벳 갯수
https://www.acmicpc.net/problem/10808 10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] arr = new int[26]; String s = br.readLine(); for (int i = 0; i < s.length(); i+..