분류 전체보기

드디어!!! 1주차가 끝났다아아~먼가 빨리 지나간 것 같은데, 1주일동안 한 공부양을 보면 빨리 지나간건 또 아닌듯.아침에 시험봐서 그런가 걍 개개ㅐㄱ 오늘 개개개 무기력했음. 집이었다면 게임하다 잤겟지..하지만??여기서는 그럴수가 없다~ 해야지 뭐 어떡해~해시 정의와 성질해시 자료구조 : 키에 대응되는 값을 저장하는 자료구조insert, erase, find, update → O(N) 해시 함수: 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수* 이상적인 상황 → O(1), 충돌이 빈번한 경우 성능 저하, 최악의 상황 → O(N)각 키의 해시 값이 최대한 균등하게 퍼져야 성능이 좋아지기 때문에 좋은 해시 함수를 정해야 함! 충돌서로 다른 키가 같은 해시 값을 가진 경우 충돌이 일어난다. 충..

https://www.acmicpc.net/problem/2630✔ 유형 : 이분 탐색✔ 문제 풀이: 큰 문제를 작은 문제로 분할하여 작은 문제부터 순차적으로 해결한 뒤 결과를 합한다.  탐색할 영역의 제일 왼쪽 위의 색을 저장해두고, 이중 for문으로 다른 색이 포함되어 있는지 확인한다.만약 다른 색이 포함되어있다면 각 면을 N/2로 나눠서 총 4 부분으로 나눈다.계속 나누다가 언젠간 한면이 1이되면 해당 색을 배열에 저장한다. 만약 한 구역을 검사했는데 모두 같은 색이라면 해당 색을 배열에 저장한 후 함수를 리턴한다. 위의 방법을 아래의 코드로 나타내었다. import sysinput=sys.stdin.readline # input함수 바꾸기import copy#inputN = int(input())..

https://www.acmicpc.net/problem/2805✔ 유형 : 이분 탐색✔ 문제 풀이: 리스트 양쪽에 start와 end 피벗을 두고 범위를 좁혀가며 답을 찾는다.   #2850 나무자르기#이분 탐색import sysinput=sys.stdin.readline # input함수 바꾸기N, M = map(int, input().split())trees = list(map(int, input().split(' ')))st, en = 0, max(trees) # 최소 최대값!while st mid: #톱날보다 긴 나무들만. count += tree - mid # 톱날h만큼 자른다 if count >= M: # 구하려는 나무길이보다 크면 더 잘라야하므로 s..

장마철이라 매일 같이 비오다가 오랜만에 정말 맑은 하늘이 떴다. 오랜만에 광합성이라 매우 좋았다. 그거와 별개로 오늘 Week 1 마지막 날이었는데. 정말 많은 일이 있었던 것 같다. 이렇게 집중해서 많은 양의 코딩 테스트를 한적이 거의 없었는데, 짧은 일주일동안 몰입해서 열심히 공부한 것 같다. 비록 모든 과제를 완료하진 못했지만, 80퍼 이상 한 것에 의의를 두고 있다~이분 탐색정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법 주의 사항1. 이분 탐색을 하려고 한다면 주어진 배열이 정렬되어 있어야 한다.2. 무한 루프에 빠지지 않게 mid 값을 정해야 한다.

https://www.acmicpc.net/problem/3190 ✔ 유형 : 큐✔ 문제 풀이: 뱀이 지나가는 맵의 좌표를 큐를 이용한다. ✨Key Point1. 뱀의 이동 좌표 2. 회전 3. 게임 종료 조건   (1) 위치가 index 범위 밖일 떄   (2) 스스로 부딪혔을 때 →  map[][] 2차원 배열에 현재 맵상태를 기록해두고 확인한다.ex ) 0 일경우 빈 맵, 1일경우 뱀이 위치해있음. 2일경우 사과가 있음. 코드import sysimport collections input=sys.stdin.readline # input함수 바꾸기dequeu = collections.deque#inputN = int(input()) # 보드의 크기K = int(input()) # 사과의 개수#사과의 위..

