'분류 전체보기' 카테고리의 글 목록 (11 Page)

[백준/6186] Best Grass | bfs, dfs

2023.02.22·

PS/BOJ&Programmers

dfs : 최대한 깊게 방문하지 않은 노드들에 쭉 방문하다가, 더이상 진행할 수 있는 인접정점이 없으면 되돌아감 - 재귀 bfs : 한 노드에서 인접노드까지 방문한 적이 없는 모든 노드를 queue에 삽입. que는 FIFO 방식이라서 순차적인 구현 가능 popleft로 앞에거 빼주면 됨 ㅇㅇ dfs 구현 from collections import deque r,c = map(int, input().split()) pasture = [list(input()) for _ in range(r)] visit = [[0]*c for _ in range(r)] d = [(0,1),(0,-1),(1,0),(-1,0)] cnt = 0 def dfs(x, y) : visit[x][y] = 1 for dx, dy in ..

[백준/6550] 부분 문자열 | 반복문으로 고정된 인덱스 다루기

2023.02.21·

PS/BOJ&Programmers

알고리즘 있는지 없는지 확인하면 되겠네~~ 개꿀~~ 이런 태도로 문제를 대했지만 내가 간과한 것이 있었다. 처음에 이중 for문으로 s랑 t를 비교해서 다르면 pop하는 알고리즘을 생각했는데 이렇게 하면 s가 t의 '부분 문자열'인지 알 수 없다. 왜냐면,, 전체를 돌면서 문자가 다르기만 하면 pop을 해버리니까 '부분 문자열'인지 판단이 불가능하다. s에 속하는 문자가 있냐/없냐의 문제가 아니라 s가 t의 부분 문자열인가?라는 문제기 때문에 이중 for문으로 s와 t를 도는 식으로는 해결이 불가능하다는 뜻. 따라서 s를 단순히 반복하며 t에 있는 문자들과 비교하는 방식이 아니라 순차적으로 돌면서 t에 속하는 문자와 같은지 확인해주면 된다. 1. for문으로 비교하고자 하는 t를 돌면서 만약 t의 문자와..

[알고리즘] 이진탐색 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..

[백준/8989] 시계 | 시침, 분침의 각도

2023.02.19·

PS/BOJ&Programmers

https://www.acmicpc.net/problem/8989 8989번: 시계 기원이의 방에는 시침과 분침으로 이루어진 아날로그 시계가 있다. 기원이는 시침과 분침이 형성하는 각도 중 작은 각도를 측정하는 것이 취미이며, 이 각도는 0보다 크거나 같고 180보다 작거나 www.acmicpc.net 알고리즘 신선하고 재밌는 문제다. 일단 이 문제를 풀기 위해서 그림을 그렸는데, 그리고 나서 알게된 사실은 분침은 1분당 6도를, 시침은 1시간당 30도에 1/2*m을 한 각도를 갖는 것이다. 사실 처음에는 12시 ~ 3시까지 90도니까 3등분을 하면 한시간 당 30도를 갖겠지?!라고 생각하고 풀었는데, 시침은 1분 동안 0.5도씩 움직이기 때문에, 이 또한 고려해주어야 한다!! 따라서, 시침과 분침의 각..

[백준/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) 분할은 말 그대로 여러 개로 나눈다는 뜻인데, 이산수학에서의 분할은 보통 집합의 분할을 뜻한다. ..

[Python] 파이썬 딕셔너리

2023.02.13·

언어/PYTHON

개요 '코드트리'에서 파이썬 딕셔너리를 공부한 내용이다 코드트리 자료가 생각보다 이해하기 정말 쉽게 되어있고, 중요한 부분을 잘 집어줘서 기록하고 두고두고 볼 예정 파이썬 딕셔너리(Python Dictionary) 파이썬 딕셔너리는 검색/삽입/삭제에 유용한 HashMap 자료구조이다. * HashMap: (key, value) 쌍으로 이루어져 있고, 순서와 상관없이 빠른 검색/삽입/삭제(시간복잡도 O(1))가 가능한 자료구조 딕셔너리 선언 파이썬 딕셔너리는 다음과 같이 선언한다. d1 = dict() d2 = {} d3 = { 'apple' : 1, 'banana' : 2, 'grape' : 3 } key와 value 딕셔너리의 기본적인 구조는 dic_name[key] = value 이다. key 값을 ..

