코딩못하는사람

www.acmicpc.net/problem/4344 코드 배운점 printf,println의 차이 printf printf는 c에서 쓰던 것과 방식이 같다. System.out.printf ("출력서식",출력할 내용) ==> %d(정수) %f(실수) %c(문자) %s(문자열)들을 사용해서 표기 할 수 있다. 당연히 %.2f와 같은 방식으로 소수 몇번 째 자리까지 출력할지 정할 수 있다. println System.out.println("정답은"+result)와 같이 문자열은 ""로 감싸주고 변수들을 섞어서 원하는 출력을 만들어 준다. 여기서 +는 한쪽이라도 문자열일 때는 문자열을 이어 붙이고 숫자끼리라면 덧셈을 해준다. ex) System.out.println("3+5" +5); >>3+55 ex)Sys..

자바의 String 객체와 String 리터럴 자바에서 String은 객체로 선언할 수도 있고 리터럴로도 선언할 수 있다. String temp=new String("abcde"); 은 new 연산자를 활용한 객체 생성 방식 String temp1="abcde"; 은 문자열 리터럴 방식으로 선언한 방식이다. 객체를 생성하는 방식은 Heap영역에, 리터럴은 Heap영역 속 String constant pool에 저장된다. 예시 그림을 보고 이해하자. String str1 = "madplay"; String str2 = "madplay"; String str3 = new String("madplay"); String str4 = new String("madplay"); 문자열 비교 equals메소드: Str..

파이썬에서의 문자열 문제해결방법 in을 사용해서 포함여부 판단하기 find()를 사용해서 index까지 구하기 KMP알고리즘을 사용해서 index 또는 포함여부 구하기 1,2번은 최악의 경우 O(N*M)이지만 KMP알고리즘은 O(N+M)에 해결 가능하다. 리스트 형태로 저장하였다면 ''.join(list_name)으로 공백없는 문자열을 만들 수 있다. 1. in을 사용하기 문자열에 in을 사용해서 찾는 문자열이 포함되는지 판단 가능하다. 만약 포함된다면 True를 아니면 False값을 반환해준다. ex) string='python' print('pyt' in string) =>True print('ppp' in string) ->False 2.find() 함수 사용하기 문자열간에 포함여부와 인덱스를 반환..

1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 1.접근 알파벳 소문자는 26개이다. 따라서 int(32bit) 크기의 2진수 배열에서 알파벳을 각각 하나씩 마스킹에 할당해서 문제를 풀 수 있다. 2.풀이 남극의 모든 단어는 a,n,t,i,c 으로 이루어져 있으므로 k가 5보다 작다면 어떠한 단어도 읽을 수 없다. 5개의 단어는 모두 배운다고 가정한고 한줄씩 입력받으면서 a,n,t,i,c을 지우고 가운데 알파벳들만 입력받는다. 만약 a,n,t,i,c로 지운 리스트의 길이가 0이라면 무조건 읽을 수 있는..

Inversion counting이란? 배열 A는 1,2,3,...n 의 수가 무작위 순서로 들어 있다고 했을 때 그 순서 대비 크기가 역전되어 있는 수들의 쌍을 구하는 문제이다 예를들어 4 2 7 1 5 6 3순서의 배열은(4–2), (4–1), (4–3), (2–1), (7–1), (7–5), (7–6), (7–3), (5–3), (6–3)인 10개의 역순쌍이 있는 것이다. Inversion counting 해결방법 직관적으로 해결하자면 O(n^2)을 이용해서 모든 수에서 모든수를 돌아보면 되지만 O(NlogN)으로 해결하는 merge sort를 이용한 방법과 segment tree를 이용한 방법이 있다. 1.merge sort 병합정렬을 이용한 방법은 병합정렬을 사용해서 반으로 나눈 뒤 합치는 과정..

http://acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 점이 여러 번 주어질 수도 있 www.acmicpc.net 1.접근 n이 100000이므로 O(N^2)으로는 풀 수 없다. 내가 아는 방법이 없는 것 같아서 구글링으로 라인 스위핑 알고리즘과 분할정복을 통한 closest pair 방법이 있었는데 라인 스위핑이 아직 어려워서 분할정복으로 풀어보았다. 라인스위핑:www.acmicpc.net/blog/view/25 closet pair:casterian.net/archives/92 2..

www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 1.접근 N이 2,000,000이므로 NlogN을 생각하게된다. 세그먼트 트리를 이용할텐데 X의 크기도 2000000까지인 것을 보아 리프노드를 200만개로 만들고 1번 유형 쿼리로 숫자와 인덱스가 같은 트리를 만들어야겠다. 2.풀이 우선 트리를 만드는대 어느 숫자가 들어올지 모르기 때문에 리프노드 200만개 모두 만들어야 한다. 그 후 인덱스와 들어오는 숫자가 같은 트리이므로 ..

16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 1.접근 N은 십만 M도 십만이다. N^2으로 해결 불가능하고 NlogN으로 해결한다고 생각했다. 구간 합을 구하는 문제가 아닌 구간에 k를 더하는 문제이다. 생각을 조금 바꿔보자. 세그먼트 트리와 관련되서 생각해보니 1번 쿼리가 들어왔을 때 각 리프노드에 k를 더하지 않고 구간에 해당되는 노드에 k를 넣어놓고 출력할때 꺼내가면 된다고 생각했다. 2.풀이 우선 하던대로 완전 이진 트리를 리프노드만 전처리한다. 리프위에 노드들은 구간합같은 문제가..

세그먼트 트리란? 세그먼트 트리(Segment Tree) 또는 인덱스 트리(Index Tree)는 다음 두 연산을 어떻게 더 효율적으로 할까에 대한 고민에서 출발한다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i] = v 두번째 연산은 O(1)에 해결할 수 있겠지만 첫 번째 연산은 l-r의 길이만큼의 시간 O(NM)이 쿼리가 요청될 때 마다 소요될 것이다. (쿼리 m번 구간크기 n) 따라서 우리는 M과 N이 클때를 위한 자료구조인 세그먼트 트리를 알아야한다. 가장 기본적인 2,3,7,4,5,9,6,1의 구간합을 구하는 세그먼트 트리를 보자. 트리는 완전 이진 트리로 구성된다. 또한 트리의 ..

피보나치 수를 구하는 3가지 방법. 피보나치 수는 알다시피 다음과 같이 정의되는 수열이다. 이렇게 이전 2개의 합이 다음 오는 수가 되는 수열이다. 조금 나열하면 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...이 된다. 가장 기본적인 문제를 풀어보자 10826 피보나치 수 4 www.acmicpc.net/problem/10826 1.접근 n은 10,000보다 작거나 같은 자연수 또는 0이다. 쉬운 피보나치 수이다. 2.풀이 우리는 DP느낌의 방법으로 쉽게 O(N)시간에 답을 구할 수 있다. 3.코드 4.배운점 사실 dp로 구현했었는데 메모제이션 할 필요없이 for 문을 돌리면 가장 간단했다. 2749 피보나치 수 3 www.acmicpc.net/problem/27..