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

1. 문제 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 2. 풀이 과정 1. 사이클 찾기(DFS) 모든 경로를 돌다가 아래 두 조건을 만족하면, 사이클이므로 return true를 하고 사이클 요소에 true표시 1) 방금 전에 방문한 노드 != 다음에 방문할 노드 2) 이미 방문한 노드 dfs로 돌아가다가 출발점을 마주치면 return false로 사이클 요소 true표시를 종료한다. 2. 사이클에서부터 거리 찾..

1. 문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 2. 풀이 과정 1. 정렬 알고리즘이 필요없다. 삽입되는 값이 제일 작기 때문에, 순서대로 넣어주면 정렬된 상태이다. 차례대로 list에 add하면 내림차순으로 정렬되므로 뒤에서부터 탐색하도록 for문을 작성했다. 2. LinkedList vs ArrayList 순서대로 조회하는 일이 많으므로 ArrayList가 훨씬 효율적이다. 이 문제에서는 LinkedList로 풀이..

1. 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 2. 풀이 과정 1. 순서 찾기 : 위상정렬 2. 정렬이 안 되는 경우는 자신 앞에 있는 노드 수가 0이상인 노드만 남았을 때이다. 이 경우, 사이클이기 때문에 주어진 조건을 모두 만족하는 순서를 찾을 수 없다. import java.io.*; import java.util.*; public class boj2623 { public static void main(St..

1. 문제 https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 2. 풀이과정 방문체크를 3개씩 하는 DFS 문제이다. 처음에 N, M이 5이하라서 방문체크를 비트마스킹으로 풀었는데, boolean으로 풀었을 때가 1.5배나 빨랐다. 비트마스킹은 배열이 아닌 int로 풀어서 2차원 배열 1차원 배열 전환하는 연산이 많아서 느렸던 것 같다. +) 벽세우기를 한 후, 1.5배 더 빨라졌다. import java.io.*; import ..

1. 문제 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 2. 풀이과정 이 문제는 dfs나 bfs 둘 중 하나로 풀 수 있을 것 같은데, dfs를 선택한 이유는 n, m의 최대 크기가 100으로 작은 편이라 stack이 최대 100x100개정도 밖에 안 쌓이며, 코드도 더 짧기 때문이다. import java.util.*; import java.io.*; public class boj1743 { sta..

1. 문제 https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 2. 풀이과정 1. 부모 정보를 배열에 받아서 저장한다. 2. 뒷번호부터 검사(leaf노드부터 검사하기 위함) 1) 해당 숫자를 부모로 가진 자식들의 직간접적으로 이어진 자식들의 수를 구해서 정렬한다. 2) 자식들 중 아래에 있는 자식들이 많은 것부터 차례로 순서를 부여한다. 3) 순서 + 아래에 있는 자식들의 수가 가장 큰 값을 해당 숫자에 기록하며 업데이트 해간다. import java...

1. 문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 2. 풀이과정 1. 파티 정보를 Queue에 넣고, 결과는 Queue의 사이즈를 출력한다. 2. 진실을 아는 사람은 집합(set)으로 관리한다. 3. Queue에서 파티 하나를 꺼내서 거짓말 할 수 있는지 check 1) 파티의 참여자 중 set에 포함된 사람이 있으면 해당 파티 참여자도 set에 넣는다. 2) set에 한 명도 포함되지 않으면, 다시 queue에 넣는다. 4. 진실을 아는 사람 ..

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

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://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(..