본문 바로가기

Tech

[백준 1800] 인터넷 설치 (Java) 문제 링크 : www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 풀이 이분 탐색 + 다익스트라 응용 문제로 개인적으로 많이 어렵게 느껴졌던 문제였다. (나중에 다시 한 번 풀어볼만한 문제) 참고한 블로그에 설명이 잘 나와 참고하여 풀었다. [참고] - batory.tistory.com/371 - justicehui.github.io/usaco/2019/07/12/BOJ1800/ 코드 import java.io.Buffe..
[백준 16639] 괄호 추가하기 3 (Java) 문제 링크 : www.acmicpc.net/problem/16639 16639번: 괄호 추가하기 3 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 풀이 dfs로 완탐하는 방식으로 시도하다가 경우가 너무 많아서 자력으로 풀지 못했다. 다른 분의 블로그를 참고하여 해결할 수 있었다. DP 방식을 통해 풀이가 가능했는데, 2차원 배열을 생성하고 i번 째부터 j번 째 숫자들을 포함한 연산 결과들의 최솟값, 최댓값을 구했다. 최종적으로 최댓값을 구하는 것이지만, 연산 숫자가 음수 * 음수 인 경우 최댓값의 후보가 될 수 있기 때문..
[백준 17780] 새로운 게임 (Java) 문제 www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 풀이 크게 체스판에 대한 데이터, 체스말(Node)에 대한 데이터, 쌓여있는 체스말에 대한 데이터를 어떻게 저장할 것인지 고민했다. - 체스판에 대한 데이터(빨, 파, 흰)는 2차원 int 배열로 입력 받는 그대로 저장한다. - 체스말에 대한 데이터는 x, y좌표 값과 방향 값을 필드 데이터로 갖는 Node 객체를 생성해 ArrayList에 저장하였다. (방향 별 이동을 쉽게 하기 위해 dir_x, dir..
[백준 10021] Watering the Fields (Java) www.acmicpc.net/problem/10021 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 풀이 N개의 필드 간 수로 파이프를 설치하는데, 모든 필드가 연결되도록 하는 최소 비용을 구하는 문제. 즉, 모든 필드를..
[백준 15591] MooTube (Silver) (Java) www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 풀이 그래프 문제라고 2차원 배열을 사용하면 시간 초과가 발생한다. 불필요한 연결을 탐색하기 때문에 ArrayList를 담는 배열을 만들어 입력 받은 연결만 탐색하도록 구현하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor..
[프로그래머스] 카카오 블라인드 리쿠르트 2020 - 블록 이동하기 (Java) https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 문제 설명 로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 무지는 0과 1로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된..
[프로그래머스] 카카오 윈터 인턴십 2019 - 징검 다리 건너기 (Java) https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 카카오 초등학교의 니니즈 친구들이 라이언 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. 라이언 선생님은 니니즈 친구들이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다. 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다. 디딤돌의 숫자가 0이 되면 더 ..
[데이터베이스] 정규화(Normalization)와 역정규화(Denormalization) 정규화(Normalization)란? 관계형 데이터베이스의 설계에서 중복을 최소화하게 데이터를 구조화하는 프로세스 (위키백과) 정규화의 필요성 불필요한 데이터를 제거, 데이터의 중복을 최소화 하기 위해서 데이터베이스 구조 확장 시 재디자인을 최소화 다양한 관점에서의 query를 지원하기 위해서 무결성 제약조건의 시행을 간단하게 하기 위해서 각종 이상 현상(Anomaly)을 방지하기 위해서, 테이블의 구성을 논리적이고 직관적으로 한다. 데이터베이스를 잘못 설계하면 불필요한 데이터 중복으로 인한 공간낭비를 넘어 부작용을 초래할 수 있다. 이러한 부작용에는 삽입이상, 갱신이상, 삭제이상이 있다. 삽입 이상 (Insertion Anomaly) 새 데이터를 삽입하기 위해 불필요한 데이터도 함께 삽입해야 하는 문제..

티스토리툴바