https://www.acmicpc.net/problem/2580 문제조건스도쿠판을 채우자각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.접근방법 문제를 보자마자 떠오른 생각은 N-Queen 문제와 상당히 유사한 문제라는 생각 이었다. 물론 Brute Force로 모든 경우의 수를 탐색해서 구할 수도 있겠지만, O(2^n) 이상의 시간소요로 시간초과가 날 것이 분명했고, N-Queen문제와 같이 백트래킹으로 접근했다.유망한지 판단하고, 유망하다면 DFS를 진행하는 백트래킹 방식에서 시간단축이 됨을 인지하고, 가로, 세로, 3x3 크기의 칸에서 같은 숫자가 하나도 없는지 체크하고 그..

2024.04.30 - [Spring/대용량 트래픽] - Redis 다양한 데이터 타입 알아보기 Redis 다양한 데이터 타입 알아보기2024.04.05 - [Spring/대용량 트래픽] - Redis CLI 실습lsdiary.tistory.com이전까지 Redis CLI를 통해서 다양한 데이터 타입을 알아보고 명령어들도 알아봤다.이번 글은 Java에서는 어떻게 사용하는지 알아보겠다. JedisJava + Redis로 줄여서 Jedis라고 부른다. 우선 Java로 실습하기 위해서 개발환경툴인 InteliJ를 사용해서 새로운 프로젝트를 만들고 시작해보겠다. https://redis.io/docs/latest/develop/connect/clients/java/jedis/ Jedis guideConnect ..

2024.04.05 - [Spring/대용량 트래픽] - Redis CLI 실습 Redis CLI 실습2024.04.05 - [Spring/대용량 트래픽] - Redis,Docker 설치하기와 수많은 에러 Redis,Docker 설치하기와 수많은 에러 도커 컨테이너 기반으로 Redis를 설치해보겠다. https://hub.docker.com/_/redis redis - Official Image | Dolsdiary.tistory.com이전글에서는 Redis CLI에서 간단한 명령어들을 알아봤다.이번 글은 Redis가 저장할 수있는 다양한 데이터 타입에 대해 알아보겠다.NoSQLKey/Value 구조의 저장을 지원한다. 저장 가능한 데이터 타입이 의미하는 것은 Value이다.Key : binary / t..

https://www.acmicpc.net/problem/17136 문제조건  1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류의 색종이가 있다.각 종류마다 5개씩 가지고 있다. 10×10인 종이에 색종이를 붙인다. 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다., 0이 적힌 칸에는 색종이가 있으면 안 된다. 필요한 색종이의 최소의 개수?모두 덮는것이 불가능한 경우 -1을 출력 접근방법 하나씩 범위를 넓혀주는 BFS 방법을 써야하나,,? 라는 생각이 들었지만 정형화 시킬 방법이 떠오르지 않았다. 따라서 DFS측면으로 접근했는데, 한변의 길이가 1일때부터 5일때 까지 하나씩 판단해야하고, 그럴려면 중복을 방지 하기위해 visited 배열을 활용해야한다. 이 ..

https://www.acmicpc.net/problem/2254 문제조건 감옥의 좌표 (px,py)가 주어진다.담 기둥의 좌표들이 주어진다.감옥과 담 기둥은 일직선상에 위치할 수없다.각각의 담은 감옥을 완전히 감싸야 하고, 담 안에 (부분적으로라도) 포함되는 담이 있다면 이러한 담도 완전히 감싸야 한다겹치지 않는 최대의 중첩된 담의 겹 수?접근방법 처음보는 유형의 문제라 생각만 2시간이상하다가 검색을 통해 도움을 얻었다,,,,역시 구현이나 어떤 알고리즘을 쓰는가 보다는 기하학적으로 접근해야하는 문제였다.정말 오랜만에 다시 보는 벡터의 외적이 쓰인다니,,, 역시 배운게 다 쓰이긴 한다. Convex Hull 알고리즘 이 문제에서 사용된 알고리즘이다.convex hull이 그래서 대체 뭐냐? 2차원 좌표 ..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제조건 랜선의 개수 K, 그리고 필요한 랜선의 개수 N개를 만들 수 있는 랜선의 최대 길이를 구하라. K개를 잘라서 모두 N개의 같은 길이의 랜선으로 만든다. 접근방법 조건에 따른 참, 거짓이 두구간으로 명확히 나뉘므로, 매개변수 탐색이 떠올랐다. 다만 너무 만만하게 보고 들어간건지 진짜 많이 틀렸다,,, 틀린원인 질문 게시판을 찿아 보면서 여러가지 반례들을 보고 다..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제조건 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이는? 접근방법 시간제한도 타이트하고, 입력값도 크게 주어지길래, 단순히 for문 두번 돌려서 O(n^2) 으로 시간이 걸리게 된다면 당연히 시간초과가 날 것이라고 생각했고, 문득 저번에 이런 비슷한 문제를 푼 경험이 떠올랐다. 2024.03.21 - [Algorithm/구현, 시뮬레이션..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 문제조건 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있다. 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 숫자를 최대로 뽑는 경우, 뽑는 숫자들을 출력하라. 접근방법 모든 경우의 수를 따져서 비교해줄려고 DF..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제조건 부모 자식들간의 관계가 주어졌을때, 계산하고자 하는 두사람의 촌수를 구해라 접근방법 트리 모양 구조를 탐색하는 그래프 탐색 방법으로 접근했다. 근데 촌수 이므로 cycle이 생길 일은 없다. 따라서 각 노드를 양방향 연결해주고 DFS로 탐색해줬다. 아버지의 형제들과 나와의 관계는 3촌으로 분류할 수 있는데, 이를 계산하는 방식은 나 → 아버지(1촌) → 할아버지(2촌)..

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 문제조건 시작점, 시작방향, 세대가 주어진다. K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다. 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다. 접근방법 같은 모양이 계속해서 반복해서 추가되는 것을보고, DP아니면, 재귀의 형식으로 풀 수 있지 ..