'백준' 태그의 글 목록 (2 Page)

[백준/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의 문자와..

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

[백준/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)

[백준/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..

[백준/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..

[백준/1942] 디지털시계 | 1초씩 증가 => while t += 1

2023.01.27·

PS/BOJ&Programmers

🤓 시간 표현(시,분,초) 시/분/초를 나눠서 구현해야 하는 문제는 알고리즘을 모르면 꽤 돌고 돌아서 구현을 하는 경우가 생긴다. (유경험자) 이 문제에서는 3으로 나누어 떨어지는 시계 정수의 개수를 구해야 하지만, 시간 문제를 푸는 방법에 집중하여 포스팅하려 한다. (복습용으로..🤓) 시: 0부터 24까지의 숫자로 나타낼 수 있음. 60분에 1시간이므로 분값이 60으로 증가되었을 때, 분 변수는 0으로 초기화되고 시 변수는 +1 분: 0부터 60까지의 숫자로 나타낼 수 있음. 60초에 1분이므로 60초가 되었을 때 초 변수는 0으로, 분 변수에는 +1 추가 초: 0부터 60까지의 숫자로 나타낼 수 있음. # 표현 방법 if s1 == 60 : m1 += 1; s1 = 0 if m1 == 60 : h1 ..

[백준/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..

[백준/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 ..

[백준/7523] Gauß, 가우스 수학, 파이썬

2023.01.19·

카테고리 없음

📝 알고리즘 이 문제는 기본적인 수학 지식이 있으면 쉽게 풀 수 있다. 부등호 양쪽이 이하, 이상일 때 n부터 m까지의 개수 = m-n+1 n부터 m까지의 합 = (n+m)/2 💻 전체 코드 n = int(input()) for i in range(n): n,m = map(int, input().split()) ans = (m-n+1)*(n+m)//2 print('Scenario #{}:'.format(i+1)) print(str(ans)+'\n')

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

2023.01.18·

PS/BOJ&Programmers

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

[백준/14592] 2017 아주대학교 프로그래밍 경시대회(small) - 파이썬

2023.01.18·

PS/BOJ&Programmers

📝 알고리즘 그냥... 완전 탐색으로 풀었다.. N의 크기가 1= n: print(t.index(min(t))+1) break else: print(cnt.index(min(cnt))+1) break else: print(total.index(max(total))+1) break count 함수는 문자열이나 list에만 사용할 수 있다. 처음에 문자열에만 사용 가능하다 생각하고 map(str, list)랑 map(int,list)를 번갈아 가며 해주었다. 똥코드 😆. 코테였다고 생각하니까 끔찍하다. 매일매일 배우는 게 중요하지.. 코테까지만 잘 하면 된다!! 하나씩 구현하면서 코드를 정확하게 구현하는 법을 익혀야겠다. 내가 쓴 코드도 계속 보니 고칠 점이 많았다.. 더 많이 공부해서 잘하고싶다 흑

[백준/13424] Three Dots / 완전탐색 - 파이썬

2023.01.17·

PS/BOJ&Programmers

📝 알고리즘 이 문제는 완전탐색 방식으로 풀면 점의 개수가 1000 개일 때, 1000 * 1000 * 1000 = 10^9로 시간 초과를 하게 된다. 따라서 세 점의 거리가 동일한 케이스를 모두 계산하는 방법이 아닌, 동일한 간격이 존재하는 점을 찾는 방식으로 구현하도록 한다. 수직선 상에 임의의 세 점 a,b,c가 있을 때 점 C는 b에서 a와 b의 거리만큼 더한 값이다. 이 알고리즘을 활용하여 점 C를 찾고, 이 값이 입력받은 list에 존재한다면 세 점은 동일한 거리를 가진 점들이다. 💻 최종 코드 from collections import defaultdict t = int(input()) for _ in range(t): n = int(input()) dots = sorted(list(map(..

티스토리툴바