note

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 처음엔 제일 작은 수부터 시작해서 점점 길이를 줄이면서 잘라내고 자른 개수 >= N 이면 멈추는 방식으로 코드를 짰는데 틀렸다. # 틀림 import sys k, n = map(int, sys.stdin.readline().split()) cable = [] for i in range(k): cable.append(int(sys.stdin.readline())) len..

객체 지향 - 컴퓨터가 수행하는 작업을 객체들 간의 상호작용으로 표현 - 클래스 혹은 객체들의 집합으로 프로그램 작성 캡슐화 - 객체를 캡슐로 싸서 그 내부를 보호하고 볼 수 없게 하는 것 상속 - 상위 개체의 속성을 하위 개체에 물려줌. 다형성 - 같은 이름의 메소드가 클래스나 객체에 따라 다르게 구현되는 것 - 메소드 오버로딩: 한 클래스 내에서 같은 이름이지만 다르게 작동하는 여러 메소드 - 메소드 오버라이딩: 슈퍼클래스의 메소드를 동일한 이름으로 서브 클래스마다 다르게 구현 클래스와 객체 - 클래스: 객체의 속성과 행위 선언. 객체를 만들어내기 위한 틀 - 객체를 클래스의 인스턴스라고 함. - 객체들은 클래스에 선언된 동일한 속성을 가지지만 속성 값은 서로 다르다. 자바 클래스 만들기 클래스 구성..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 채점하는데만 1분 30초는 걸려서 나 처음에 시간 초과 뜨는 줄^^,, import sys n = int(input()) card = sorted(map(int, sys.stdin.readline().split())) m = int(input()) find = list(map(int, sys.stdin.readline().split())) dict_card = d..

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 반복문으로 이진탐색을 풀어주었다 import sys n = int(sys.stdin.readline().rstrip()) a = list(map(int, sys.stdin.readline().split())) m = int(sys.stdin.readline().rstrip()) b = list(map(int, sys.stdin.readline().s..

순차 탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 - 데이터 정렬 여부와 상관 없이 가장 앞에 있는 원소부터 하나씩 확인 - 시간 복잡도 O(N) ㄴ 데이터의 개수가 N개일 때 최대 N번의 비교 연산 # 순차 탐색 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i + 1 # 현재의 위치 반환 print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.") input_da..

배열 - 인덱스와 인덱스에 대응하는 일련의 데이터들로 이루어진 연속적인 자료 구조 - 같은 종류의 데이터들이 순차적으로 저장된다. 배열 선언 및 생성 1) 배열에 대한 레퍼런스 변수 선언 2) 배열 생성 - 배열 공간 할당 레퍼런스 치환과 배열 공유 - 자바에서는 배열 공간과 레퍼런스 변수가 분리되어 있기 때문에 생성된 배열에 대한 공유가 쉽게 이루어진다. - 레퍼런스의 치환은 배열을 복사하여 새로운 배열을 만드는 것이 아니라 레퍼런스만 복사된다. - myArray는 intArray 레퍼런스 값을 가지게 됨으로써 intArray 배열을 공유하게 된다. int intArray[] = new int[5]; int myArray[] = intArray; // 레퍼런스 치환. myArray는 intArray와 ..

애증의 자바 이제 더이상 미룰 수 없다 처음부터 다시 차근차근 해보자.. 자바 프로그램의 구조 public class Hello { // 메소드 public static int sum(int n, int m) { return n + m; } // 메소드 // main() 메소드에서 실행 시작 public static void main(String[] args) { int i = 20; int s; char a; s = sum(i, 10); // 메소드 호출 a = '?'; System.out.println(a); System.out.println("Hello"); System.out.println(s); } } 클래스 - 자바에서는 클래스를 만들고 그 안에 변수, 상수, 함수(메소드) 등 모든 프로그램 ..

정렬 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택 정렬 : 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복 -> 매번 '가장 작은 것을 선택' - 시간복잡도 O(N^2) ㄴ 연산횟수: N + (N-1) + (N-2) + ··· 2 → N*(N+1)/2 → O(N^2) ㄴ 소스코드: 2중 반복문 사용 # 선택 정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if array[min_index] > array[j]: min_in..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 날 아주아주아주아주 화나게 한 문제다 맞는 거 같은데 자꾸 틀려서 열심히 반례 찾고 다녔다 예시 입력1 2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2 예시 출력1 YES NO 예시 입력2 11 3 1 2 3 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2 3 2 2 1 3 2 4 4 2 1 3 2 4 3 4 1 5 2 1 5 1 2 5 2 1 2 2 5 4 3 1 2 4 3..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net from collections import deque t = int(input()) def bfs(x1, y1, x2, y2): queue = deque() queue.append([x1, y1]) chess[x1][y1] = 1 dx = [-1, -2, -2, -1, 1, 2, 2, 1] dy = [-2, -1, 1, 2, 2, 1, -1, -2] while queue: qx, qy = queue..