알고리즘

[백준] 1002번 - 터렛

오늘은 살짝 수학공식이 필요한 문제를 풀어보았습니다 개념만 알고 그대로 알고리즘에 적용하면 어렵진 않은 문제인 것 같네요! https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 문제에 사용된 변수명과 공식을 설명하자면, 입력받은 r1, r2는 두 원의 반지름이고 R은 두 원의 중심 사이의 거리 입니다. 반지름과 두 점 사이의 거리를 비교하면서 교점을 구하면, 있을 수 있는 위치의 개수가 나옵니다. 경우의 수는 다음과 같은데요. 이 경우를 그대로 코드로 작성하면 문제를 해결할 수 있습니다.

[백준] 2583번 - 영역 구하기 (DFS / BFS)

오늘은 문제를 보자마자알 수 있는 DFS, BFS 분류의 문제를 풀어보았습니다. 오랜만에 풀어서 조금 감을 잃었는지 조금 헤매면서 풀었던 것 같네요 😅 바로 풀이 보시죠!!! 1. 문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 2. 풀이 문제 입력부터 확인하면, 첫번째 줄에 세로, 가로, K 를 입력하고 (K는 모눈종이의 직사각형의 개수) 두번째 줄부터 직사각형의 꼭짓점 좌표를 하나씩 입력받습니다. 문제에서 해당 직..

[Python] 리스트의 모든 최댓값의 인덱스 구하기

파이썬에서 리스트의 최댓값을 구하는 코드는 max 연산자만 붙이면 간단히 사용할 수 있다. 그렇지만, 리스트에서 최대값이 여러개라면 여러개를 모두 리턴하는 것이 아닌 리스트에서 가장 앞에 있는 값이 리턴된다. 다음 배열에서 최댓값인 4는 4번째와 7번째에 위치해있지만 출력해보면 3만 출력 되는 것을 확인할 수 있다. list_num = [1,2,3,4,3,2,4] print(list_num.index(max(list_num)) + 1) #4 그렇다면, 모든 최댓값의 인덱스를 구하려면? 값을 하나하나 비교해보면 된다! 첫번째 방법은 간단하게 for 문을 이용해서 구할 수 있다. list_num = [1,2,3,4,3,2,4] answer = [] for i in range(len(list_num)): if..

[프로그래머스] 연습문제 - 나누어 떨어지는 숫자 배열

오늘은 기초부터 다지기 위해 간단한 수학 연산 문제를 풀었습니다! https://programmers.co.kr/learn/courses/30/lessons/12910 코딩테스트 연습 - 나누어 떨어지는 숫자 배열 array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요. divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하 programmers.co.kr 첫 시도는 생각 나는대로 코드를 작성하다보니 길게 작성했는데, def solution(arr, divisor): answer = [] for v in arr: if v % divisor != 0: continue answer.ap..

[Python] itertools 주요 클래스 (permutations, combinations ... )

오늘은 python 에서 반복적인 데이터를 처리하는 기능을 가진 itertools 라이브러리의 주요한 클래스에 대해 알아봅시다. 저는 java로 먼저 코테 문제를 풀다가 python 으로 언어를 변경했는데, 이 때 python의 가장 강력한 장점 중 하나가 바로 이러한 모듈들을 직접 구현하지 않고 라이브러리를 사용만 하면 간단히 구현할 수 있다는 점인 것 같아요! iterable 객체를 가지고 주로 사용하는데, 이 때 iterable은 반복 가능한 List, Dictionary, Tuple 자료형 같은 객체를 말합니다. permutations 1. 단어의 뜻 먼저 사용하기 전! permutation 사전적 정의가 무엇일까요? "순열" 서로 다른 원소를 가진 집합에서 대상을 선택하여 순서있게 배열하는 것을..

[프로그래머스] 2020 KAKAO 인턴십 (Lv1) : 키패드 누르기

