네발로 코딩하는 포메라니안

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 - bfs + 비트마스킹 - 입력이 8개이하이므로 비트마스킹(32bit)을 사용 class Solution { int n, answer; public void bfs(int k, int[][] dungeons, int visit, int cnt){ answer = Math.max(answer, cnt); for(int i=0; i

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 - 끊었을 때 한 쪽 전력망 개수만 cnt해서 (전체)-cnt와 차이를 구한다. => dfs를 시작할 때, 제거할 선과 연결된 노드는 방문처리하여 다시 방문하지 않게 함으로써 "끊어짐"을 고려한다. - n-1개의 선으로, 전체 가능한 간선(n*(n-1))에 비해 매우 적은 편이므로 LinkedList로 구현 import java.util.*; class Solution ..

1. 문제 https://www.acmicpc.net/problem/1917 1917번: 정육면체 전개도 세 개의 입력 데이터가 주어지며, 각각의 입력 데이터는 여섯 개의 줄로 이루어져 있다. 각 데이터는 여섯 개의 줄에 걸쳐 여섯 개의 숫자가 빈 칸을 사이에 두고 주어진다. 숫자는 0 또는 1로 이 www.acmicpc.net 2. 풀이 과정 주사위의 위치와 번호를 이용하는 아이디어는 다른 코드를 보다가 얻어서 아쉽지만, 코드는 보지 않았기에 같은 아이디어라도 다르게 구현할 수 있었던 것 같다. 아이디어를 한 줄로 정리해보면, 원래의 주사위를 전개도로 펼친다고 볼 수 있다. 1. 주사위 위치에 따라 1~6번호를 저장하는 배열을 만든다. 2. 위로, 왼쪽으로, 오른쪽으로, 아래로 굴려가면서 배열 정보를 ..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 1. 균형 잡힌 괄호 문자열 + 올바른 괄호 문자열을 동시에 확인한다. - 열린 괄호가 오면 +1, 닫힌 괄호가 오면 -1 => 중간에 한 번이라도 음수가 되면, 올바른 괄호 문자열이 아니다. 2. u가 올바른 괄호 문자열인지에 따라, 다르게 처리하고 재귀함수를 돌린다. - '올바른'이면, u + 재귀(v) - '올바른'이 아니면, ( 재귀(v) ) + 뒤집은 u cla..

1. 문제 https://www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 2. 풀이 과정 1. '0'으로 벽 세우기 2. 1~9까지 같은 수 dfs탐색 2-1. 주변에 자신보다 작은 값이 있으면 수영장 X 2-2. 주변에 자신보다 작은 값이 없으면 물 채우기 실행 예시 1. 1을 찾으면서 방문한 곳은 check한다. 2. 방문한 곳 주변이 자기보다 작은 값이 없다면, 1) 주변 값들인 5, 9중에 작은 5에 맞춰 채우고 방문 체크를 다..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 1. game_board의 빈칸과 table의 퍼즐을 dfs로 탐색 1) 각 덩어리의 좌표들을 저장 2) 각 덩어리의 개수를 저장 3) 각 덩어리의 시작값 저장 2. 평행이동을 이용하여 같은 블럭인지 확인 & 회전을 반복한다. *회전은 블럭 하나하나를 생각하지 않고, 판 전체를 돌린다는 생각으로 좌표를 이동시켰다. import java.util.*; class Block{..

1. 문제 https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 2. 풀이 과정 1. 자신의 오른쪽만 보면서 업데이트한다. 2. 기울기가 증가하는 지점만 count한다. import java.io.*; import java.util.*; public class Boj1027 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(..

1. 문제 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 2. 풀이 과정 1) 지도의 색깔 정보 = 2차원 배열 2) 말의 위치 = 2차원 연결 리스트 배열에 '말 번호'를 저장 => 0번부터 말을 순서대로 이동시킨다. import java.io.*; import java.util.*; public class Boj17780 { static int N, K, map[][], nodes[][];//node정보 static LinkedList n..

1. 문제 https://www.acmicpc.net/problem/23791 23791번: K번째 음식 찾기 1 한식 [1..3], 양식 [1..3]을 오름차순으로 나열하면 1 2 3 5 8 10이고 여기서 세 번째로 맛있는 음식 맛은 3이므로 첫 번째 질의 정답은 양식 2번이다. 한식 [1..3], 양식 [1..4]를 오름차순으로 나열하면 www.acmicpc.net 2. 풀이 과정 병합 정렬 + 이진 탐색 문제이다. 여기서 시간 단축을 위해 누적합 개념을 추가적으로 사용했다. 예를 들어, 입력이 아래와 같이 주어진다면 4 1 5 10 15 2 3 8 9 병합 정렬하면서 한식, 양식 수를 세서 누적합을 구해놓고 이진탐색할 때 이용한다. 1 2 3 5 8 9 10 15 한식 1 1 1 2 2 2 3 4..

1. 문제 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 2. 풀이과정 풀이방법은 2가지가 있다. 위상 정렬 문제를 많이 접해보지 않아서 헤맸던 문제다. 1. 위상정렬 선행 요소를 입력 받을 때, 선행요소에 '나'를 추가하는 방식으로 한다. 즉, 모든 노드들의 후행요소로 저장해주는 것이다. 0번째 작업부터 차례대로 돌면서, 자신의 뒤에 실행할 곳에 수행 시간을 더해준다.이때, 선행 요소가 여러 개 있는 작업은 수행 시간이 가장 긴 선..