본문 바로가기

알고리즘

창발성 떠오름 현상은 하위 계층(구성 요소)에는 없는 특성이나 행동이 상위 계층(전체 구조)에서 자발적으로 돌연히 출현하는 현상이다. 모든 테스트를 실행한다. 중복을 없앤다. 프로그래머 의도를 표현한다. 클래스와 메서드 수를 최소로 줄인다. 테스트를 철저히 거쳐 모든 테스트 케이스를 항상 통과하는 시스템을 만들라. - 테스트가 가능한 시스템을 만들려고 애쓰면 설계품질이 높아진다. - SRP 를 준수하는 클래스일수록 테스트하기 쉽다. - 테스트 케이스가 많을수록 개발자는 테스트 코드를 쉽게 작성한다. - 결합도가 높으면 테스트 케이스를 작성하기 어렵다. DIP 의존성 주입, 인터페이스 추상화 등을 통해 결합도를 낮춘다. - 테스트 케이스를 만들고 계속 돌려라라는 간단하고 단순한 규칙을 따르면 시스템은 낮은 결합도.. 더보기
백준 16934 게임 닉네임 https://www.acmicpc.net/problem/16934 16934번: 게임 닉네임 첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고, �� www.acmicpc.net 1 . 트라이 문제에 들어가기 앞서 간단히 트라이에 대해 설명하겠다. 트라이는 문자열 검색에 특화된 트리로 다음과 같은 구조를 가지고 있다. 각 노드마다 Map을 가지고 있고, 문자열을 문자단위로 쪼개고 노드에 저장한다. 문자열를 검색하고 삽입하는데 걸리는시간은 O(NlogN)이다. 2. 알고리즘 알고리즘은 다음과 같다. 1. 문자열(word)을 문자로 쪼개고 각 문자를 노드에.. 더보기
백준 - 6198 옥상정원꾸미기 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으�� www.acmicpc.net 스택에 아이템을 한 개씩 push하면서 스택의 top()과 비교한다. push 한 아이템의 높이가 스택의 top() 보다 작다면 스택의 모든 원소들은 그 아이템을 볼 수 있다는 뜻이다. 그러므로 답에 스택의 크기만큼 더해준다. 아이템의 크기가 스택의 값보다 크거나 같다면 스택의 top() 더이상 아이템 오른쪽에 있는 것들을 보지 못하므로 pop 시켜주고 이를 모든 아이템에 대해서 반복하.. 더보기
JAVA 8 - (1) 람다 함수 1. 람다 함수 VS 기존 JAVA 익명 함수 , 익명 클래스 기존 Java에서도 익명함수, 익명 클래스는 있었다. 다음과 같이 표현되었다. Comparator 인터페이스를 상속받는 클래스를 상속 받기 위해 위와 같은 익명클래스를 사용하고 했다. 하지만 보다시피 코드가 너무 길고, 복잡하고, 실제로 나같은경우에도 실수를 너무 많이 했던 부분이다. 람다 함수를 이용하면 같은 코드를 훨씬 더 간결하게 쓸 수 있다. 그러면 람다함수는 어떻게 작동하는 것이고 어떤 문법을 가지고 있는지 알아보자 2. Functional Interface(함수형 인터페이스) 우선 람다함수를 알기 전에 Functional Inteface에 대해서 알고 있어야한다. Functional Interface는 Interface 중에서 단 .. 더보기
백준 17822 원판 돌리기 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 삼성 공채에서 나온 시뮬레이션 문제다. 삼성 역테 A+를 목표로 하거나 공채 코테를 목표로 하려면 1시간 안에는 풀어야 한다고 생각한다. 주의 할 점은 시뮬레이션에서 지우거나 없애거나 바꾸거나의 동작을 할 경우 항상 예외를 생각해야한다. 이 문제의 경우 3가지 정도 까다로운 점이 있다. 1. 회전시키기 회전시키려는 배열의 크기가 작다면 임시 배열을 만들어서 회전시키는 걸 추천한다... 더보기
백준 세부 13905 https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 다익스트라를 변형해서 풀면된다. 기존의 다익스트라가 한 정점에서 다른 정점으로의 최단거리를 구한다고 하면 변형된 다익스트라는 한 정점에서 다른 정점으로의 경로중로 이동하는 가중치의 최소값들의 최대값을 구하는 것이다. 예시로 든 그림을 보면 1에서 5로 가는 경로는 총 4가지다. 1) 1-2-3-5 2) 1-7-3-5 3) 1 -7-5 4) 1-7-6-5 각.. 더보기
백준 15961 회전초밥 https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 연속해서 K 개의 초밥을 먹었을때 먹을수 있는 최대의 초밥 종류 갯수를 구하는 문제다. 완전탐색을 이용할 경우 초밥의 접시가 N이 최대 300만개, 연속해서 먹을수 있는 접시의 갯수 k 가 최대 3000이므로 시간복잡도가 O(N*k) = O(300만 * 3000) = O(90억)이므로 시간초과가 난다. 연속하는 경우 수를 구할때는 투포인터를 이용하여 풀.. 더보기
swea 9843 촛불 이벤트 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXGBKzuaPOoDFAXR&categoryId=AXGBKzuaPOoDFAXR&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com N이 주어졋을때 이 N개의 촛불을 1 2 3 4 5 6 7 8 .. K 와 같은 방식으로 쌓을수있는지 판단하는 문제이다. 1~K 의 등차수열의 합은 K(K+1)/2이므로 K(K+1)/2 = N의 해를 구해주면된다. 완전 탐색으로는 N이 10^18 이므로 당연히 안되고 이분탐색을 이용하면 logN시간에 방정식의 해를 구.. 더보기

티스토리툴바