프로그래밍 공방

문제 programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 문제해결방법 이 문제를 풀기 위해 먼저 Floyd Warshall 알고리즘으로 모든 정점 사..

문제 www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제해결방법 이 문제는 n과 m이 주어지면 m개 중에 n개를 고르는 조합 문제였다. 제한시간이 0.5초라 시간을 줄이기 위해서 미리 구할수 있는 모든 조합의 수를 계산해두기로 했다. 처음에는 1부터 모든 n까지의 곱 DP를 계산하고 m개에서 n개를 구할 때 DP를 사용해서 구할려고 했다. 그런데 위와 같은 방법은 자료형의 범위를 초과해서 1C1~mC1 을 구하고 미리 계산해둔 것들을 이용해서 2C2~mC2..

문제 www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제해결방법 이 문제는 위상정렬 문제였는데 이 전에 풀었던 문제와 다른 점은 가능하면 쉬운 문제부터 풀어야 한다는 점이였다. 이 부분을 해결하기 위해 Priority Queue를 사용해서 문제집들을 정렬해서 출력해주었다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464..

Trie : 트라이 빠른 패턴 매칭을 지원하기 위해 문자열들을 저장하는 트리 기반의 자료구조이다. Trie의 특징 1. Trie의 주요 질의 연산은 패턴 매칭과 접두사 매칭(prefix matching)이다. 2. Trie는 루트로부터 리프 노드들까지의 경로로써 문자열을 표현한다. 크기 d의 알파벳으로 s개의 문자열의 집합 S(전체 길이 n)를 저장하는 Trie - Trie의 모든 내부 노드는 최대 d개의 자식을 가진다. - Trie는 s개의 리프 노드들을 가진다. - Trie의 높이는 S에서 가장 긴 문자열의 길이와 같다. - Trie의 노드들의 개수는 O(n)이다. - 크기가 m인 문자열에 대한 탐색 실행시간은 O(dm)이다. Trie의 단점 Trie는 각 노드마다 실제로 다음에 올 문자가 없더라고 ..

제어자 / Modifier 클래스, 변수 또는 메서드의 선언부에 함께 사용되어 부가적인 의미를 부여한다. - 접근 제어자 : public, protected, default, private - 그 외 : static, final, abstract, native, transient, synchronized, volatile, strictfp 등 하나의 대상에 대해 여러 제어자를 조합해서 사용하는 것이 가능하다. ( * 접근제어자는 하나만 사용가능, 제어자간의 순서는 상관없지만 주로 접근제어자를 가장 왼쪽에 둔다.) static 멤버변수, 메서드, 초기화 블록 앞에 사용해서 인스턴스와의 관계를 클래스와의 관계로 만들어준다. 인스턴스 멤버를 사용하지 않는 메서드는 static을 고려하는 것이 좋다. 인스턴스를..

OSI 7 Layer 국제 표준화 기구(ISO)에서 개발한 모델 컴퓨터 네트워크 프로토콜 디자인과 통신 과정을 계층으로 나누어 설명한 것 계층화의 장점 시스템이 계층구조를 가질때, 그 계층이 제공하는 서비스의 구현을 변경하는 것이 쉽다. -> 한 계층이 상위 계층에 같은 서비스를 제공하고, 하위 계층의 서비스를 이용하는 한, 어떤 한 계층의 구현이 변하더라도 시스템의 나머지 부분은 변하지 않는다. 계속해서 갱신되는 복잡하고 커다린 시스템의 경우, 시스템의 다른 요소에 영향을 주지 않고 서비스 구현을 변화시킬 수 있다. OSI 7 Layer 모델 애플리케이션 계층 - 네트워크 애플리케이션과 애플리케이션 계층 프로토콜이 있는 계층 - 인터넷 애플리케이션 계층 : HTTP, SMTP, FTP 등을 포함 - D..

문제 programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 [23:59,23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59] 18:00 programmers.co.kr 문제해결방법 크게 착각을 해서 이 문제를 푸는데 엄청 헤맸다. 예를들어 버스가 두 대 온다면 첫 번째 버스 이전에 도착하는 크루들 중에 첫 번째 버스에 못 타고 두 번째 버스에 탈 수도 있는데 이 크루들을 계산을 안해줘서 계속 틀렸다. 기본 아이디어는 아래와 같았다. 1. 셔틀 버스가 도착하는 시간을 기준으로 더 일찍 도..

문제 programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제해결방법 처음에는 이 문제를 HashMap을 사용해서 풀려고 했지만 효율성 테스트에서 시간 초과, 메모리 초과가 발생해서 다른 방법으로 풀었다. 그래서 생각한 방법이 lower bound, upper bound 였다. 가사를 정렬하고 쿼리마다 정렬된 가사에서 lower bound와 upper bound를 계산해준 다음에 두 bound의 차이를 출력해줬다. * 다 풀고나서 보니까 이 문제는 Trie로 푸는 문제인 것 같았다. 추후에 Trie로 푼 코드를 업데이트 해야겠다. [21-02-08] Trie 코드 업데이트 완료 코드 1234567891011..

문제 programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 문제해결방법 장르를 key, 를 저장하는 우선순위 큐를 value로 하는 HashMap과 장르를 key, 장르의 재생횟수를 value로 하는 HashMap 두 개를 사용해서 문제를 풀었다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535..

문제 programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴 programmers.co.kr 문제해결방법 균형잡힌 괄호 문자열을 올바른 괄호 문자열로 바꿔주는 과정을 그대로 짜주었다. 1. u, v를 분리하는 과정 -> '('와 ')'의 개수가 동일하게 되는 부분을 u로, 나머지를 v로 분리한다. 2. 올바른 괄호 문자열을 판단하는 방법 괄호 문자열의 앞에서부터 '('의 개수를 세주며 ')'가 나오면 '('의 개수를 차감해준다. 만약 '('가 나왔는데 '('의 개..