프로그래밍 공방

문제 www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제해결방법 이런 BFS 문제는 보통 방문했는지 체크를 해주기 위해 맵과 동일한 사이즈의 배열을 사용하곤 하는데 이 문제는 동일한 위치를 다시 방문하더라도 다른 종류의 열쇠를 가지고 있을 수 있기 때문에 방문 체크를 위한 배열을 열쇠의 조합만큼 가지고 있어야 한다는게 특징이었다. 열쇠의 조합을 쉽게 체크해주기 위해 a ~ f 까지의 조합을 이진수로 표현해주었다. ( 00000..

문제 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 문제해결방법 로봇이 가로로 있는 경우와 세로로 있는 경우를 다른 배열로 관리해서 문제를 풀었다. 1. 기존 방향을 유지하면서 이동하면 같은 방향의 배열에 기록해주고, 회전을 하면 다른 방향의 배열에 기록해준다. 2. 로봇을 이동할 때, 두 칸 중 하나라도 0이면 이동한다. 3. 위 두 가지 규칙을 지키면서 BFS를 돌며 N, N 칸에 도착하면 그 값을 출력해줬다. 코드 12345678910111213..

문제 programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr 문제해결방법 1. 기둥과 보를 설치할 때, 설치할 수 있는 조건을 만족하는지 확인하고 설치한..

문제 www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제해결방법 이 문제는 랜선의 길이를 기준으로 이분탐색으로 풀었다. left를 자를 수 있는 가장 작은 길이, right를 K개의 랜선 중 최대 길이로 두고 mid(=(left+right)/2)의 길이로 잘라보면서 만약 N개보다 적다면 left를 mid+1로 해서 다시 탐색하고 N개보다 많거나 같으면 mid로 최대 길이를 갱신해준다. 코드 123456789101112131415..

문제 www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 문제해결방법 이 문제는 정확한 키를 비교해서 학생의 줄을 세우는 것이 아닌 선후 관계가 정의된 그래프 상에서 선후 관계에 따라 출력을 해주는(위상정렬) 문제였다. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253package baekjoon; i..

상속 / Inheritance 기존의 클래스를 재사용하여 새로운 클래스를 작성하는것 - 적은 양의 코드로 새로운 클래스를 생성할 수 있다. - 코드를 공통적으로 관리할 수 있다. -> 코드의 재사용성을 높이고 코드의 중복을 제거하여 프로그램의 생산성과 유지보수에 크게 기여한다. 123class 자식클래스 extends 부모클래스 { // ...}cs 부모 클래스 : 상속 해주는 클래스 ( 조상 클래스, 상위 클래스, 기반 클래스 ) 자식 클래스 : 상속 받는 클래스 ( 자손 클래스, 하위 클래스, 파생된 클래스 ) 상속의 특징 - 생성자, 초기화 블럭은 상속되지 않고 멤버만 상속된다. - 자손 클래스의 멤버 개수는 조상 클래스보다 항상 같거나 많다. * 부모 멤버 중 private이나 default가 사..

스패닝 트리 프로토콜 (Spanning Tree Protocol) OSI 2계층 프로토콜로 스위치나 브리지에서 발생하는 루핑을 방지하기 위해 사용되는 프로토콜이다. ( * 스위치나 브릿지 구성에서 출발지부터 목적지까지의 경로가 2개 이상 존재할 때, 한 개의 경로만을 남겨두고 나머지는 모두 끊어두었다가 사용하던 경로에 문제가 발생하면 끊어두었던 경로를 살린다.) Bridge ID 브리지나 스위치들이 통신할 때 서로를 식별하기 위해 하나씩 가지고 있는 번호 Bridge Priority : 0 ~ 2^16-1 까지의 숫자 ( Default = 32768 / 중간값 ) MAC Address : 장비의 고정값 Path Cost 브리지가 얼마나 가까이, 얼마나 빠른 링크로 연결되어 있는지 1000Mbps를 두 장..

문제 programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 문제해결방법 이 문제는 계단 오르기, 포도주 시식 과 비슷한 문제인데 원형으로 되어있다는 점이 달랐다. 그래서 첫번째 집과 마지막 집을 연속으로 털지 않도록 2가지 경우를 나눠서 계산해줬다. 1. 첫 번째 집을 터는 경우 : 이 경우에는 두 번째 집은 털 수 없으며, 마지막 집도 털 수 없다. 2. 첫 번째 집을 털지 않는 경우 코드 123456789101112131415..

문제 programmers.co.kr/learn/courses/30/lessons/12902 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr 문제해결방법 이 문제는 2x1 짜리 타일을 가로, 세로로 사용해서 3xn 직사각형을 채우는 문제였다. 직사각형의 세로는 3인데 세로 3을 만족하면서 직사각형을 만드는 방법은 아래 두 가지 케이스가 있다. 1. 가로가 2이고 세로가 3인 타일 2. 가로가 4 이상인 짝수들 (4, 6, 8 ... ) / 뒤집은 모양도 있다. 따라서 가로가 홀수인 경우는 타일을 채울 수 없다. DP 배열에 가로가 n인 직사각형을 채우는 경우의 수를 저장한다고 가정했을 때 DP[n]을 구하는 방법은 아래와 같다. DP[n] = ( DP[n-2] * 3 ) + ( DP..

문제 programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 문제해결방법 1. 음식을 먹는데 걸리는 시간이 적은 순서대로 정렬한다. 2. 적은 시간부터 ( 음식을 먹는데 걸리는 시간 x 남은 음식의 개수 ) 를 k에서 차례로 빼준다. 3. 만약 ( 음식을 먹는데 걸리는 시간 x 남은 음식의 개수 ) 가 k보다 크다면 남은 음식들을 먹는 도중에 네트워크 장애가 발생한다는 것이므로 남은 시간 k % 남은 음식의 개수를 인덱스로 하는 음식을 찾아준다. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647..