오늘은 2020년 카카오 인턴십 문제였던 "키패드 누르기" 문제를 풀어보았습니다. 1레벨임에도 비교적 다른 카카오 기출 문제 보단 시간이 필요했던 문제였던 것 같습니다. (저만 그런가요? 😅) 살짝 수학적인 계산이 필요한 조건이 있었는데, 거기서 약간 시간이 소요된 것 같습니다. 먼저 문제의 조건을 살펴볼까요? 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]..

[Python] bisect_left, bisect_right

안녕하세요! 오늘은 python 이 기본 제공하는 이진 탐색 알고리즘을 구현한 bisect 모듈에 대해 알아보겠습니다. 1. 이진 탐색 먼저 이진 탐색이란 탐색 범위를 절반씩 좁혀나가면서 데이터를 탐색하는 알고리즘 입니다. 특히 데이터가 정렬된 상태일 때, 우수한 성능으로 탐색 합니다. 예를 들어 [1, 2, 3, 4, 5, 6, 7, 8, 9] 이라는 배열에서 Target = 3이라면 1. Middle 값을 기준으로 Target 값이 작은지 큰지 비교합니다. 2. 5 (Middle) > 3 (Target) : 기준 값보다 작으므로 5보다 큰 값들은 비교하지 않고 작은 값 들만 비교합니다. 3. [1, 2, 3, 4] 배열의 중간 값을 기준으로 또 비교를 하는데 4. 여기선 3이 middle이라 치면 t..

[Python] 2019 KAKAO BLIND RECRUITMENT - 오픈채팅방

문제 https://programmers.co.kr/learn/courses/30/lessons/42888 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 문제가 길어서 어려워보일 수 있겠지만, 어렵다기 보단 친절한 문제인 것 같다. 채팅방에 들어왔다가 나갔을 때 기록이 남으며, 닉네임이 바뀌는 경우는 2개의 경우 인데 1. 채팅방을 나갔다가 똑같은 닉네임으로 다시 들어오는 경우 (이전 기록에도 이름이 변경됨) 2. 채팅방에서 닉네임을 변경하는 경우 처음 시도는 기록이 남겨질 때마다 Enter, Leave, ..

[Python] heapq 사용시 리스트를 heapify / 값 하나씩 heappush 차이점

프로그래머스 더 맵게 문제를 풀다가 리스트를 정렬하는 sort() 메소드를 사용하면 값은 나오는데 시간초과가 떠서, 배열을 heapq로 바꿔주는 heapify 대신 ( 제자리에서 힙으로 변환된다 ) 원소 하나하나를 heappush 하면 힙의 불변성을 유지하며 push, pop 된다. 파이썬에 내장된 heapq는 이진 트리이며 최소힙을 사용한다고 한다. 1. 리스트를 그대로 힙으로 변환할 때 import heapq arr = [9, 3, 2, 1, 12, 10] heapq.heapify(arr) print(arr) //[1, 3, 2, 9, 12, 10] 2. 원소 하나하나 heappush 할 때 import heapq arr2 = [9, 3, 2, 1, 12, 10] new_arr = [] for i i..

[Python] 프로그래머스 고득점 Kit (스택/큐) : 프린터

문제 코딩테스트 연습 - 프린터 [ 문제 조건 ] priorities : 현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 location : 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지 return 값 : 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 [ 해결순서 ] 처음에 문제를 풀 때 잘못 이해했다. 어떻게 이해했냐면 중요도가 중요도가 제일 높은 값을 발견할 때까지 계속 반복해서 앞에 값 뒤로 보내다가 최댓값이 발견되면 해당 인덱스가 몇번째인지 바로 리턴하게 코드를 짰다. 이렇게 풀면 프로그래머스에서 제시한 2가지 입출력 예에는 해당이 되지만 실패로 채점이 되고 다른 테스트 케이스에서는 제대로 작동하지 않는다. 반례로 priorities=[1,2,8,3,4]이고, loca..