'알고리즘' 태그의 글 목록 (2 Page)

[알고리즘] 이진탐색 Lower/Upper Bound | Python bisect

2023.02.20·

PS/Algorithm

개요 이진탐색을 하는데 만약 배열에 target 값이 여러 개 존재한다면, 정확한 위치의 값을 도출하는 데에 어려움을 겪을 것이다. 이를 해결하기 위한 알고리즘이 Upper Bound와 Lower Bound이다. Python에서는 bisect라는 도구를 제공한다. Lower Bound target 이상의 값이 최초로 나오는 위치다. 즉, target보다 같거나 큰 원소 중 가장 작은 값의 위치다. 예를 들어서 아래와 같이 정렬된 배열이 존재한다고 가정하자. 1 5 5 5 10 11 100 이 배열의 lower_bound(5) = 5다. 또한 lower_bound(4) = 5다. 가장 작은 값을 구하기 위해서 min_idx 변수를 활용하여 초기값으로 답이 될 수 없는 최댓값을 넣어놓고 문제를 해결한다. l..

[백준/2852] NBA 농구

2023.02.16·

PS/BOJ&Programmers

알고리즘 게임 라운드별로 골 넣은 시간과 해당 팀이 주어지고, 각 팀이 몇 분동안 이기고 있는지 출력하는 문제다. 게임 진행 상황에 따라서 각 팀이 이기고 있는 시간(출력물)이 바뀌기 때문에 이를 구현해야 한다. 1. 골이 들어갈 때 마다 입력을 해주는 거기 때문에 입력되는 팀 번호의 개수를 통해서 각 팀이 이기고 있는지 지고 있는지 판단한다. 2. 현재 게임 득점 시간이 다음 게임 득점 시간에 영향을 주기 때문에 이전 게임의 득점 시간을 반복문의 마지막에 저장한다. 3. 주어진 48분 동안 득점을 한 시간이 주어지기 때문에, (주어진 시간 - 득점 시간) 연산으로 이기고 있는 시간을 출력한다. 파이썬 시간 출력 시간과 관련된 문제를 풀 때, 보통 초 단위로 시간을 변경해서 푸는데 이렇게하면 알고리즘은 ..

[백준/6236] 용돈 관리 | 이진 탐색 트리 | 분할 | 파이썬

2023.02.14·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 이진 탐색 / 이진 탐색 트리를 공부하고 첫 활용 문제를 풀어봤다. 이 문제가 왜 이진 탐색이냐면 N일 동안 사용하려고 계획한 금액에 맞게 최소 K 값을 구해야 하는데, 이때 K원은 M번에 맞춰서 출력이 해야 하기 때문에 분할 개념으로 최소 K가 나올 때까지 탐색을 하기 때문이다. 분할(partition) 분할은 말 그대로 여러 개로 나눈다는 뜻인데, 이산수학에서의 분할은 보통 집합의 분할을 뜻한다. ..

[백준/15821] 낚이고 낚아라 | 배열 2칸씩 묶기 _ range()의 활용

2023.02.05·

PS/BOJ&Programmers

알고리즘.. 나의 생각 🐤 이 문제 내용 자체가 흥미로워서 비행기에서도 계속 아이패드로 풀이를 생각해봤다. 내가 생각한 첫 번째 알고리즘은 원 둘레를 이용하는 것이었다. 하지만 계산을 해보니, 엉터리 풀이라서 깔끔하게 안녕.. 그 다음엔 원 넓이를 이용한 알고리즘을 생각했다. 1, 2, 3, 4분면에 입력 받은 점 중 최댓값을 골라서 그만큼의 길이를 반지름으로 만들어주면 되겠다!가 결론이었다. 그럼 내 메모에서 빨간 점들과 원점 사이의 거리가 가장 큰 값이 낚시 거리가 되겠다. 알고리즘 생각은 잘 했는데 구현을 스스로 하지 못했다. 그 이유는 1. 연속적으로 입력되는 값들의 좌표 표현 x y 좌표가 연속적으로 들어오는데 이걸 좌표로 어떻게 표현을 해야할 지 몰랐다. 홀수 번째에 있는 건 y 좌표, 짝수 ..

[백준/10819] 차이를 최대로 | 모든 순서를 고려한 배열.. permutation | 리스트 갱신법이 항상 효율적일까?

2023.01.31·

PS/BOJ&Programmers

알고리즘 1. 모든 배열 케이스를 확인해주기 위해서 permutarion으로 배열 케이스를 모두 생성해준다. 2. 생성된 배열 케이스의 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|를 확인해준다. 최종코드 from itertools import permutations n = int(input()) li = list(map(int,input().split())) per = permutations(li) ans = 0 for i in per: case = 0 for j in range(1, len(i)): case += abs(i[j-1] - i[j]) if case > ans: ans = case print(ans) 알게된 점 1. 모든 순서를 고려한 ..

[백준/3029] 경고 | 파이썬

2023.01.29·

PS/BOJ&Programmers

