본문 바로가기
728x90

CS Study

 (21)
[Programmers] 2019 KAKAO BLIND RECRUITMENT - 후보키 (Python) 코딩테스트 연습 - 후보키 [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 programmers.co.kr 데이터베이스에서 사용할 수 있는 후보키의 개수를 구하는 문제! 효율적으로 보이지는 않지만 후보키의 개수가 많이 않기 때문에 combinations을 사용해서 구해도 충분히 시간안에 해결 가능한 문제였다! from itertools import combinations def solution(relation): answer = 0 n = len..
[Programmers] 방문 길이 (Python) 코딩테스트 연습 - 방문 길이 programmers.co.kr 처음에는 매 칸의 상하좌우로 방문한 곳을 다 저장해야하나 하고 생각해서 매우 어렵게 접근했었다..🥲 하지만 뮤.뮤가 매우 간단한 아이디어를 제공해줬다!! 이 문제의 핵심은 바로 "선을 어떻게 표현할 수 있는가?" 이다! 이 문제에서 선은 어떻게 만들어지는가! 바로 점과 점이 만나서 선이 만들어진다. 즉, (출발점, 도착점) 정보가 바로 선에 대한 정보인것! 따라서 (출발점, 도착점) 정보가 총 중복 없이 몇 개 있느냐가 정답이된다! 나같은 경우 (출발점) : [(도착점)]을 저장하는 딕셔너리를 만드는 방식으로 구현했다. 이때 (출발점, 도착점)과 (도착점, 출발점)은 동일한 선이므로 각각 딕셔너리에 저장한 후 마지막에 2로 나누어 주어야 한다..
[BOJ] 1261. 알고스팟 (Python) 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 오랜만에 푸는 벽 부수기 문제! 코테 준비를 하면서 제일 처음 벽 부수기 문제를 만났을 때는 머리 터지겠다.. 했는데 그래도 여러 BFS 문제를 풀어봐서인지 비교적 쉽게 풀 수 있었다! BFS의 대표 유형과 비슷한데 알고스팟에서 유의해야할 점은 "이미 지나간 곳이지만 더 적은 횟수로 벽을 부수고 지나갈 수 있는가?"라는 점이다! 더 적은 횟수로 벽을 부수고 지나갈 수 있다면 이미 방문한 곳이라도 다시 재방문을 해주어야 한다. 따라서 일반적으..
[2022 KAKAO BLIND RECRUITMENT] 양궁대회 (Python) 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr 2022 카카오 공채.. 마지막 컬쳐핏 면접에서 떨어져서 정말 눈물을 흘렸던 바로 그 공채.. 오랜만에 그때 풀었던 풀이를 다시 살펴봤다. n의 제한이 10개밖에 되지 않아서 combination을 사용하여 간단하게 풀었고 무난하게 통과했다. from itertools import combinations_with_replacement as cwr from collections import Counter def solution(n, info) : answer = [] ..
[Programmers] 힙(Heap) - 이중우선순위큐 (Python) 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 오랜만에 기초 문제 다시 풀기! heap 자료구조를 사용한 문제풀이는 정말 오랜만이라서 heapq 라이브러리의 간단한 사용법을 정리할겸 써본다. 파이썬에서는 내장 라이브러리로 heapq라는 기능을 제공하기 때문에 heap 문제를 매우 간단하게 풀 수 있다. 우선 heap을 사용해서 풀 때 유용한 유형은 "최댓값/최솟값을 반복적으로 리턴해야할 때"이다! 사용법은 간단하다. import heapq heap = [] # 그냥 리스트로 힙을 만들어준다 heapq.heappush(heap, 1) heapq.heappop(heap)​ 그냥 리스트로 힙을 만들어준 후 heapq라이브러리를 사용하여 값을 넣고, 빼주면 된다는 것! 만약 풀고자하는 문제가..
[BOJ] 9252. LCS 2 (Python) 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 오랜만에 코테 풀기! LCS란 최장 공통 부분 수열을 의미한다. 두 개의 문자열이 있을 때, 최장 공통 부분 수열이란 다음과 같다. ACAYKP CAPCAK ---------> ACAK 그렇다면 어떻게 최장 공통 부분 수열을 구할 수 있을까? 위 예시를 통해 최장 공통 부분 수열을 구하는 법을 살펴보자! 우선 아래와 같은 배열이 존재한다고 가정하자.행에 있는 문자를 기준으로 열에 해당 문자가 존재하는지 체크하고, ..
[BOJ] 9372. 상근이의 여행 (Python) 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net * 신장 트리 (Spanning Tree) : 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 의미 이때, 모든 정점을 연결하기 위한 최소 간선의 수는 n-1개입니다. (아무 그래프나 직접 그려보시면 이해하기 쉽습니다!) * 최소 신장 트리 (Minimum Spanning Tree, MST) : 신장 트리 중에 연결 비용이 가장 적은 것을 의미 상근이의 여행 문제는 최소 신장 트리 파트에 속해있긴 하나 비용은 ..
[BOJ] 11725. 트리의 부모 찾기 (Python) 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리의 부모 찾기 문제! 방법은 간단하다. 먼저 각 트리에게 연결 된 노드들의 정보를 저장한다. 루트 노드는 무조건 1번 노드로 정해져있으니 1번노드를 시작으로 DFS 또는 BFS로 순회를 하면 각 노드의 부모 노드를 한 번에 찾을 수 있다. * DFS의 경우 recursion limit을 설정해두어야 한다. import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline n = int(input()) tree = [[] for _ in range(n+1)] parents..
728x90

티스토리툴바