Problem Solving

[알고리즘] 코딩테스트 합격을 위한, 나만의 알고리즘 로드맵 설정하기

[로드맵 단기목표] [목표를 달성하기 위해서 해야 할 일] 백준 2+,3+ class 문제 풀기 [완료] 1번을 하고 난 뒤 피드백 정리하기 [완료] Winter Coding 기출문제 15문제 풀고 정리 [완료] 부족한 유형 추가문제 풀기 [완료] sql 기출문제 풀기 [진행 상황] ① 백준 2+,3+ class 문제 풀기 ② 1번을 하고 난 뒤 피드백 정리하기 https://supersett-diary.tistory.com/258 [피드백] BFS문제 정리하기 오늘 알고리즘을 풀며 헷갈렸던 부분, 해결 방법 0. bfs를 해줄때 할 수 있는 장치들 ㅡ 주변의 값을 1씩 증가시켜가며 탐색한다. (모두 탐색하는데 얼마나 걸리는지) ㅡ 주변의 값을 방문 체크하 supersett-diary.tistory.co..

[피드백] BFS문제 정리하기

오늘 알고리즘을 풀며 헷갈렸던 부분, 해결 방법 0. bfs를 해줄때 할 수 있는 장치들 ㅡ 주변의 값을 1씩 증가시켜가며 탐색한다. (모두 탐색하는데 얼마나 걸리는지) ㅡ 주변의 값을 방문 체크하고 일괄적으로 값을 변경한다. ㅡ 주변의 값을 체크하면서 count 수를 늘려간다. (탐색하면서 몇개를 만났는지) 1. 2차원 배열과 그래프를 접목 시킬때, list = [[1,2,3,4] , [5,6,7,8] , [9,9,9,9]] (예)x,y = 1,2 인 부분의 값은 list[y][x] = list[2][1] = 9 (예)x,y = 0,1 인 부분의 값은 list[y][x] = list[1][0] = 5 2. 2차원 배열(m행 n열) 선언하기 #x,y #5 7 m,n=map(int,sys.stdin.rea..

[알고리즘][왜이거써요?]list 와 deque, 분기를 잡자, 자주쓰는 list 함수

1. 이런 경우에는 list보다는 deque를 사용하는건 어떨까? → 첫번째 값을 넣고 뺴고를 자주 해야할 상황 첫번째 원소를 추가 삭제한다면 극명한 속도 차이가 발생 덱과는 다르게 python의 리스트는 fixed size memory blocks(array)로 구현되어 있습니다. 이름은 List여서 링크드 리스트처럼 보이지만 고정된 사이즈의 메모리를 갖는 array 형태입니다. 리스트의 마지막 원소를 삭제는 O(1)이지만, 아래 그림처럼 첫번째 원소를 삭제하면 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)입니다. 삽입, 삭제의 operation()이 앞, 뒤, 중간 등에서 발생한다면 list 보다는 deque 사용을 우선적으로 고려하는 것이 속도 측면에서는 훨씬 좋을 것 2. ..

[백준][파이썬] 1662 - 압축

배열에는 튜플도 추가할 수 있다! 애용하자 stack.append((temp,length-1)) length=0 multi,preL=stack.pop() HTML 삽입 미리보기할 수 없는 소스

[백준][파이썬] 2504 - 괄호의 값 (런타임에러 발생..해결)

런타임 에러 (IndexError) 왜 발생했을까? 답은 스택 배열이 비어있는 상태에서 stack[-1]의 값을 조회할때 에러가 발생하는것이었다. 비어있는 상태라면 조회를 할수없게 코드를 분리해서 해결하였다. 파이썬에서의 Stack 은 List를 활용하자! append() : 마지막에 값추가 pop() : 마지막에 들어온 값 제거 (반환받아서 값을 사용할수도 있음) list[-1] : 제일 top에 있는 값 조회 가능 ( 비어있을때 조회시 에러 발생하므로 유의할것) not list : 비어있는지 확인 입력값을 받을때 rstrip()을 꼭 사용하자! (주의) HTML 삽입 미리보기할 수 없는 소스 위 아래의 입력된 값이 달라서 len(입력값)에 차이가 있었다. 주의하자 제출 코드 HTML 삽입 미리보기할 ..

[백준] 1931 - 회의실 배정 (그리디 알고리즘)

[시간초과 요인 분석] - 이전의 코드는 O(n^2)였지만 O(n)으로 줄어들었다. - 정렬을 한번 더 했어야 했다. - 바로 머릿속에 있는대로 구현하기보다는 (모든것을 확인하려고 했었음), 불필요한것은 덜어낸 채로 찾아보는 방법을 더 생각해 보도록 하자.(시간초과와 관련이 있음) #회의 시작시간 순으로 배열을 정렬한다. sch=sorted(sch,key = lambda x: [x[1], x[0]]) [처음 코드] import sys n=int(sys.stdin.readline()) sch=[] #회의의 시작시간 S , 마치는시간 E 를 sch 배열에 담는다. for i in range(n): S,T=map(int,sys.stdin.readline().split()) sch.append([S,T]) #회..