📝 3029 경고 파이썬 알고리즘 시간 계산을 할 때 주의할 점은 24시간이 넘어갔냐 아니냐를 컴퓨터가 판단하도록 지시해야 하는 것이다. 20시와 4시는 숫자만 봤을 때 당연히 20이 더 크지만, 만약 다음날 4시를 뜻하는 거라면 4시가 더 늦은 시간이기 때문에, 이를 컴퓨터가 알아차리도록 해야 한다. 이 문제의 예시에는 두 가지 케이스가 잘 나와있다. 첫 번째 케이스는 다음날 새벽 4시를 뜻하므로 이미 24시간이 넘어간 경우이기 때문에 이를 계산할 때 주의해야 한다. 두 번째 케이스는 같은 날 오후를 뜻하므로 그냥 계산해도 상관없다. 🕰 넘어간 24시간은 어떻게 표현할 수 있을까 만약 24(시) * 60(분) * 60(초) = 86400을 넘어간다면 00:00:00 ~ 23:59:59 로 표현할 수 있..

[백준/11383] 뚊 | 2차원 이미지 | 행렬 한줄씩 걷어내기(?)

2023.01.28·

PS/BOJ&Programmers

📝 알고리즘 처음에 문자열로만 생각해서 못 풀었는데 문제를 정확하게 읽어야 한다. N x M 크기의 '이미지'와 N x 2M 크기의 '이미지'가 주어지는 거라서 행렬로 생각하는 게 더 수월하다. 처음에 헷갈렸던 점은 일단 큰 for문 안에서 비교를 해야 하는데 입력이 NxM크기의 이미지가 먼저 들어온 다는 거다. 그러면 for _ in range(n): img1 = input() img2 = input() 이런식으로도 받을 수 없기 때문에..(리스트인 경우도 마찬가지) n,m = map(int,input().split()) img1 = [input() for _ in range(n)] img2 = [input() for _ in range(n)] 이렇게 한 줄 for문으로 입력을 받아주었다. 또한, im..

[백준/2309] 일곱 난쟁이 | sorted()를 반복문의 대상으로

2023.01.25·

PS/BOJ&Programmers

📝 알고리즘 들어오는 순서에 상관없이 숫자 7개의 합을 100으로 맞춰야 하기 때문에 파이썬 itertools의 combinations를 사용했다. 알고리즘은 잘 생각했는데 출력물이 깔끔하지 않아서 아쉬웠다. 당장 생각나는 게 이 코드여서 제출을 하고, 다른 사람의 코드를 보니 sorted를 for문의 반복횟수로 지정해주었다. 파이썬 for문은 어떤 시퀀스(sequence)를 반복하는 문법이므로 sorted가 반복횟수가 될 수 있는 것이다. 💻 최종 코드 from itertools import combinations as comb t = [] h = 0 for _ in range(9): t.append(int(input())) for i in comb(t,7): if sum(i) == 100: i = l..

[자료구조] 트리(Tree)

2023.01.24·

PS/Data Structure

트리 트리란? 회사의 조직도, 가계도와 같이 나무처럼 뻗어나가는 모양의 사이클이 없는 그래프다. 노드 간선 루트 노드: 트리의 맨 꼭대기 부모 노드/자식 노드 리프 노드: 자식이 없는 노드 차수와 깊이 그리고 높이 차수: 특정 노드의 자식 수 깊이: 특정노드로부터 루트노드와 떨어져있는 정도 높이: max깊이 + 1 이진트리 트리의 자식을 2개로 한정하면, 이진트리 배열로 나타내기 좋다. 부모는 i, 왼쪽 자식은 i2, 오른쪽 자식은 i2+1 만약 모든 자식이 꽉 차있지 않다면 배열도 같이 비워줘야한다. 이진트리는 한번 알면 여러모로 편하다.. 자식이 2개로 제한되어 있기 때문에 구현도 좋다… 그러니 확실하게 알아둘 것! 트리의 순회 트리를 탐색하는 순회 방법은 3 가지가 있다. 전위 순회(왼>뿌>오) 중..

[백준/10809] 알파벳 찾기 | find() 찾고자 하는 문자의 인덱스를 반환

2023.01.22·

PS/BOJ&Programmers

📝 알고리즘 파이썬 내장함수 find와 아스키코드를 활용하여 문제를 풀 수 있다. find 함수는 해당 문자열에서 괄호 안의 문자가 몇 번째에 나타나는지 인덱스를 반환한다. 만약, 해당 문자가 없다면 -1을 반환한다. 소문자 a부터 z까지의 아스키 코드 넘버는 97부터 122까지다. (대문자 A to Z는 65 ~ 90이다.) 💻 전체 코드 s = input() alpha = list(range(97,123)) # a ~ z for i in alpha: print(s.find(chr(i))) 소문자 알파벳 전체를 아스키 코드로 (97번부터 122번까지) 리스트에 저장한다. 저장된 소문자 알파벳 아스키 코드를 for문으로 돌면서 포함되었는지, 아닌지 확인해주면 된다!

[백준/1436] 영화감독 숌

2023.01.22·

