본문 바로가기

전체 게시글376

[BaekJoon] 백준 알고리즘 2003번 / 수들의 합 2 / 투포인터 / Python 간단한 투 포인터 알고리즘을 이용하여 풀 수 있습니다. 시작점(start)과 끝점(end)을 이용하여 구간합(interval_sum)을 구하며 end를 이동시키며 구간합이 M과 같아지면 카운트합니다. start를 이동시키면서 구간합(interval_sum)도 갱신합니다. 이 알고리즘의 시간 복잡도는 O(N)입니다. """ 1. 아이디어 - 투 포인터를 통한 계산 2. 시간복잡도 - O(N) : 10,000 < 2억개!, 출력 가능 3. 자료구조 - 수열 저장 int[] - 합계 저장 int - 경우의 수 저장 int """ import sys input = sys.stdin.readline N, M = map(int, input().split()) A = list(map(int, input().split.. 2023. 3. 30.
[Java] 뷰(View)를 포함한 모델 데이터에 대한 추상화를 담당하는 ModelAndView 구현하기 Controller의 반환값은 String이다 public class HomeController implements Controller { @Override public String execute(HttpServletRequest req, HttpServletResponse resp) throws Exception { QnaDao qnaDao = new QnaDao(); req.setAttribute("questions", qnaDao.selectAll()); return "home.jsp"; } } 위 Controller의 excute() 메서드 반환 값 String을 받아 서블릿에서 JSP로 이동한다. 만약 JQuery의 ajax() 함수를 활용해 서버에 요청을 보낸다면? 응답 데이터 타입은 JSON.. 2023. 3. 29.
[BaekJoon] 백준 알고리즘 2559번 / 수열 / 투포인터 / Python 문제 접근방법 해당 문제는 연속적인 부분합 중에서 가장 큰 값을 찾는 문제이다. 가장 간단하게 시간복잡도 O(N^2)의 알고리즘으로 구할 수 있다. 그 방법은 완전 탐색 방법으로, 각 구간을 시작하는 인덱스 i와 끝나는 인덱스 j에 대해, i부터 j까지의 합을 구해서 가장 큰 값을 찾는 것이다. 이를 위해서는 2중 반복문을 사용하여 모든 구간에 대해 합을 구해야 한다. 하지만 해당 문제의 N은 100_000 이하로 주어지며, 시간복잡도 O(N^2)이므로 시간초과로 이어질 수 있다.( 2억개 미만이면 가능) 소스 코드 """ 1. 아이디어 - 투포인터 활용 - for문으로, 처음 K개 합산 - 다음 인덱스 더해주고, 이전 인덱스 빼주면서 최대값 갱신 2. 시간복잡도 - 완전 탐색일 경우 O(N^2) -> .. 2023. 3. 28.
[H2 DB] insert시 auto increment인 sequence 값을 바로 받아 오는 법 DAO 메서드 지금까지 DAO(Data Access Object) 클래스의 메서드를 아래와 같이 설계해왔다. public void insert( Ans ans ) { ... } public Ans select(String answerId ) { ... } public List selectAll(String questionId) { ... } 테이블 구조 DTO(Data Transfer Object) 클래스인 Ans의 테이블 구조는 아래와 같다. CREATE TABLE ANSWERS ( answerId bigintauto_increment, writervarchar(30)NOT NULL, contentsvarchar(5000)NOT NULL, createdDatetimestampNOT NULL, quest.. 2023. 3. 28.
[Java] 톰캣(WAS)에서의 URL 패턴과 관련된 이슈 / 자동으로 마지막 슬래시(/)가 추가되어서 리다이렉트 되는 경우 이슈 설명 제대로된 url 맵핑을 했는데도, 에러가 발생하는 경우 예) http://localhost:8080/qna 로 요청시 http://localhost:8080/qna/ 로 리다이렉트 되는 경우 URL 매핑 클래스 public class RequestMapping { private static final Logger logger = LoggerFactory.getLogger(DispatcherServlet.class); private Map mappings = new HashMap(); void initMapping() { mappings.put("/", new HomeController()); mappings.put("/users/form", new ForwardController("/user/.. 2023. 3. 26.
[BaekJoon] 백준 알고리즘 4963번 / 섬의 개수 / DFS / Python import sys sys.setrecursionlimit(10**6) dr = [-1, -1, -1, 0, 0, 1, 1, 1] dc = [-1, 0, 1, -1, 1, -1, 0, 1] def dfs(a, b): global island, visited visited[a][b] = 1 for dir in range(8): nr = dr[dir] + a nc = dc[dir] + b if nr >= 0 and nr = 0 and nc < w: if arr[nr][nc] == 1 and visited[nr][nc] == 0: dfs(nr,nc) while True: island = 0 w, h = map(int,input().split()) if w == 0 and h == 0 : .. 2023. 3. 25.

티스토리툴바