본문 바로가기

분류 전체보기

 (328)
[백준] 1351번 : 무한수열 1351번: 무한 수열 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 🤔 문제분석 다이나믹프로그래밍 + 깊이우선탐색으로 문제를 해결 할 수 있습니다. 깊이 우선탐색을 하게되면 P와 Q가 2이상이기때문에 지수시간이 됩니다. N이 10^12 이므로 O(N)으로는 문제를 해결 할 수 없습니다. 다이나믹 프로그래밍을 처음에는 배열을 N크기만큼 생성했었는데 N의 크기만큼 생성하지않고 딕셔너리 자료구조를 활용하였습니다. 딕셔너리 자료구조도 마찬가지로 메모리 크기가 지수의 크기만큼 생성되기때문에 훨씬 효율적입니다. 💻 코드 import sys from collections import defaultdict input = sys.stdin.readline N, P..
[Spring] WebSocket 머리말 오늘은 Spring 프레임워크를 공부하면서 WebSocket을 사용할 기회가 생겨서 아래와 같이 WebSocket에 관련된 내용을 정리해보았습니다. 실시간 데이터 전송을 필요로 하는 채팅서버를 구현하기위하여 WebSocket을 도입하여 사용해보았습니다. WebSocket을 적용하면서 어떤것들이 있고, 어떻게 사용해야하는지에 대하여 정리해보겠습니다. Http vs WebSocket Http HTTP는 비 연결성이고 매번 연결을 맺고 끊는 과정이 필요하다. ( 요청 - 응답 ) 구조 기본적으로 무상태(Stateless)이므로 연결된 상태를 저장하지 않는다. 실시간으로 바뀌는 정보에 대해서는 지속적으로 요청해야한다. WebSocket TCP Layer위에서 통신하는 계층이다. TCP 처럼 핸드쉐이크를 ..
[백준] 16562번 : 친구비 16562번: 친구비 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 🤔 문제분석 유니온-파인드로 문제를 해결 할 수 있습니다. 친구-친구-친구인 상태는 이미 Parent가 같은 집합들입니다. 그렇기 때문에 처음에 친구관계가 주어진다면 모두 유니온 합니다. 그런다음 친구비를 오름차순으로 정렬한뒤에 해당 친구와 유니온을 하는데, 이미 간선이 연결되어있는 상황이라면 유니온을 하지 않아야합니다. 최소신장 트리의 길이는 구하는 문제처럼 해결하면 됩니..
[백준] 1525번 : 퍼즐 1525번: 퍼즐 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 🤔 문제분석 너비우선탐색, 집합 자료형을 활용하여 문제를 해결하였습니다. “123456780”을 하나의 문자열로 보고 해당문자열을 방문처리 하여 그다음 방문때 방문하지 않도록 합니다. 0의 위치를 파악하고 해당위치에서 갈 수 있는 곳을 선택하여 너비우선탐색합니다. Serialize 와 Deserialize 함수를 두었는데, Serialize 함수는 2차원 배열을 문자열로 바꾸어주는 함수이고, Deserialize 함수는 문자열을 다시 배열로 바꾸어주는 함수입니다. 탐색을 할때에는 2차원 배열을 사용하고, 방문처리를 할때에..
[백준] 6198번 : 옥상 정원 꾸미기 6198번: 옥상 정원 꾸미기 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 🤔 문제분석 스택 자료구조를 활용하여 문제를 해결한다. 스택은 해당위치에서 자기자신보다 낮은 건물이 나올때까지 꺼낸다. 스택에 담긴 자료는 해당 건물포함해서 그 뒤에 볼 수 있는 건물을 담는다. 자기자신보다 큰 건물이기때문에 해당 건물을 포함한 그 뒤에있는 건물 또한 볼 수 있기때문이다. 💻 코드 import sys input = sys.stdin.readline N = int(input()) buildings = list(..
[백준] 17299번 : 오등큰수 17299번: 오등큰수 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 🤔 문제분석 스택 자료구조를 활용하면 문제를 해결 할 수 있다. counter 해당 숫자의 개수를 누적하고, 인덱스로 접근하여 개수의 크기를 판별한다. 만약 리터리에션에서 자기자신보다 작은 counter들은 모두 꺼내고, 작업을 다완료한뒤 stack의 크기를 확인하여 stack이 0보다 크면 스택의 마지막 원소에서 인덱스를 가져오고 그렇지 않다면 -1을 넣는다. 💻 코드 import sys input = sys.stdin.readline N = int(..
[백준] 2014번 : 소수의 곱 2014번: 소수의 곱 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 🤔 문제분석 우선순위큐로 문제를 해결하였습니다. 배열을 순회하면서 중복된 곱을 피하여 곱셈을 하며 N번 만큼 우선순위 큐에서 꺼내고 넣는다. 중복된 곱을 피하기위해서는 Set자료구조를 활용할 수 있으나, 메모리 초과가 발생하여 다른 방식으로 생각해보아야한다. 아래의 표를보면 파란색을 대칭으로 중복된값이 존재하는것을 볼 수 있다. 2x3, 2x5, 2x7이 있다면 추후 3x2, 5x2, 7x2로 나올 수 있기에 자..
[백준] 2143번 : 두 배열의 합 2143번: 두 배열의 합 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 🤔 문제분석 누적합 + 이분탐색 문제로 누적합의 경우의 수를 모두 구한다음에 하나의 누적합을 순회하면서 다른 하나의 누적합의 경우의 수를 정렬한뒤 이분탐색하여 값을 찾아낸다. 이분탐색을 통하여 좌측 index와 우측 index 를 구한뒤에 (우측 - 좌측)을 통하여 해당 값이 몇개가 있는지 알 수 있다. 💻 코드 import sys import bisect..

티스토리툴바