룰루랄라 알고리즘

무려 DGB 금융그룹이 주최하고 금융감독원, 구글, 마이크로소프트, AWS가 후원하는 대한민국 디지털 인재양성 프로젝트 IT's DGB IM Challenger에 본선진출하게 되었다. 우리 팀 이름이 뭔지는 비밀이다.

1장 운영체제 -> main memory 관리 컴퓨터구조 -> cache memory 관리 High-level 언어 -> 어셈블리어 -> 기계어 CPU가 쓰는 register가 있고 프로그래머가 쓰는 register가 있다. 무어의 법칙 : 프로세서의 성능이 2년마다 2배씩 증가한다. Hardware 와 Software 측면에서 성능 1. 알고리즘 - source-level 에서 명령어의 개수 결정 2. 언어, 컴파일러, 아키텍처(CISC, RISC) - target에 맞는 언어와 좋은 컴파일러 (어셈블리어 수를 줄여주는) - machine-level 에서 명령어의 개수 결정 3. 운영체제 스케줄러 - 프로그램을 효율적으로 스케줄링한다. 4. 프로세서, 메모리 - machine-level 명령어의 실행 ..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 오늘 취업전선에 먼저 뛰어든 여자동기 친구와 이런저런 스몰토크를 하다가 친구가 친 대기업에서 자료구조를 기반으로 한 코테 문제가 많이 나왔다는 소리를 듣고, 작년에 배운 자료구조를 생각해 보다가 트리에 대해 잘 기억이 안 나는 것 같아서 관련 문제를 풀어봤다. 자료구조 강의 시간에 C를 기반으로 배웠었는데 자바로 푸니까 확실히 선녀다. C로 할때는 트리 구성할 때 포인터로 연결하면서 ..

https://www.acmicpc.net/problem/1522 내가 제일 싫어하는 문자열 문제인 줄 알고 풀어봤는데 사실 문자열은 별로 관련 없고 슬라이딩 윈도우 문제였음. 처음에 문제 봤을 때 문자열을 서로 교환해야 되니까 자료구조로는 배열이 적합하다 해서 그냥 배열을 선택했다. 근데 사실 교환하는 로직은 문제를 푸는데 아무 관련 없다. 문자열이 처음과 끝이 연결되길래 원형큐인가 하고 봤는데 그것도 아니었다. 그래서 그냥 배열로 풀었다. 이건 그냥 문자열 길게 늘어뜨려놓고 A의 개수를 세서 처음부터 한 칸씩 움직이면서 B의 최소 개수를 세주기만 하면 된다. (문자열의 길이가 짧아서 가능한 브루트포스 느낌) (문자열 처음이랑 끝이 연결되니까 나머지 연산자로 한번 더 계산해 주자) 처음에 생각해 본 로..

보안에 민감한 응용프로그램들은 안전하지 않거나 약한 암호 함수를 피해야만 한다. DES (Data Encryption Standard) 암호 알고리즘은 매우 안전하지 않은 것으로 간주되는데, DES로 암호화된 메세지는 EFF Deep Crack과 같은 머신에 의해 하루 만에 무차별 대입 공격에 의해 복호화된다. 그럼 강한 암호 알고리즘을 간단하게 살펴보자. AES (Advanced Encryption Standard) AES는 다양한 키 길이를 지원하며 특히 256 비트 키 길이를 사용할 경우 높은 수준의 보안을 제공한다. 블록 암호화 방식으로 작동하며, 평문을 고정길이의 블록으로 나누어 암호화하고 복호화한다. Java Cryptography Extension 패키지를 사용하여 AES 암호화 및 복호화를..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 집에 누워있으면 진짜 안될 것 같은 위기감을 느끼고 집 앞 2분 거리 카페에 나와서 문제를 풀었다. 다이나믹 문제를 풀려고 푼 게 아니라 내가 좋아요 누른 문제집을 거의 다 풀고 2개 남아서 그중 하나를 골랐는데 풀어보니 dp였다. 이제 문제를 보기만 하면 dp가 생각이 난다 사실 문제를 풀려고 카페를 갔던 게 아니라서 펜과 종이가 없어서 그림판으로 풀었다. 작은 수를 놓고 좀만 끄적이다 보면 바로 규칙이 나온다. dp는 늘 규칙찾는 퍼즐 푸는 것 같다 1. [][0]에는 이전까지의 합을 누적해서 저장 2. [][1]에는 마지막 ..

Object가 기본적으로 제공하는 equals() 메서드는 모든 객체에 대해 메모리 주소로 비교한다 사실 지금까지 객체가 동일한지가 아닌 객체의 내용이 동일한지 판단할 때 equals를 사용했었기 때문에 잠깐 혼동이 왔었는데 내가 여태 사용했던 것은 Object.equals를 오버라이딩한 String.equals였다. 오늘 아이템은 "Object.equals()로 비교하지 말자"이다. (메모리 주소로 비교하기 때문에) 📌 솔루션 Object.equals만 사용하지 않고 여러 단계를 거쳐 검증하는 equals 해당 코드는 3단계로 이루어져 있다. 1. 두 Key가 동일한지 비교 2. 두 Key 객체의 인코딩 된 값 비교 3. 두 Key 모두 RSAPrivateKey 인스턴스라면 모듈러스와 개인 지수 비교 ..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 주말 하루종일 침대에만 있다가 죄책감이 들어 저녁 먹고 간단하게 홈트 후에 쉬운 문제를 풀어보았다. 다이나믹 프로그래밍은 예전에 문제를 많이 풀어봐서 바로 풀이법이 떠올랐다. // 0 1 2 3 4 // 0 0 00 000 // 1 1 11,01 111,001,011 // 2 2 22,02,12 222,002,022,012,112,122 // 3 3 33,03,..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 학교 전공 시간에 너무 듣기 싫어서 오랜만에 문제를 풀어봤다. 물론 전공시간 동안 못 풀어서 집에서 마저 풀었다. 체스에 조예가 깊었던 나는 맘에 드는 제목을 보고 덥석 풀어봤지만 시간복잡도의 늪에 빠져 몇 시간을 헤맸다. 3트 끝에 겨우 통과했다. 그럼 내가 처음에 제시했던 아이디어와 그 이후 가지치기로 시간복잡도를 줄인 코드를 살펴보자. 3가지 방법이 생각났다. 1. Pair(x, y) 클래스를 생성 후 Se..

마침 Effective Java에서 관련된 주제를 다룬 적이 있어서 자세한 내용은 아래를 참조하자. https://com-squadleader.tistory.com/267 [Effective Java] Item 50. 적시에 방어적 복사본을 만들라 자바는 네이티브 메서드를 사용하지 않아 C, C++ 같이 안전하지 않은 언어에서 흔히 보는 버퍼 오버런, 배열 오버런, 와일드 포인터 같은 메모리 충돌 오류에서 안전하다. 자바로 작성한 클래스는 com-squadleader.tistory.com 가변적 메서드의 매개변수를 방어적으로 복사하면 다양한 보안 취약점을 완화시킨다. 그러나 clone() 메서드를 부적절하게 사용하면, 정상적으로 보이지만 예상하지 못한 결과를 반환하는 매개변수를 공격자에게 제공하게 되어 ..