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

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번째 작업부터 차례대로 돌면서, 자신의 뒤에 실행할 곳에 수행 시간을 더해준다.이때, 선행 요소가 여러 개 있는 작업은 수행 시간이 가장 긴 선..

1. 문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 2. 풀이 과정 한 장소에서 여러 곳으로 뻗어나갈 수 있기 때문에, 단순 dfs나 bfs로는 풀리지 않는다. 한 장소에 방문하면, 지금까지 방문한 장소를 모두 고려해 갈 수 있는 장소를 탐색한다. 방문한 장소를 찾아서 4방위 탐색해서 dfs로 들어가면 된다. +) 중복 방지를 위해 visited 배열을 사용한다. 비트마스킹으로 경로 방문 체크를 한다. import java.io.*; pub..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 2. 풀이과정 dfs문제 + 문자열 정렬 1) 문자열을 정렬하기 위해서 지역 이름들을 하나의 문자열로 concat해서 사용 2) 사전순 정렬 3) 공항 이름이 모두 3자리이므로, 3개씩 잘라서 배열에 담아서 반환 import java.util.*; class Solution { static int N; static A..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 2. 풀이과정 0~distance 범위를 이진탐색을 통해 답을 찾는다. 매 loop마다 중간값보다 작으면 합치고, cnt를 센다. 1) cnt가 n개 이상이면, 값을 줄여야 하므로 right = m-1 2) cnt가 n개 이하면, 값을 늘려야 하므로 left = m+1 3) cnt == n이 되는 중간값은 여러 개 있을 수 있다. 그 중 ..