https://www.acmicpc.net/problem/2493 ✔ 유형 : 스택✔ 문제 풀이: 반복문으로 검사하면 최악의 경우 O(N^2)의 시간복잡도가 나온다. 이를 해결하기 위해 stack을 이용한다. 구해야 하는 답: 각 탑에서 발사한 레이저 신호를 수신한 탑의 번호 리스트.  코드import sysinput=sys.stdin.readline # input함수 바꾸기# inputN = int(input())towers = list(map(int,input().split())) #list 자료구조지만 스택 사용 가능stack = list()answer = [0 for i in range(N)]# 2. for i in range(N): # 1. 현재 스택에 값이 존재한다면? while(s..

오늘은 일기를 생략하겠다 너무 졸립다..안뇽Quick Sort 퀵 솔트는 매 단계마다 Pivot이라는 이름이 붙은 원소 하나를 차례로 보내는 정렬법이다.  장점1. 추가적인 공간이 필요하지 않다.2. 배열 안에서의 자리 바꿈으로 처리한다. → Cache Hit 비율이 높다! (속도가 빠르다)In Place Sort원소위치를 잘 바꿔주면 되기 떄문에 추가적인 공간이 필요 없다.  정렬 과정 시간 복잡도 평균 : O(N LgN)최악: O(N^2) Quick Sort VS Merge Sort Merge SortQuick Sort시간복잡도O(NlgN)평균 O(NlogN)최악 O(N^2)평균적으로 Merge Sort 보다 빠르다.추가적으로 필요한 공간(overhead)O(N)O(1)Stable Sort 여부OX

오늘 코치님과 면담을 했다. 슬랙에 커피챗 신청 공지가 올라와서 냅다 해버렸다..예전에는 뭔가 내 자신에 대해 확신이 없어서, 이런 자리들을 항상 피해왔던 것 같다. 하지만, 이전 대외활동을 하면서, 현재 상태의 나를 인정하고 나에게 도움을 줄 수 있는 사람에게 나의 상태를 보여주는게 나를 발전시키는 일이라는 것을 뒤늦게 깨달았다. 질문을 어떻게 해야할지 잘 모르겠었는데, 올려주신 파인만 질문법 영상을 보면서 많은 도움이 됐다.미리 질문을 메모장에 써놨지만, 그 영상대로 질문을 잘하진 못한 것 같아서 아쉽다. 면담을 하면서 내 상황에 대해 스스로 말하다 보니, 지금 어떤 것을 중요하게 여겨야 하는지 알 것 같았다. 집에서 공부를 할 때는 기한도 없고, 누가 강제적으로 주는 과제도 없었다. 그냥 흘러가는 ..

https://www.acmicpc.net/problem/11866✔ 유형 : 큐✔ 문제 풀이: 큐의 성질 이용. push, pop import sysimport collectionsinput=sys.stdin.readline # input함수 바꾸기size, gap = map(int, input().split())q = collections.deque()for i in range(1,size+1): q.append(i) result = list()i = 0while(len(result) ') break if idx==0: print('') else: print(result[idx], end=', ')

https://www.acmicpc.net/problem/2468✔ 유형 : 완전 탐색✔ 문제 풀이: BFS

https://www.acmicpc.net/problem/10971✔ 유형 : 완전 탐색✔ 문제 풀이:  # 외판원 순환# 입력N = int(input())W=[[*map(int,input().split())] for _ in range(N)] # 정리 해두기 N행 배열 입력 받는 법min_cost = 1e9visited = [False for _ in range(N)] # 방문 여부temp = list()def go(depth, cost)->int: global min_cost if(cost >= min_cost) : return if( depth == N ): if W[temp[N-1]][temp[0]] == 0 : return #print(f..

https://www.acmicpc.net/problem/2309 ✔ 유형 : 완전 탐색✔ 문제 풀이:  def find(): smalls = list() for i in range(9): height = int(input()) smalls.append(height) for i in range(9): for j in range(i+1, 9): odd = smalls[i] + smalls[j] if sum(smalls) - odd == 100: if i > j : i , j = j , i smalls.pop(j) ..