python(13)
-
[프로그래머스/python] 후보키
후보키 2019 KAKAO BLIND RECRUITMENT 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 조합과 집합을 사용하여 풀이를 진행했습니다. 이 문제를 들었던 생각은 유일성과 최소성을 잘 구현하면 되겠다고 생각했습니다. combinations 사용해서 후보키의 길이를 1부터 n열까지 올리면서 조합을 구했습니다. 조합의 값을 통해서 각 열에 있는 값들을 종합하여 겹치는 값이 있는지 집합을 썼습니다. 그럼 이제 유일성은 해결했습니다. 최소성의 경우 유일성에서 통과한 후보키 값을 n길이 조합이 유일성 검사하기 전에 체크합니다...
2022.08.10 -
[프로그래머스/python] 순위 검색
순위 검색 2021 KAKAO BLIND RECRUITMENT 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 해시맵과 이진탐색을 사용하여 풀이를 진행했습니다. 사실 처음에 풀 때 해시맵이 뭔지도 모르고 풀었기 때문에 한참 걸리고 틀리고 힌트를 얻어가며 풀어갔습니다. 문제 해결과정이 꽤 복잡했습니다. 일반배열로 풀고 "시간초과", 집합으로 풀고 시간을 절반 줄였으나 "시간초과", 쿼리 순환 밖에서 정렬해봤는데 "시간초과" 당했습니다. 문제를 보니 info 배열의 크기는 1 이상 50,000 이하입니다. 그렇다면 이중for문은 포기하고 ..
2022.08.10 -
[프로그래머스] 가장 먼 노드 (파이썬 python)
코딩테스트 - 그래프 - 가장 먼 노드 [Level3] 문제링크 : 가장 먼 노드 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제풀이 그래프 문제입니다. 기존 BFS 풀이를 가지고 풀면 7,8,9 케이스에서 "시간 초과"를 만나게 됩니다. 그러기 위해서 그래프의 방법 중 "인접 행렬" 이 아닌 "인접 리스트"를 사용해야 합니다. list = [[0 for _ in range(n+1)] for _ in range(n+1)] 위 행렬 생성 코드 작성만 해놔도 시간 초과가 걸립니다. 인접 행렬의 경우 연결할 수 있는 모든 경우의 수를 체크를 하고 인접 리스트는 연결된 경우의 수만..
2022.06.10 -
[프로그래머스] 네트워크 - 파이썬 python
코딩테스트 - 깊이/너비 우선 탐색(DFS/BFS) - 네트워크 [Level3] 문제링크 : 네트워크 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제풀이 DFS 문제입니다. conected_check 배열에는 컴퓨터의 연결을 체크합니다. 연결 안 되어 있으면 False 되어있으면 True 연결 안되어 있는 컴퓨터의 경우 (connected_check == False) 이를 기점으로 dfs함수를 실행해 연결된 컴퓨터를 체크합니다. 기점과 연결된 컴퓨터를 conected_check에 tmp배열에 넣어 ..
2022.06.08 -
[프로그래머스] 정수 삼각형 - 파이썬 python
코딩테스트 - 동적계획법(Dynamic Programming) - 정수 삼각형 [Level3] 문제링크 :정수 삼각형 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 문제풀이 다이나믹프로그래밍(DP) 문제입니다. 삼각형을 거꾸로 거슬러 올라간다고 생각하면 편합니다. 끝에서부터 시작을 해서 자신과 옆에 있는 숫자를 위에 있는 숫자와 더했을 때 더 큰 값을 위에 할당시켜줍니다. 할당이 끝나면 삼각형의 가장 밑줄을 없애고 반복합니다. 삼각형 원소가 1개가 남으면 자연스레 최댓값이 남게 됩니다. 가장 인기 많은 답변 코드는 간단하지만 막상 봤을때는 많이 난해하다고 느껴졌습니다. 분석하기도 힘..
2022.06.07 -
[프로그래머스] 디스크 컨트롤러- 파이썬 python
코딩테스트 - 힙(Heap) - 디스크 컨트롤러 [Level3] 문제링크 : 디스크 컨트롤러 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 문제풀이 Heap 문제입니다. 그런데 저는 힙 없이 사용했습니다. 일단 가장 먼저 핵심적인 것은 "할 수 있는 작업에서 시간이 짧은 거부터 시작한다"라는 점입니다. 긴 작업 소요시간이 걸리면 그만큼 시간이 남은 작업만큼 배로 더해지기 때문입니다. 처음에 jobs를 "작업이 요청되는 시점, 작업의 소요시간" 순으로 정렬합니다. (정렬이 안되어 있음!!) jobs의 처..
2022.06.07