🌷맹이나라🌻

문제 링크 1. 설계 로직 입력된 숫자를 정렬합니다. 2개의 숫자를 뽑았을 때의 합이 0에 가까울 때를 찾아야하므로, 투포인터를 사용합니다. 맨 왼쪽, 맨 오른쪽 값을 구하고, 만약 이 값이 0이라면 answer에 담아서 반복문을 종료합니다. 현재 선택된 2개의 값의 합의 절댓값이 이전에 구한 합보다 더 작다면 해당 값을 answer에 담고, 해당 값이 음수면 left값을 오른쪽으로 한 칸 옮기고, 해당 값이 양수라면 right 값을 왼쪽으로 한 칸 옮깁니다. left가 right보다 작다면 위의 2를 반복합니다. 시간복잡도 : O(NlogN) 2. 코드 N = int(input()) nums = sorted(list(map(int, input().split()))) left, right = 0, N-1..

문제 링크 1. 설계 로직 N, M, map 입력 받습니다. dp용으로 사용할 3차원 배열을 만듭니다. 방향 정보가 들어가 있으므로 3차원으로 만듭니다. 초기 값은 최대 값으로 채워줍니다. dp[y][x][0]: dp[y-1][x+1]의 최솟 값 + map[y][x] dp[y][x][1]: dp[y-1][x]의 최솟 값 + map[y][x] dp[y][x][2]: dp[y-1][x-1]의 최솟 값 + map[y][x] dp에서 y == 0인 경우, map 값을 초기 값으로 채워줍니다. 각각의 경우에 따라 dp를 진행합니다. (0 < y < N) x == 0 인 경우: ↘로 오는 방향이 존재하지 않음 x == M-1인 경우: ↙로 오는 방향이 존재하지 않음 dp를 모두 채우고 나서, N-1번째 행에 존재하..

1. 문제 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 2. 접근 방법 문제 추천 받아서 풀었는데, 굉장히 삼성틱한 문제입니다. 이 문제에서 유의해야할 점은 4가지라고 생각합니다. 1. 최대 3칸까지 한 번에 갈 수 있다는 점 2. 회전이 존재한다. 3. 방향 회전 및 이동이 아니라 회전, 이동이 각각 한 번의 명령이라는 점 4. 1회 회전시 시계, 반시계 방향으로 1번만 회전할 수 있다는 점 1번이 유의해야할 점인 이유는 다음과 같습니다. 이 문제에..

1. 문제 https://www.acmicpc.net/problem/14675 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net 2. 접근 방법 단절점과 단절선이라는 용어가 나와서 쫄았었는데, 별 거 아니었습니다. 문제에 나온대로 적어보자면, 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다. 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 ..

1. 문제 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 2. 접근 방법 문제에 등장하는 케빈 베이컨 수는 해당 노드에서 다른 노드를 모두 방문하는 데 필요한 총 길이인데요, 결국 그래프의 최단 길이 문제라 다익스트라 혹은 플로이드 워셜로 풀이할 수 있습니다. 하지만 N이 500이하라서 플로이드워셜을 써도 되겠다 싶었습니다. 물론 bfs로도 풀이 가능합니다. 플로이드 워셜을 쓰기에 앞서 간단히 ..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 2. 접근 방법 완전 빡! 구현입니다,,~! 이걸 어째야하나 하다가 승환님의 풀이를 듣고 츄롸이츄롸이 1. game_board를 순..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 2. 접근 방법 전 문제(입국심사)를 풀면서 거리를 기준으로 이분탐색을 하면 되겠다는 생각을 했습니다. 그래서 거리를 기준으로 제거되는 바위의 갯수를 세고, 해당 바위의 갯수가 n개보다 많을 때에는 기준 거리를 줄이고, n개보다 적을 때에는 기준거리를 늘리고, n개일 때 return하게 짰습니다. 근데 요러케 하면 ^^ 왜인지는 모르겠지만..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 2. 접근 방법 이분탐색인데요~! (이분탐색인 이유 1. 이분탐색 탭에 위치한 문제다 2. 입국심사를 기다리는 사람이 10억명이고, 심사관이 심사하는 데 걸리는 시간이 최대 1억이고, 심사관이 최대 10만명 이하이기 때문에 이분탐색입니다.) 여튼 그래서 심사에 걸리는 총 시간을 기준으로 이분탐색을 해주면 됩니다. 상당히 생각하기 까다로운 문제예욧 흥! ..

1. 문제 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 2. 접근 방법 그냥 구현하면 됩니다. 백준은 입력도 내 맘대로 받을 수 있어서, input으로 입력받을 수도 있고, readline을 사용해서 입력받을 수도 있는데 readline이 훠얼씬 빠르구 이 문제도 주어지는 명령의 갯수가 10,000개까지 가능해서 readline으로 받아야 시간초과가 나지 않습니다. 사실 deque쓸 필요 없는데 input으로 할 때 시간을 ..

프로그래머스 17686 파일명 정렬 문제 링크 1. 설계 로직 파일명 : HEAD, NUMBER 부분을 파싱합니다. 파싱 후, HEAD에 담긴 문자는 모두 소문자로 만들어주고, NUMBER에 답긴 숫자는 int형으로 바꾸어 [기존 문자, HEAD.lower(), int(NUMBER)] 형태로 만들어줍니다. 이렇게 2차 배열을 만들어, 배열을 sort해줍니다. sort의 첫 번째 순위는 HEAD, 두 번째 순위는 NUMBER가 되게끔 key값을 넣어줍니다. sort를 하면 HEAD, NUMBER의 우선순위가 같을 때 기존 배열의 순위를 가지고 있기 때문입니다. sort 후 맨 앞의 값(기존 문자)만 배열에 담아 보여줍니다. 시간복잡도: O(N*(M+logN))입니다. (N은 파일의 갯수, M은 파일명의 길..