전체 글

[백준/JAVA] 2156번 포도주 시식

규칙에 따라 포도주를 마실 때, 최대로 마실 수 있는 포도주의 양을 구하는 문제 https://www.acmicpc.net/problem/2156 1. 문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있..

[백준/JAVA] 10844번 쉬운 계단 수

동적 계획법을 이용해 계단 수를 구하는 문제 https://www.acmicpc.net/problem/10844 1. 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 2. 문제 접근 1) 첫째 줄에 계단 수의 길이 N을 입력받는다. 2) 자리 수가 1일 때는 1부터 9까지 한개씩이기 때문에 0~9를 인덱스로 가지는 int형 배열에 1부터 9까지 인덱스의 value를 1로 정한다. 3) 자리 수 만큼 반복하면서 끝 수의 위 아래 수의 인덱스에 기존의 값들을 더해주고 마지막에 기존에 있던 수들을 빼주는 형식으로 계단 수를 구할 수 있다. 3...

[백준/JAVA] 1764번 듣보잡

듣도 보도 못한 문제 https://www.acmicpc.net/problem/1764 1. 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 2. 문제 접근 1) 듣도 못한 사람의 수 N과 보도 못한 사람의 수 M을 입력받는다. 2) 듣도 못한 사람과 보도 못한 사람을 입력받는다. 3) 듣도 못한 사람을 입력받을 때 이를 HashSet에 저장한다. 4) 보도 못한 사람을 입력받을 때 HashSet에 존재하면 이를 ArrayList에 저장한다. 5) ArrayList를 정렬한다. 6) 지정된 출력형식으로 출력한다. 3. 코드 import java.io.IOException; import java.io.InputStr..

힙(heap)

완전 이진 트리의 일종 우선순위 큐를 위해 만들어진 자료구조 느슨한 정렬 상태 유지 큰 값이 상위 레벨에 있는 동시에 하위 레벨에도 존재 가능 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 큰 이진 트리 힙 트리에서는 중복된 값 허용 힙의 종류 최대 힙 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 힙 구현 자료구조 배열 사용(표준) 0번 인덱스 사용 x 부모 노드 자식 노드 관계 왼쪽 자식 노드 = (부모 인덱스) *2 오른쪽 자식 노드 = (부모 인덱스) *2 +1 부모 노드 = (자식 인덱스)/2 활용 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서의 작업 스케쥴링 수치 해석..

ktlint

lint : 코드를 분석하여, 프로그램 오류, 버그, 스타일 오류, 구조적 문제점을 확인하는 도구 코딩 컨벤션에 따라 코드를 작성했는지 확인해주는 도구 ktlint: kotlin 개발 환경에서 사용되는 lint 로, 공식 코틀린 코딩 컨벤션과 안드로이드 코틀린 스타일 가이드에 따라 만들어짐 Android lint: 폴더 선택 > 마우스 오른쪽 버튼 > Analyze > Inspect https://pinterest.github.io/ktlint/ ktlint 적용 1) ktlint 공식 홈페이지 > Installation > Integrations 2) 페이지 중간 build.gradle 부분을 보면서 프로젝트에 적용 3) 프로젝트 내 gradle 파일에서 필요한 부분 삽입 configurations d..

[백준/JAVA] 9184번 신나는 함수 실행

간단한 동적 계획법 문제 https://www.acmicpc.net/problem/9184 1. 문제 재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 ..

[백준/JAVA] 9663번 N-Queen

조금 더 복잡한 백트래킹 문제 1 https://www.acmicpc.net/problem/9663 1. 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 2. 문제 접근 1) 첫째 줄에 체스판의 크기 N을 입력받는다. 2) 퀸이 공격할 수 없으려면 한 행에 한개씩 두어야한다. 3) 백트래킹 알고리즘을 사용하여 depth를 행으로 생각, 0부터 N-1까지 반복하며 열을 선택한다. 4) 이때, 열, 2개의 방향의 대각선에 겹치면 안되기 때문에 체크를 하는 boolean형 배열 3개를 선언한다. 5) 열, 2개의 방향의 대각선 모두 겹치지 않을 때 백트래킹 함수를 실행하고 각 체..

[백준/JAVA] 14889번 스타트와 링크

https://www.acmicpc.net/problem/14889 1. 문제 늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sj..