[백준]1946 - 신입사원

import sys t = int(sys.stdin.readline().strip()) for _ in range(t): n = int(sys.stdin.readline().strip()) worker = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)] worker.sort() min_ = workers[0][1] cnt = 1 for i in range(n): rank = workers[i][1] if rank < min_: min_ = rank cnt += 1 print(cnt)

[백준] [파이썬] 11497 - 통나무 건너뛰기

드디어 혼자 풀었다. 너무 행복하다... 여기서 내가 구글링했던 정보들 1. 배열요소 앞, 뒤 추가 deque를 import 해와서 앞뒤에 값을 추가해주는 appendleft() , append()를 사용했다. 정보를 내가 원하는대로 정렬한 뒤 다시 list에 담아서 다음 작업을 진행했다. from collections import deque my_list = [2, 9, 3] deq = deque(my_list) deq.appendleft('a') new_list = list(deq) print(new_list) 2. 절대값 abs('원하는값') 3. 나의 제출 코드 import sys from collections import deque #절대값 abs(,,) n=int(sys.stdin.readli..

[백준][파이썬] - 1263 시간관리

원리는 알겠는데 내마음대로 while문과 for 문을 사용한다는게 어려웠다. 지금 잘못된게 있는데 안보인다 내일 다시 봐야지 import sys n=int(sys.stdin.readline()) todo=[] for x in range(n): input_list=list(map(int,sys.stdin.readline().split())) input_list.reverse() todo.append(input_list) todo.sort() print(todo) time=0 while True: sumtime=time for x in todo: if (time + x[1])

[백준] 1522 - 슬라이딩 윈도우

a가 연속적이여야 한다는 말은 a가 a의 개수 만큼 연속적으로 위치해야 한다는 뜻이다. 예를 들어, "ababa" 라는 문자열이 있다면, a가 3개이므로 "aaabb", "baaab", "bbaaa".... 등 a가 3개 연속적으로 위치해야한다. 따라서, 인덱스 0 부터 끝까지 a의 개수 만큼의 길이를 슬라이딩 윈도우로 생각하고 b의 개수를 세면 b를 교환하면 된다. 예를 들어, "ababa" 라는 문자열이 있다고 하자. 이때 a의 개수는 3개이다. 인덱스 0 : ababa -> b가 1개 -> 한 번의 교환 필요 인덱스 1 : ababa -> b가 2개 -> 두 번의 교환 필요 인덱스 2 : ababa -> b가 1개 -> 한 번의 교환 필요 인덱스 3 : ababa -> b가 1개 -> 한 번의 교환..

[백준]1254 - 팰린드롬 만들기

- 반복문을 통해 문자열의 문자를 확인한다. - i번째로 시작한 문자열과 i번째로 시작한 문자열을 뒤에서부터 확인한 문자열을 비교한다. - 두 문자열이 같을 경우 i번째 이전에 문자들을 문자열 뒤에 추가하면 팰린드롬을 만들 수 있다. - 현재 문자열의 개수와 i번째 이전에 문자의 개수를 더해서 출력한다. import sys word = str(sys.stdin.readline().rstrip("\n")) # 반복문을 통해 문자를 확인 for i in range(len(word)): # i번째로 시작한 문자열과 i번째로 시작한 문자를 뒤에서부터 확인한 문자열을 확인 # 같을 경우 i번째 이전에 문자가 다른 것으로 문자열 뒤에 추가해주면 된다. if word[i:] == word[i:][::-1]: prin..

KMP 알고리즘 : 문자열 검색 알고리즘 (백준-16916)

▶N문자열에서 M문자열을 검색할 때? 가장 단순한 문자열 검색 : O(NM) KMP 알고리즘 : O(N+M) [PI 배열] pi[i]는 주어진 문자열의 0~i 까지의 부분 문자열 중에서 prefix == suffix가 될 수 있는 부분 문자열 중에서 가장 긴 것의 길이 (이때 prefix가 0~i 까지의 부분 문자열과 같으면 안된다.) [KMP 알고리즘] - j-1번째 까지 탐색을 했는데 문자열이 일치 했고 j번째 문자열에서 i번째 문제열과 다를 경우 -> 0~j-1번째 까지의 pi배열에서 패턴이 있는지 확인한다. -> 즉 pi[j-1]값이 있는지 확인(코드에서는-> j>0 이 부분) 1, k라는 값이 있다면 j는 k라는 값을 가지게 되고 j번째 문자열과 i번째 문자열을 비교한다! => 이 때 j가 0보..