potato's devlog

문제링크 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 나의 풀이 dfs/bfs를 활용한 코드를 풀어보지 않아서 참고자료를 활용해 문제를 훑어보는 시간을 가졌다. 지금은 단순히 그래프를 탐색하는 문제를 풀었지만, 앞으로는 응용문제를 계속 풀어보면서 LG CNS 코테 전까지 bfs, dfs를 정복하는게 목표다. 꼭 dfs/bfs문제는 풀고 나오리라! bfs, dfs의 정말 간단한 개념) https://did..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 나의 풀이 이전에 풀었던 입국심사 와 비슷한 문제다. 이분탐색의 개념을 확실히하고, 이 문제의 유형은 확실하게 풀고 넘어갈 수 있도록 해야겠다 ㅠㅠ def solution(distance, rocks, n): answer = 0 left = 0 right = distance rocks.sort() # left, right, mid는 거리 ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 programmers.co.kr 나의 풀이 자료형 list를 사용하면 효율성이 떨어진다. list를 사용하지말고 무조건 deque를 사용하자 (실제로 list를 모두 deque로 바꾸었더니 효율성테스트 통과를 하였다.) 괄호는 () 이렇게 닫혀야만 True로 인식해야한다. s에 주어진 괄호들을 한개씩 left 변수에 저장해놓고, 다음 변수..

문제링크 나의 풀이 1. 이분탐색이라고 주어지지 않았을 경우에는 못풀었을 확률이 크다. 2. 이분탐색 알고리즘 강의를 듣고 풀었다..... 어렵다 ㅠㅠ ▶ 풀이설명 이분탐색은 탐색하고자 하는 리스트가 정렬된 상태에서, 가장작은값(left), 가장큰값(right)로부터 mid값을 찾고, mid값과 비교해나가면서 최적값을 탐색하는 것이다. 해당 문제에선 가장 최적의시간을 left, 가장 오래걸리는 시간을 right로 두고, 두 값을 더하고 2로 나누어준 값을 mid시간으로 정했다. mid시간을 times 리스트에 있는 값들을 사용해서 나누어주면, 해당 몫은 mid시간에 처리할수 있는 손님의 수를 의미한다. 만약 이 손님의 수가 n보다 크면 반복문을 나오게 된다. 손님의 수가 n보다 크다는 의미는, 제시된 손..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 나의 풀이 일단 brown과yellow의 합의 약수만 한변의 길이가 될 수 있다는 것을 캐치해야했다. 그리고, 규칙을 살펴보면, 문제의 그림과 같이 yellow가 brown에 모두 둘러쌓여있으려면 각 변의 -2한 것들의 곱이 yellow의 갯수와 같아야함을 알 수 있다. 그대로 생각힌대로 코드를 구현했다. def solution(brown, yell..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 나의풀이 deque를써야 효율성테스트를 통과할 것이라고 생각했는데, 의외로 간단하게 리스트형태로 풀었더니 그냥 해결되었다. def solution(prices): answer = [] for i in range(len(prices)-1): price = prices[i] for j in range(i+1, len..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42888/ 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 나의풀이 딕셔너리의 key값을 기준으로 value를 넣어주면, 가장 최근의 value를 저장한다는 특징을 이용 사용자는 Enter할 때, change할 때 닉네임을 바꿀 수 있으므로, 이 두가지의 경우에 한해서 dic에 userid(KEY) 기준으로 Nickname(VALUE)를 저장해줌 def solution(record): # 우선 split으로..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 나의풀이 규칙찾는데 1시간걸림 3진법, 4진법 등 여러 진법에 대한 이해가 필요 (난 이해도가 낮아서 찾아보면서 풀었음 ㅠ ) 사고 순서 3개의 숫자로 돌아간다? 3진법을 생각할 수 있다. 3진법일 경우, 0,1,2 세개의 숫자로 이루어져있는데 해당 문제는 1,2,4 이므로 어떤경우에 어떤 숫자가 오는지에 대한 확인이 필요하다 도저히 규칙을 못찾겟다가 인터넷에서 -1을 해서 이용한다는 글을 참고해서 규칙을 찾아보았다. 예시를들어 생각해보자. n =10 이라면, 먼저 n-1을 해보자. 그럼 9에서 3으로 나누기시작할것 9나누기..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 programmers.co.kr 나의 풀이 일단, 테스트케이스를 이해하는데 시간이 좀 걸림 트럭 하나가 이동할때는 무조건 1초가 지나고, 1초 안에 두 대의 트럭은 움직이지 않음 그리고 다리 길이가 10이면, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 로 구성되어있음. 트럭 ㅁ가 해당 다리를 지나려면 1초 [0, 0, 0, 0, 0, 0, 0, ..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/42626/ 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 나의풀이 초반에는 리스트를 활용해서 최소값을 출력하고, 더해주고 넣어주고 과정을 반복하려고 했다. 하지만, 리스트를 사용할 경우 분명히 시간초과, 효율성테스트를 통과하지 못할 것이라 생각했다. 그래서 일단 바로 heapq에 대해서 찾아보았다. heapq 를 사용하면 효율성 개선이 될 수 있다고 생각되었다. 따라서 앞서 내가 말한 방식의 진..