[백준/5430] AC | deque의 reverse() | reverse를 여러 번?

2023.02.13·

PS/BOJ&Programmers

괜히 난이도가 높은 게 아닌 듯한 문제 자료구조를 정확하게 이해하고, 효율적으로 사용할 줄 아는지 체크하기 좋다. 처음 작성한 코드 t = int(input()) for _ in range(t): p = input() n = int(input()) li = list(map(int, input()[1:-1].replace(',', ''))) for p_i in p : # R : 순서 뒤집기 if p_i == 'R': li = sorted(li, reverse= True) elif p_i == 'D': if len(li) == 0 : print('error') else: li.pop(0) print(li) 문제 1. replace는 단순히 변환해주는 함수라서 그대로 문자열임. split은 리스트 반환. 문제..

[백준/1021] 회전하는 큐 | python deque | dequed의 rotate()

2023.02.12·

PS/BOJ&Programmers

파이썬 deque deque는 문제풀이에서 종종 사용했었지만 주요 내용을 다시 한번 정리해보았다. 알고리즘 파이썬 deque 자료구조를 알고있다면 어렵지 않게 해결할 수 있다. 최종코드 from collections import deque n,m = map(int, input().split()) que = deque(range(1,n+1)) idx = list(map(int, input().split())) cnt = 0 for i in idx: # 다 찾을 때까지 수행 while True: # 찾고자 하는 값의 위치가 중간보다 왼쪽인 경우 if que.index(i)

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

2023.02.05·

PS/BOJ&Programmers

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

[DB/MySQL] 기본 명령어

2023.02.02·

DB

기본 명령어 1. SHOW / SHOW TABLE SHOW TABLE; # world db의 테이블 이름 보기 SHOW TABLE STATUS; # world db의 데이터 이름 + 각각의 table 정보 조회 * world는 실습 예제 데이터 베이스이다. 2. DESCRIBE DESCRIBE table_name # DESC로 줄여서 사용 가능 데이터 베이스 내에 존재하는 테이블의 data를 확인 할 수 있다. 각각의 영역은 Field로 표시된다. 예제 데이터베이스 world의 테이블은 city, country, countrylanguage가 있고 위 코드를 실행하면 city에 존재하는 내용에 대해 확인 가능하다. 3. SELECT ⭐️⭐️⭐️ 데이터를 가져오는 명령어 FROM SELECT * FROM ..

[백준/20410] 추첨상 사수 대작전!(Easy)

2023.01.31·

카테고리 없음

알고리즘과 여러 번의 시도 뭐야 이문제 ㅋ 하고 처음에 이런 코드를 작성했다. m,s,x1,x2 = map(int,input().split()) a,c = 0, 0 while True: if x1 == (a*s+c)%m : if (a*x1+c)%m == x2: print(a,c); break else: a+=1 c+=1 else: a+=1 c+=1 3 3 / 4 4가 출력돼서 생각해보니까 a랑 c를 같은 조건에서 동시에 +1 해주면 항상 a=c이다. a랑 c를 따로 증가해주면서 조건에 맞는 구현을 하고싶으면 이중 포문으로 각각 증가하면서 조건에 맞는 케이스를 출력하면 된다. m,s,x1,x2 = map(int,input().split()) a,c = 0, 0 for a in range(m): for c ..

[백준/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 로 표현할 수 있..

[백준/15656] N과 M(7)

2023.01.29·

PS/BOJ&Programmers

(1,3) (3,1)같은 경우도 모두 출력(중복 순열)을 해주어야 하기 때문에 파이썬 itertools의 product를 사용했다. 1번 코드 from itertools import product as p n,m = map(int,input().split()) num = list(map(int,input().split())) num.sort() num = map(str, num) ans = map(' '.join, p(num, repeat=m)) print('\n'.join(ans)) 2번 코드 from itertools import product as p n,m = map(int,input().split()) num = sorted(list(map(int,input().split()))) for i i..

티스토리툴바