잡담연구소

2019 카카오 개발자 겨울 인턴십 5번 문제 징검다리 건너기 programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr IDEA의 흐름 1. 보자마자 될 때까지 while 문 돌면서 stones에서 하나씩 빼주면 되지 않나? 라고 생각하고 돌려봤지만 역시나 실패! 사실 돌려보지않고 제한사항만 봐도 알 수 있다. stones의 원소 값 200,000,000 이니까,,, 단순 반복문은 안될 거라고 생각했다. 그러면 이제 $N^{2}$이 아니라 NlogN으로 갈 수 있는 방법이나 N으로 갈 수 있는 방법을 찾아야 한다. 2. 혹시 k값 이하로 연속하는..

내 머리 속에 삼성 코테 = bfs + dfs + 빡구현이라서, 오히려 더 어렵게 돌아돌아 풀었다. 70분 정도 걸렸는데, 시험장 가면 떨려서 더 걸릴텐데 벌써 걱정된다. 힝;ㅜ 컴공이 아닌 걸 극복하려고 문제를 무작정 많이 푸는 스타일이지, 엄청 효율적으로 사고하는 편이 아니다. 그래서 구현같은 경우는 주어진 순서를 따라서 차근차근 하나하나씩 함수를 짠다. 내 코드 choice standard 라는 4중 포문으로 기준점 x,y와 길이 d1,d2를 선택한 다음, color_five 함수로 경계선을 -1로 체크해주었다. 그 다음 왼쪽, 오른쪽을 나눠서 divide 함수를 통해서 1,2,3,4 구역별로 정해주었다. 마지막으로 color_inner이라는 bfs문을 돌면서 경계선 혹은 경계선 내부면 5로 체크를..

www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net I번 선수의 경로를 설정하는 것과 사다리를 선택하는 것과 헷갈려서 좀 시간이 걸린 문제 ㅜㅜ 코드 자체는 진짜 몇 줄 필요하지 않다. 1시간 20분정도 걸려서 다 풀고 신나는 마음으로 제출했는데,,, 틀렸다!!ㅜㅜ 아무리 봐도 완벽한데; 의심가는 부분은 DFS 부분 항상 1차원 VISITED 배열을 만들어서 DFS로 조합을 선택하는 건 잘하는데, 2차원으로 가면 응용이 안된다. 원래 내 코드는 DFS로 사다리..

www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net IDEA 고냥 깜찍한 BFS/DFS문제다. DFS보단 BFS가 편해 BFS로 풀었다. '#'이라는 울타리로 막혀있는 공간 안에서 양과 늑대의 개수를 세어, 더 많은 동물의 개수가 살아남아 최종적으로 아침까지 살아있는 양과 늑대의 수를 구하는 문제다. 1. #이 아니면 BFS문 돌림 2. 큐에서 꺼낸 좌표에 O가 존재하면 양을 , V가 존재하면 늑대의 수를 하나 세준다. 3. 상하좌우에 대해서 마당을..

www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net IDEA 여러가지 방법이 있을 수 있겠다. 뭐 유니온파인드를 쓰는 방법도 있겠지만,,,, arr라는 배열에 저장한 후, 배열값을 인덱스로 가지는 그 다음 배열로 넘어가면 될 거 같다. 사이클인지 아닌지 구분하는 방법은 이미 지나온 곳으로 다시 돌아간다면 사이클이다. 1 2 3 4 5 6 7 8 3 2 7 8 1 4 5 6 1부터 시작해서 ..

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net IDEA N개의 정점에서 파티가 열리는 특정한 X점까지 갔다가 다시 돌아오는 최소 시간을 물어보는 문제다. 이것도 다익스트라를 이용해서 풀었다. 뭐 플로이드 와샬을 이용해서 풀어도 될 거 같다. 만약, 문제가 양방향이라면 정점 -> 파티장 비용과 파티장 -> 정점의 비용이 같으므로 시작지점을 파티장으로 설정한 후 다익스트라를 이용하면 된다. 하지만, 이 문제는 도로가 단방향이기때문..