PS/BOJ&Programmers

처음 작성한 코드 처음에 숫자를 while 문에서 계속 +1 해주고 idx를 설정해서 n번째가 나오면 break를 해주는 코드를 작성했다. n = int(input()) i = 0 num = 665 while True: num += 1 s_num = str(num) i += 1 if '666' in s_num and i == n: print(s_num) break 근데 이렇게 하니까 무한 루프에 걸려서 동작을 제대로 안한다. 코드를 보면 검사할 필요가 없는 idx 번호까지 즉, 종말의 숫자가 아닌 것까지 카운트를 하기 때문에 잘못된 구현이기 때문이다. 최종코드 n = int(input()) i = 0 num = 665 while True: num += 1 s_num = str(num) i += 1 if ..

[백준/1181] 단어 정렬 (파이썬)

2023.01.18·

PS/BOJ&Programmers

아주 기본적인 것들을 충실하게 물어본 문제다. 이런 컴팩트한 문제..! 너무 좋음 정렬을 하는데 조건이 2개 이상이면 이중 for 문이나 if 문을 사용해도 되지만, lambda 함수를 사용하여 깔끔하게 정리할 수 있다. 이 문제를 풀기 위해 알아야 하는 파이썬 기초 개념 lambda(익명함수) set 자료형은 중복을 제거할 수 있으나, 순서가 없기 때문에 list(set(arr)) 형식으로 종종 사용된다. (정렬이 필요할 때) set 자료형은 순서가 없기 때문에 정렬이 불가능하기 때문이다. python sort와 sorted 차이 [Python] 파이썬 정렬 심화, lambda(익명함수) 함수 -파이썬 정렬 정렬 메소드인 sort()와 함수 sorted()는 디폴트 값이 오름차순이고, 내림차순으로 정렬..

[백준/12759] 틱! 택! 토! - 파이썬

2023.01.17·

PS/BOJ&Programmers

📝 첫번째 시도 개인적으로 이 문제가 어려웠던 이유는 게임이 끝나고 승부를 판단하는 게 아니라 입력이 될 때 누가 언제 이기는지 알아내야 하기 때문에 헤맸다. 만약에 승부만 판단하는 문제였다면, 플레이어 1과 2가 했던 게임을 입력 받고 승부 조건만 확인하면 되기 때문이다. 그래서 처음에는 이렇게만 이해하고 다음과 같이 코드를 작성했다. # 먼저 시작하는 사람 n = int(input()) g = [[' ']*3 for _ in range(3)] for i in range(9): r,c = map(int, input().split()) # 게임판 if i % 2 == 0: g[r-1][c-1] = 'X' else: g[r-1][c-1] = 'O' # 승부 확인을 위해서 새로운 배열에 대입. res = [..

[백준/14582] 오늘도 졌다 / 야구에 대한 이해 / 파이썬 리스트 누적합

2023.01.14·

PS/BOJ&Programmers

🔎 문제 이해 평소 야구를 즐겨보지 않아서 그런지 초와 말에 대한 개념이 없었다. 그래서 처음엔 그냥 i번째에 이기고 있으면 역전패가 성립한다고 코드를 구현했는데 틀린 거다...! 질문 게시판을 통해 반례를 찾아보니 출제자가 그래서 문제 마지막에 경기는 1회초 -> 1회말 -> 2회초 -> ... -> 9회초 -> 9회말이라는 설명까지 덧붙인 듯하다. 역시 문제를 꼼꼼히 잘 읽는 것도 중요하다. 괜히 써진 문장은 없기 때문에 최대한 힌트를 많이 얻어가는 게 유리하다. 💡 파이썬 리스트 원소 누적합 게임은 현재까지 얻었던 점수들의 합으로 판단을 하기 때문에, 누적합을 구해서 승부를 판단했다. a = list(map(int, input().split())) b = list(map(int, input().sp..

[백준/3986] 좋은 단어 / 스택 / 스택 활용법 / 스택 원리

2023.01.13·

PS/BOJ&Programmers

아쉽게도 처음부터 이 문제를 보고 스택으로 풀어야겠다!! 라고 떠오른 건 아니다. 처음에 인덱스가 짝수인 / 홀수인 경우를 나눠서 세어보려고 했는데,, 알고리즘이 너무 복잡하고 변수도 쓸데없이 많다는 생각에 서치를 했다! 오래 고민하고 생각했는데도 내가 생각하는 알고리즘이 이상하다/도저히 모르겠다 싶을 땐, 빠르게 다음 스탠스를 취하는 것도 중요한 것같다.. 생각보다 아직 나는 아는 게 없기 때문이다. 그래도 괜찮다. 알고리즘 공부를 더욱 꾸준히, 열심히 해서 아는 영역을 넓혀 나가는 것이 이번 방학의 목표이기 때문에, 하루하루 정진하다보면 방학이 끝날 때 쯤엔 나도 아는 게 꽉꽉 차있을 테니까~~~~ 혹시 스택에 대해 모르신다면? https://cobinding.tistory.com/entry/%EC%..

티스토리툴바