분류 전체보기
[BaekJoon] 백준 4358번 생태학
[BaekJoon] 백준 4358번 생태학 🎈문제 https://www.acmicpc.net/problem/4358 💬설명 문제에는 트라이 알고리즘이라고 적혀있었지만 dictionary로만 풀어도 풀리는 문제였다. 포인트 데이터가 크기 때문에 시간을 최대한 줄여줘야 했다. (pypy로 하지 않고 python으로 채점해도 되긴 함) 입력이 언제 끝나는지 따로 표시해주지 않는다. 입력이 끝났는지 따로 체크해줘야 함 출력 시 소수점 4째자리까지 반올림 해서 출력하라고 하는데 그냥 round만 쓰면 50 -> 50.0000으로 출력하지 않기 때문에 %.4f로 출력해줘야 한다. 👩💻코드 # BaekJoon4358.py import sys input = sys.stdin.readline dic = {} sum_t..
[BaekJoon] 백준 2170 선 긋기
[BaekJoon] 백준 2170번 선 긋기 🎈문제 https://www.acmicpc.net/problem/2170 💬설명 스위핑 기법으로 푸는 문제라고 한다.스위핑 기법이란 말 그대로 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것이라고 보면 된다. 풀이 과정 시작점을 기준으로 sort한다. 다음 line이 이전 line에 포함되는 경우, 일부가 겹치는 경우, 아예 겹치지 않는 경우 이렇게 3가지로 나눠서 생각한다. 주의 데이터의 크기가 큰만큼 시간초과가 계속 났다. 해결책 import sys -> input = sys.stdin.readline arr 속에 line들을 tuple로 저장 (iteration 도는 속도가 tuple이 빠르다고...?) pypy로 채점 👩💻코드 # Ba..
[Spring] 입문4
회원관리 예제 - 웹 MVC 개발 이번 부분은 타임리프라는 템플릿엔진으로 간단하게 화면들을 추가하는 부분이다. 어렵지 않아서 금방금방 습득할 수 있었다. 개발 완료 후 파일 구조 회원 웹 기능 - 홈 화면 추가 1. HomeController.java 추가 package hello.hellospring.controller; import org.springframework.stereotype.Controller; import org.springframework.web.bind.annotation.GetMapping; @Controller public class HomeController { // localhost:8080/ 로 들어오면 가장 기본적으로 호출될 부분 @GetMapping("/") public..
[Spring] 입문3
스프링 빈과 의존관계 스프링 빈에 대해 알기 전에 IOC와 DI에 대해 먼저 알아야한다. 아직은 명확히 와닫지 않아서 쉽게 설명해놓은 링크만 첨부한다. 좀더 명확하게 알게되면 새로 포스팅해야지! 간단하게 말하면 이제 controller에서 view에 화면을 뿌려주는 작업을 할건데, controller에서는 service를 통해서 회원가입을 하고 데이터를 조회할 수 있다. 이렇게 되는 걸 서로 의존관계가 있다고 하고(controller가 service를 의존하고 있다.) 이제 이 과정을 스프링으로 구현해볼 것이다. 오늘 개발 후 폴더 구조 (보이지 않는 부분은 변경 사항 없음) 스프링 빈을 생성하는 방법 스프링 빈이란? Spring IoC 컨테이너가 관리하는 자바 객체를 빈(Bean)이라는 용어로 부른다...
[BaekJoon] 백준 21609번 상어중학교
[BaekJoon] 백준 21609번 상어중학교 🎈문제 https://www.acmicpc.net/problem/21609 💬설명 bfs, 구현 문제 따져줘야하는 조건이 많아서 까다로웠다. python으로 채점하면 시간초과가 나서 pypy로 채점해줬다. 좀더 깔끔하게 풀 수 있을 것 같은데 문제 잊었을 때 쯤 다시 풀어봐야겠다. 👩💻코드 # BaekJoon21609.py from collections import deque import copy N, M = map(int, input().split()) result = 0 dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] arr = [[] for _ in range(N)] for i in range(N): arr[i] = list(ma..
[Programmers] 더 맵게
[Programmers] 더 맵게 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42626 💬설명 처음에는 PriorityQueue로 풀었는데 시간초과가 나서 heapq를 이용해 풀었다. 둘다 push pop이 O(logn)인걸로 알고 있는데 의문이었다. 찾아보니까 PriorityQueue는 heapq의 함수들을 이용해서 만들어졌지만 thread-safe한 대신 속도가 느리다고 한다. (참고) heapq로 우선순위 고려해서 풀어준다. 👩💻코드 # 시간 초과 코드 from queue import PriorityQueue def solution(scoville, K): answer = 0 pq = PriorityQueue() # priority queue..
[Programmers] 주식가격
[Programmers] 주식가격 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42584 💬설명 for문을 두번 돌면 되는 문제 처음부터 끝까지 돌면서 각각에 대해 뒤에 있는 price들을 체크해준다. 데이터 크기도 그렇게 크지 않고 O(nlogn)에 풀수 있어서 효율성도 통과했다. 스택으로 풀면 시간이 더 단축된다. (두번째 풀이) (약 100ms -> 약 20ms) 👩💻코드 def solution(prices): answer = [] for index, price in enumerate(prices): answer.append(0) for i in range(index + 1, len(prices)): answer[-1] += 1 if price..
[Programmers] 다리를 지나는 트럭
[Programmers] 다리를 지나는 트럭 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42583 💬설명 처음에 다리 길이 만큼 [0, 0, ... 0] 이렇게 만들어주고 트럭이 올라가고 지나가는 것을 pop과 append로 구현해줬다. 입출력이 순서가 있는 문제이므로 스택/큐 문제! 👩💻코드 def solution(bridge_length, weight, truck_weights): answer = 0 bridge = [0 for _ in range(bridge_length)] weight_sum = 0 while bridge: answer += 1 weight_sum -= bridge.pop(0) # 다음 대기 트럭이 올라갈 수 있는지 무게 체..