분류 전체보기
p10010 ( Where's Waldorf )
문제 문자들이 적혀있는 표( 배열, 격자 ) 에서 왼쪽 위에서부터 오른쪽 밑으로 탐색하여 찾고자 하는 문자열을 8방향으로 탐색, 탐색에 성공하면 현재 위치를 출력하는 문제이다. 추가조건으로 문자의 대소문자를 구분하지 않는다. 위의 예제에 대하여 나타내면 다음과 같다. 입력되는 격자의 최대 크기가 50 x 50이고, 찾는 문자열의 길이는 최대 20이다. 격자의 각 위치마다 8방향을 탐색하고, 최대 길이가 20이므로 단순하게 50 x 50 x 8 x 20으로 계산을 해보더라도 40만이다. 그냥 좌측 위를 ( 0, 0 )으로 두고 오른쪽 아래로 나아가며 8방향 탐색을 하면 된다고 판단했다. 소스코드. 더보기 #include #include using namespace std; #pragma warning(di..
p10150 ( Doublets )
문제 동일한 길이의 두 문자열의 차이가 한 글자만 있는 경우 Doublet이라 한다. 단어사전에 해당하는 문자열이 한줄에 하나씩 나열되며, 두 문자열이 공백을 기준으로 나뉘어져 입력이 들어오게되면 출력을 해야함을 의미한다. 출력은 입력으로 들어온 두 문자열 중에서 앞의 것을 시작 단어, 뒤의 것을 끝 단어로 둔다. 시작단어부터 현재 단어와 Doublet관계에 있는 단어를 타고 다음 단어로 이동이 가능하다. 끝 단어에 도착하게 되면 지금껏 타고온 단어들을 순서대로 출력해야한다. (단, 제일 빠르게 끝 단어에 도착한 순서를 출력해야한다. ) 문자열의 최대길이는 16이며, 입력되는 단어의 최대개수는 25143개 이다. booster rooster boosted roaster coasted roasted coa..
p679 ( Dropping Balls )
FBT, 완전 이진 트리에 대하여 푸는 문제. FBT의 모든 노드는 초기값이 false로 세팅되어있고, 공은 루트노드부터 떨어진다. 공이 거쳐간 노드는 값이 반전( false라면 true로, true라면 false로 ) 되며, false였다면 왼쪽으로 공이 떨어지고 true면 오른쪽으로 떨어진다. 트리의 높이와 공을 떨어뜨린 횟수가 주어졌을 때, 마지막에 떨어진 공이 위치하는 노드의 값을 출력하는 문제. 공은 리프노드까지 떨어진다. 풀이 더보기 위와 같은 트리에서 공을 떨어트릴 수 있는 기회는 총 8번이다. ( 리프노드까지 공이 떨어지므로 ) 이를 숫자로 표현하여 다시 나타내보면 다음과 같다. 잘 보면 루트노드를 기준으로 왼쪽 서브트리는 모두 홀수의 순서값을 가지고, 오른쪽 서브트리는 짝수의 순서값을 가..
p10137 ( The Trip )
여행경비로 지출된 총 금액을 모든 인원이 최대한 균등하게 돈을 지출하도록 만드는 문제 돈을 많이 낸 사람들과 작게 낸 사람들 중 평균값과의 차이가 더 큰 만큼 돈을 이동해야한다. 예를 들어 13.01 13 3.01 3 이렇게 돈을 냈다고 가정했을 때, 총 지출한 돈의 양은 32.02 달러이다. 이를 4로 나누게 되면 8..005달러가 되지만, 0.5센트는 없으므로 8달러와 8.01달러로 평균값을 둔다. 8달러와 8.01달러 중 작은 금액에 해당하는 8달러보다 작게낸 사람은 3.01달러와 3달러가 되고, 8.01달러보다 많이 낸 사람은 13.01달러와 13달러가 된다. 적게낸 사람들 각각 평균값과의 차이는 4.99달러, 5달러이고 많이낸 사람들 각각 평균값과의 차이는 5달러, 4.99달러이다. 적게낸 사람..
p100 ( 3n + 1)
두 수 i, j 를 입력받은 다음, 그 사이 값에 대하여 규칙에 따라 연산을 했을 때, 제일 연산을 많이 수행했을 때의 횟수를 출력하는 문제. 규칙 홀수이면 *3을 하고 1을 더한다. 짝수이면 /2를 한다 더보기 #include #include #pragma warning(disable:4996); using namespace std; int solve(int num) { int cnt = 1; while (num > 1) { cnt++; if (num % 2 == 0) { num /= 2; } else { num = num * 3 + 1; } } return cnt; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); in..
Dynamic Sets (계속 추가될 예정 )
Dynamic Set? Dynamic Set( 동적 집합 )이란 집합의 요소들이 계속해서 변화하는 집합입니다. Dynamic Set의 자료구조는 여러개가 존재합니다. BST : 이진 탐색 트리 AVL Tree : 균형잡힌 이진 탐색 트리 2-3 Tree Red-Black Tree Splay Tree ....? 동적 집합에서 몇몇의 쿼리와 수정 연산자를 지원하며, 모두 O(log n)의 시간복잡도를 가져야합니다. Search(S, k) : S 내에서 key가 k의 값을 가지는 원소 탐색 Minimum(S) : S 내에서 key값이 가장 작은 값을 가지는 원소 Maximum(S) : S 내에서 key값이 가장 큰 값을 가지는 원소 Successor(S, x) : S 내에서 x의 key 값을 가지는 원소의 다..
람다식
목표 자바의 람다식에 대해 학습하세요. 학습할 것 (필수) 람다식 사용법 함수형 인터페이스 Variable Capture 메소드, 생성자 레퍼런스 람다식 람다 식은 자바 8 버전에서 추가된 기능입니다. 오라클 자바 튜토리얼에서는 람다식의 사용배경에 앞서 기존 익명클래스의 불편함에 대하여 얘기합니다. 하나의 메소드만 포함하는 인터페이스처럼 익명 클래스의 구현이 매우 단순할 경우 사용이 불편할 수 있다. 위와 같은 상황에서 불편함을 해결하기 위하여 등장한 기능이 람다식 이라고 합니다. 앞서 말한 하나의 메소드만 포함하는 인터페이스는 주로 함수형 인터페이스라고 부릅니다. 이런 함수형 인터페이스의 예시로 멀티쓰레드를 공부할 때 배웠던 Runnable 인터페이스가 떠올랐습니다. 람다식의 사용에 앞서서 기존 익명클..
제네릭
제네릭? 제네릭, 어노테이션, 스트림, 람다.. 자바를 접하게되면서 "이게 뭐지?" 라는 생각이 들게만든 키워드이다. 어노테이션은 기능을 가진 주석. 람다는 함수형 인터페이스를 간편하게 표현. 스트림은 작업의 흐름을 표현하는 방법. 자바 공부를 하게되면서 각각의 키워드를 나름대로 위와 같이 생각하게 되었다. 그렇다면 제네릭은 무엇일까? 제네릭은 클래스나 인터페이스 또는 메소드 정의 시에 이 자리에 사용될 타입을 호출이나 선언 시 지정해라. 를 표현하는 방법이다. 여기서 이런 종류에 프리미티브 타입은 올 수 없다. 제네릭이 사용된 List인터페이스를 보면 와 같이 표현된 부분을 찾을 수 있으며, 이 부분이 바로 제네릭이다. 이는 List를 선언할 때 E타입의 값을 가지도록 지정할 수 있다는 의미를 가진다고..
입출력
목표 자바의 Input과 Ontput에 대해 학습하세요. 학습할 것 (필수) 스트림 (Stream) / 버퍼 (Buffer) / 채널 (Channel) 기반의 I/O InputStream과 OutputStream Byte와 Character 스트림 표준 스트림 (System.in, System.out, System.err) 파일 읽고 쓰기 자바의 입출력 자바에서의 입출력은 Stream, Buffer, Channel 기반으로 작동합니다. 스트림( Stream ) 스트림(Stream) 이란, 데이터의 흐름 또는 데이터의 순서를 의미합니다. Source( 키보드 or 파일 etc.. )에서 InputStream을 이용하여 데이터를 읽어 들이고 OutputStream을 이용하여 Destination( 콘솔 or..