전체 글

[baekjoon 11659] 구간 합 구하기 4 (누적합) (C++)

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 기본적인 누적합 문제이다. 누적합 문제를 최근에 안 풀었더니 투 포인터로 접근했다가 시간 초과가 났다. 입력을 받으면서 앞의 인덱스의 누적 합을 따로 저장해준다. 그러면 start와 end의 구간 합을 sum[end] - sum[start-1]의 식으로 O(1)에 구할 수 있다. 여기에 쿼리가 추가되어 값이 수정되면서 구간 결과을 구하려면 세그먼트 트리 문제로 된다. 수많은..

1. 인터넷 네트워크

- 인프런 김영한 님의 '모든 개발자를 위한 HTTP 웹 기본 지식'을 수강 후 정리한 내용입니다. 1. IP란 - Internet Protocol로 인터넷에서 사용하는 프로토콜이다. - 지정한 IP 주소로 데이터를 전달하고, 패킷이라는 통신 단위로 전달된다. - 내 컴퓨터에서 상대 컴퓨터(서버)로 인터넷을 통해 통신할 때 패킷을 전달할 때 사용된다. - IP 프로토콜의 특징은 다음과 같다. 비연결성 해당 패킷을 받을 대상이 없거나, 서비스 불능 상태여도 패킷이 전송된다. 비신뢰성 전달 도중 패킷이 손실될 수 있다. 순서대로 패킷을 전송했지만 순서대로 도착하지 않을 수 있다. 프로그램 구분 불가 포트 정보가 없기 때문에 해당 서버에서 여러 개의 어플리케이션 중 어떤 애플리케이션에 도달해야 할지 모른다. ..

[프로그래머스 카카오 블라인드 채용 2021 4번] 합승 택시 요금 (다익스트라, 플로이드와샬) [C++]

https://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 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 밤늦게 귀가할 ..

[baekjoon 17298] 오큰수 (스택) (C++)

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 현재 수의 오른쪽에 있는 수 들 중 나보다 큰 가장 왼쪽의 수를 출력하는 문제이다. 즉, 1 9 8 10 이면 1의 오큰수는 9(큰 수 중 바로 왼쪽), 9의 오큰수는 10, 8의 오큰수는 10, 10의 오큰수는 없기에 -1을 출력하면 된다. 또한 입력값의 범위는 백만으로, 매 수마다 오른쪽 범위로 반복문을 돌려서 나보다 큰 수를 찾는 2중 for문을 이용하면 시간 초과가 날 것이다. 따라서, 스택 자료구조..

[baekjoon 15961] 회전 초밥 (슬라이딩 윈도우, 두 포인터) (C++)

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만이므로 N^2은 당연히 시간 초과가 난다. 이렇게 K개의 수를 한번 훑어야 하는 경우 보통 슬라이딩 윈도우를 이용하면 O(N)만에 연산을 마칠 수 있다. 또한, 나는 가짓수를 관리해줄 때 map 자료..

[baekjoon 2021] 최소 환승 경로 (BFS, 0-1 BFS, 다익스트라) (C++)

https://www.acmicpc.net/problem/2021 2021번: 최소 환승 경로 첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발 www.acmicpc.net 지하철 노선과 그 노선을 지나는 역의 개수가 주어진다. 이 정보를 갖고 어떻게 그래프화 시켜서 이동을 할까 고민을 했는데, 해당 역을 지나는 노선 정보와 노선을 지나는 역, 이 두 개를 저장했다. 10 3 1 2 3 4 5 -1 // 1번 노선 9 7 10 -1 // 2번 노선 7 6 3 8 -1 // 3번 노선 1 10 의 경우 route벡터에는 노선 번호에 해당하..

[프로그래머스 LV3] 단어 변환 (BFS, DFS) [C++, JAVA]

https://programmers.co.kr/learn/courses/30/lessons/43163?language=java 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 단어 집합이 주어지고, 시작 단어에서 타깃 단어까지 몇 번만에 바꿀 수 있는지 리턴하는 문제이다. 그 대신, 단어는 한 글자만 바꿀 수 있다. 나는 처음에 DFS+백트래킹으로 단어의 문자 알파벳 하나하나를 바꿔가면서 ex) abc bbc cbc dbc ebc... 만약에 그 단어가 단어 집합에 ..

Servlet이란?

네이버 부스트 코스 웹 백엔드 과정을 공부하고 정리한 내용입니다. 0. Java Web Application이란 - WAS에 설치되어 동작하는 어플리케이션이다. - 자바 웹 어플리케이션에는 HTML, CSS, 이미지, 자바로 작성된 클래스(Servlet 클래스 포함, package, 인터페이스 등), 각종 설정 파일 등이 포함된다. 1. 서블릿이란? - 자바 웹 어플리케이션의 구성요소 중 동적인 처리를 수행하는 Java 클래스이다. - WAS에서 동작하며 HttpServlet 클래스를 상속받아야 한다. - JSP와 서블릿을 효율적으로 이용하려면 웹 페이지 구성(JSP) + 복잡한 프로그래밍(서블릿)으로 구현한다. 2. 서블릿의 생명 주기 - init() 1. 해당 URL로 클라이언트가 서버로 요청을 하면..