林's

이 문제는 삼성 역량 테스트 기출문제입니다. 당시 기억으로는 버스가 이동할 수 있는 경로의 가짓수를 구하라는 문제였는데. 놀랍게도 하루만에 복기돼서 버스가 파이프로 바뀌었던걸로 기억하고 있습니다. ㅋㅋ 그 때는 버스의 시작모양이 세로일 수도 있고 대각선일 수도 있었던 것 같은데. 이번 문제는 반드시 파이프(=버스)가 가로로 시작하네요~ 여담이지만, 최근 이 문제의 제한시간을 0.5초로 줄였더군요! 그래서 더욱이 DP가 아니면 풀 수 없는 문제가 되고 말았습니다. 파이프1번 문제의 경우에는 BFS로 풀다 시간초과로 털리는 쓴맛을 보았기에,, 이해도 된 겸 포스팅으로 DP적 접근에 관한 아이디어를 나눠보겠습니다. 1). 점화식이란 무엇일까? DP는 흔히, 점화식을 세운다라고 표현하곤 합니다. ...더보기 (..

문제주소: 풀러가기 구사과씨의 방에 미세먼지가 가득하군요! 공기청정기를 가동시키면 윗공기와 아랫공기가 순환을 하고 청정기로 들어간 공기는 깨끗한 공기로 바껴서 나오게 되네요~ 풀고나니 이 문제의 핵심은 아래와 같이 두 가지 였던 것 같습니다. 1. 공기 확산을 하기 위해 BFS 를 활용할 줄 아는가? 2. 공기확산 후 대류를 시키기 위해 배열 인덱스를 잘 다룰 수 있는가? 2번은 아이디어에 의한 것이지만, 1번은 BFS에 적응되어 있지 않으면 힘들 수도 있겠네요! 2번을 해결하기 위해 달팽이수를 풀고나면 더 수월할 것 같습니다. 달팽이수 문제를 풀고난 뒤 이 문제를 풀게 되면, 배열 안의 요소를 회전시키는 게 익숙해질 거테니까요! 각자 풀어보시고 참고를 위해 코드를 올립니다. import java.io...

문제 풀러가기 1). 문제 읽기 상근이라는 친구가 N개의 나라를 모두 여행하고 싶어하는데. 돈을 절약하기 위해 최소한의 항공편을 사용해서 다녀오는 법을 알고싶어 합니다. 2). 문제접근 음.. 최대한 적은 항공편을 사용하면서 모든 나라를 여행한다. 여기서 나라를 그래프의 정점이라 생각하고 항공편을 간선이라고 생각하면, 최소 신장 트리를 구하라는 문제가 되는군요! 최소신장 트리에 대해서는? 아래에서 알려드릴게요~ 3). 풀이방법 두 가지 풀이로 접근할 수 있을 것 같습니다. 1. BFS를 통해 갔던 나라는 다시 가지 않고 모든 나라를 방문해보기. 나라별로 존재하는 항공편을 리스트에 등록해두고 어느 점에서 출발해도 좋으니 1번을 큐에 넣고 큐가 빌 때까지 연결된 모든 정점을 방문해 나갑니다. 최소값을 구해야..

문제보고오기 1. 프렉탈이란 프렉탈이란 fractus 라는 쪼개지다라는 뜻을 갖는 라틴어에서 그 어원을 찾을 수 있습니다. 프렉탈은 위의 번개처럼 자기 자신을 닮은 모양이 끊임없이 반복되는 자기유사성을 띤다는 특징이 있습니다. 우리는 이러한 프렉탈 특징을 갖는 현상을 자연을 통해 손쉽게 확인해볼 수 있습니다. 그리고 몇몇 현상들은 재귀함수를 통해 손쉽게 구현할 수 있습니다. 이번 시간에는 프렉탈과 관련이 있는 BOJ 문제를 통해 재귀함수 사용을 익혀보도록 하겠습니다. 문제에서 주어진 삼각형의 모양을 자세히 살펴보면, 다음과 같이 큰 삼각형 안에 자신을 닮은 작은 삼각형이 위, 왼쪽, 오른쪽으로 나뉘어 계속 반복 되고 있음을 알 수 있습니다. 2. 삼각형의 규칙과 재귀함수 큰 삼각형 안에 작은 삼각형이 1..

문제보고오기 인풋 분석 첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다. n과 소문제 번호는 int로 받아도 충분하지만, k의 경우 최대값이 20!이 된다. 10!만 되도 백만이 넘는데. 20팩토리얼이면..? 이렇게 큰 수는 자바면 long을, C/C++이면 long long ( = __int64 철수 -> 훈이 -> 맹구 짱구 -> 철수 -> 맹구 -> 훈이 짱구 -> 훈이 -> 철수 -> 맹구 짱구 -> 훈이 -> 맹구 -> 철수 짱구 -> 맹구 -> 철수 -> 훈이 짱구 -> 맹구 -> 훈이 -> 철수 철수 ..

문제 주소: 클릭 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 www.acmicpc.net 위의 사진은 지도어플의 벡터 지도 일부를 캡처한 모습입니다. 용산역에서 서울 고속버스 터미널을 가고싶을 때, 우리는 일반적으로 출발지점을 용산역, 도착지점을 터미널로 두고 검색을 하게 됩..