학교 알고리즘 소모임에서 세미나로 1주 간격으로 알고리즘/자료구조 세미나를 진행한다. 저번 주에 약속 때문에 못 들었는데, 오늘 '이분탐색' 영상을 찾아서 다시 봤다. (오늘 주제는 우선순위 큐였음) 세미나는 백준 다이아.. 이상인 학우분들이 진행한다. (빡고수 ㄷㄷ) 이분 탐색을 하는 가장 큰 조건! '단조성이 있는 배열, 함수' 단조성은 우상향, 우하향, 오름차순, 내림차순과 같이 일정한 방향성을 띄는 성질을 얘기한다. 어떤 흐름(배열, 함수)에서 특정한 값을 탐색할 때 반으로 나눠서 탐색하는 것이다. 위 상황의 경우에는 특정 분기점(k)를 기준으로 true / false로 이어지는 단조성(우하향이라고 봐도 무방)을 갖는다. 이런 상황에서 좌/우 값을 좁혀가면서 찾는 것이 이분 탐색이다. 10816 ..

나는 이 포스트를 다시 봐야할 때에, 밑의 DFS 예제를 재귀함수 / 스택으로 구현해봐야하고, BFS 예제를 큐로 구현해봐야하고, 음료수 얼려먹기 / 미로 찾기 문제를 풀어야한다. 1번 노드와 연결되어 있는 것 [2, 3, 8] 2번 노드와 연결되어 있는 것[1, 7] 이런 식이다. 그리고, 방문 여부를 표현하는 1차원 리스트를 정해준다. 1번 노드로 시작한다 (방문 1) 1번 노드와 인접한 노드들 중 방문하지 않은 노드[2, 3, 8]로 굴린다. 2부터 시작한다. 2는 방문하지 않았으므로, 재귀한다 2번 노드로 시작한다 (방문 1, 2) 1은 방문 했으므로 7로 재귀한다. 7번 노드로 시작한다 (방문 1, 2, 7) 2는 방문 했으므로, 6으로 재귀한다. 6번 노드로 시작한다 (방문 1,2,7,6) 7..

- 내가 쓴 코드 - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 # NxN 지도를 만들 것인가? N, 그냥 좌표로 움직여도 될 듯. # 무시되는 제한 조건을 구현해야 한다. # LRUD를 구현해야 한다. N = size = int(input()) commands = list(input().split()) class traveler: def __init__(self): global size self.position = [1, 1] #y, x좌..

나동빈님의 이것이 코딩 테스트다 강의를 이용해서 공부하고 있다. 신찬수 교수님 강의도 짬짬이 병행하고 있는데, 원론 + 실전문제풀이 느낌이라 딱 좋다. - 맞힌 코드 - N이 10만까지이므로, 내 풀이방법처럼 할 수야 있지만, 좌측의 풀이방법의 시간복잡도에 비해 내 풀이의 시간복잡도가 높다. (n - target)으로 덩어리로 쳐내냐 vs (n-target)만큼 반복으로 -1로 쳐내냐 29와 5를 입력했다. 29와 5의 1차 타겟은 25다(가장 가까운 5로 나눌 수 있는 수) 29에서 25까지 4(N - target)를 빼야하므로, 시행횟수는 4가 더해진다(result +=) 그렇게 N은 target과 동일해진다. 25 < 5는 거짓이기 때문에 넘어간다. 25를 5로 나누고, 시행횟수를 1 더한다. (1..

어제 날라간 posfix 계산기를 다시 코딩해봤다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 def postfix_calculator(expression): operator = ['+', '-', '*', '/', '^', '%'] #'^', '%'는 '*', '/'와 동일한 우선순위를 갖는다. operand = ['0', '1', '2', '3', '4' ,'5'..

C언어에서 배열(Array)과 Python에서 List의 차이. + 파이썬 리스트 내부 구조 - seoyeon hwang님 C언어는, 1. 배열에 쓰일 자료형과 그 수를 지정해줘야 한다. 2. 배열에 원소가 저장되면, 메모리에 그 배열이 연속적으로 저장되고(값 자체), 첫 원소의 주소를 통해 원소들에 접근한다. 한편 Python은, 1. 자료형과 수를 지정해줄 필요가 없다. (내장 기능을 통한 resize와 작동원리로 인해) 2. C언어와 다르게, 이중으로 배열을 저장한다. (C언어는 메모리에 그 값 자체를 저장하고 배열의 주소를 이용해 호출하였지만, Python은 메모리에 그 값의 주소를 저장하고, 배열의 주소 - 값의 주소를 이용해 호출한다.) -> 이로 인해 자료의 type에 구애받지 않고 서로 다..

(컴맹을 위한 Go 언어 기초 프로그래밍 기초 강좌) Go라고 써있긴 하지만, 1~6강 동안에는 컴퓨터가 어떻게 작동하는지에 대한 원리를 설명해준다. 트랜지스터 - 논리소자 - 계산기 - 원시 컴퓨터(튜링/폰 노이만) - 현재의 컴퓨터로 빠르면서도 간결하게 얘기해줘서 진짜 기술의 발전이 컴퓨터에 집약되어 있구나 하는 생각이 들었다. 그 외에 언어별로 구분하는 동적/정적 언어에 대한 구분법(일종의)이나 컴파일러, 기계어와 같은 개념도 알게 되었다. 요리로 비유해서 컴퓨터의 동작을 설명하는 부분이 진짜 압권이다. 저장소(HDD - 마트)에서 bus(실제로 케이블 이름이 버스임)를 통해 메모리(냉장고)에 불러오고, 그 메모리에서 재료들을 '움큼'(필요한 것만 빼는게 아니라 근처 값들도) 꺼내서 도마(Cache..