'알고리즘' 카테고리의 글 목록

2022. 10. 18. 06:36 알고리즘

Lv1 총 56문제 풀이 기간: 2022.09.04 ~ 2022.09.16 파이썬으로 한 번씩 다 풀었던 문제들인데 코딩 테스트 언어를 자바스크립트로 바꾸면서 공부를 위해 다시 풀었습니다. 문제를 풀면서 정리한 자바스크립트 개념을 PR에 적어놨는데 검색에 불편함을 느껴 블로그에 정리해두려고 합니다. 📌는 다시 풀어볼 문제를 의미합니다. K번째 수 https://github.com/algo-malgo/jungo-malgo/pull/3 공부한 개념 slice for of / for in / forEach sort push 참고 레퍼런스 [Javascript] 배열 자르기 - slice() [javascript] for in / for of / forEach() 차이점 [Javascript] 배열 정렬하기 (..

[백준] 2579 계단 오르기 - 파이썬

2022. 4. 24. 14:02 알고리즘

2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net * 무조건 첫 번째 계단을 밟지 않아도 됨 import sys n = int(input()) s = [int(sys.stdin.readline()) for _ in range(n)] dp = [] for i in range(2): dp.append(sum(s[:i + 1])) if n >= 3: dp.append(max(s[0] + s[2], s[1] + s[2])) for i in range(3, n): dp.append(max(dp[i - 3] + s[i - 1] + s..

[백준] 1003 피보나치 함수 - 파이썬

2022. 4. 21. 01:38 알고리즘

1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 초반에는 그냥 단순하게 메모 사용하면 되는 게 아닌가 했는데 생각보다 삽질을 좀 많이 했다. 처음에는 n이 0이거나 1일 때 cnt_0과 cnt_1이라는 변수를 만들어서 하나씩 값을 더하며 구하려고 했는데 메모를 사용하면 n이 몇이 되든 저 두 변수의 값은 1과 2로 고정이 된다. 그래서 어떻게 해야 할까 하다가 n이 6일 경우 0과 1이 각각 몇 번 나오는지 보려고 그림을 그려봤다. 숫자 옆에 배열은 각각 0과 1의 횟수이다. 그런데 저 숫자들을 보니 1, 1, 2, 3, 5, 8.. 피보나치 수열이었다. 사실 중간에 삽질이 더 생략되어 있긴 하지만 피보나..

[백준] 18870 좌표 압축 - 파이썬

2022. 4. 11. 20:42 알고리즘

18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 시간 초과 import sys n = int(input()) lst = list(map(int, sys.stdin.readline().split())) tmp = set(lst) result = [0] * n for i in range(n): for t in tmp: if t < lst[i]: result[i] += 1 print(result[i], end=" ") 여기서는 어차피 한 줄로 받으니까 sys.stdi..

[백준] 1181 단어 정렬 - 파이썬

2022. 4. 9. 04:01 알고리즘

1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net import sys n = int(input()) word = [sys.stdin.readline().strip() for _ in range(n)] word = list(set(word)) word.sort(key=len) length = 1 tmp, result = [], [] for w in word: if len(w) != length: length = len(w) tmp.sort() result += tmp tmp = [w] else: tmp..

[백준] 11650 좌표 정렬하기 - 파이썬

2022. 4. 7. 23:57 알고리즘

11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net import sys n = int(input()) lst = [] for _ in range(n): lst.append(list(map(int, sys.stdin.readline().split()))) lst.sort() for a, b in lst: print(a, b) 첫 번째 값이 같으면 두 번째 값을 보고 정렬을 하는 문제인데 어떻게 정렬을 할까 하다가 일단 sort() 함수를 돌려보고 결과를 볼까? 해..

[백준] 2018 통계학 - 파이썬

2022. 4. 6. 13:38 알고리즘

2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net import statistics, sys n = int(input()) lst = [int(sys.stdin.readline()) for _ in range(n)] print(round(statistics.mean(lst))) print(statistics.median(lst)) mode = statistics.multimode(lst) if len(mode) > 1: mode.sort() print(mode[1]) else: print(mode[0]) print(max(ls..

[백준] 10989 수 정렬하기 3 - 파이썬 (카운팅 정렬)

2022. 4. 5. 17:21 알고리즘

10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 카운팅 정렬에 대해서는 다음 블로그 참고 https://elrion018.tistory.com/37 카운팅 정렬은 non-comparison sort 기법으로 두 수를 반복적으로 비교하는 정렬 기법이 아니다. counting sort 1. input 배열 요소들의 빈도 값을 세어서 counting array에 저장 counting array의 각 요소 값은 인덱스에 해당하는 요소가 input 배열에 얼마나 존재하는지를 의미한다. 2. counting array의 각 요소에 직전 요소..

[백준] 2751 수 정렬하기 2 - 파이썬 / 퀵 정렬

2022. 4. 5. 15:09 알고리즘

2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net import sys n = int(input()) lst = [int(sys.stdin.readline()) for _ in range(n)] lst.sort() for n in lst: print(n) 사실 파이썬 내장 함수 sort 쓰면 통과되는 문제, 설명에서도 내장 함수 쓰라고 하고.. (단, input 사용하면 시간 초과) 파이썬의 sort는 병합정렬과 삽입정렬을 적절히 섞은 알고리즘이라고 하고 시간복잡도는 O(NlogN)이라고 한다. (근데..

[백준] 1436 영화감독 숌 - 파이썬

2022. 4. 4. 19:38 알고리즘

1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net def nth_number(n): order = 0 for i in range(666, 2147483647): cnt = 0 for c in list(str(i)): cnt = cnt + 1 if c == '6' else 0 if cnt == 3: order += 1 break if order == n: return i n = int(input()) print(nth_number(n)) 그냥 무식하게 666부터 시작해서 종말 숫자들을 계속 하나씩 세는 함수다...

티스토리툴바