본문 바로가기

스터디-공부/알고리즘13

단방향 연결리스트의 중간 노드 삭제 중간 노드 삭제: 단방향 연결리스트가 주어졌을 떄 중간(정확히는 가운데 노드일 필요는 없고 처음과 끝 노드만 아니면 된다)에 있는 노드 하나를 삭제하는 알고리즘을 구현하라. 단, 삭제할 노드에만 접근할 수 있다. 삭제할 노드(A) 접근 → 다음 노드(B = A.next) 접근 → A.next = B.next, A.value = B.value 하면 A 노드가 사라지게 된다. 코드 class Node: def __init__(self, val=0, next=None): self.val = val self.next = next def delete_node_in_middle(node_to_delete): # 첫 번째 노드나 마지막 노드는 삭제할 수 없다고 명시되어 있기 때문에 고려하지 않음. # 다음 노드의 값.. 2023. 8. 24.
정렬되어있지 않은 연결리스트의 중복 없애기 중복 없애기: 정렬되어있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라 (+ 임시 버퍼를 사용할 수 없다면 어떻게 풀 수 있을까?) 문제를 듣고 바로 든 생각 Set을 이용하여 풀 수 있지 않을까? 임시 버퍼가 없다면 반복문 2개로 해결할 수 있지 않을까? 해결 코드는 따로 적지 않는다. python에서 LinkedList를 구현 위한 Node Class 정의하기. 아래와 같이 Class를 정의 할 수 있다. class Node: def __init__(self, val=0, next=None): self.val = val self.next = next 정의된 Node Class는 아래와 같이 사용할 수 있다. node2 = Node(2) node1 = Node(.. 2023. 8. 23.
문자열 회전 문자열 회전: 한 단어가 다른 문자열에 포함되어 있는 판별하는 isSubstring이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌고, s2가 s1을 회전시킨 결과인지 판별하고자 한다(가령 'waterbottle'은 'erbottlewat'을 회전시켜 얻을 수 있는 문자열이다). isSubstring 메서드를 한 번만 호출해서 판별할 수 있는 코드를 작성하라. 그냥 문자열 length 만큼 한칸씩 돌려가면서 일치하는 경우가 있는지 확인하면 되는거 아닌가 생각이 들었다. def is_substring(a, b): char_array = list(b) for i in range(len(char_array)): char = char_array.pop(0) char_array.append(char.. 2023. 8. 22.
행렬 90도 회전 #### 행렬 회전: 이미지를 표현하는 N x N 행렬이 있다. 이미지의 각 픽셀은 4바이트로 표현된다. 이때, 이미지를 90도 회전시키는 메서드를 작성하라. 행렬을 추가로 사용하지 않고서도 할 수 있겠는가? - N x N 행렬 - 90도 회전 - 행렬 추가 사용 금지 위 조건들을 기반으로 생각을 해보자. 일단 행렬 추가 사용 금지 라고 했기 때문에 swap 하는 방식으로 처리가 되야 할 것이다. 문제를 간략화해서 다음과 같이 생각해보자. 아래와 같은 행렬이 있다고 하자. ``` [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16] ] ``` 이 행렬을 90도 회전하면 다음과 같을 것이다. ``` [ [13, 9, 5, 1], [14, 10, .. 2023. 8. 21.
문자열 매칭 수 계산 하나 빼기: 문자열을 편집하는 방법에는 세 가지 종류가 있다. 문자 삽입, 문제 삭제, 문자 교체. 문자열 두 개가 주어졌을 때, 문자열을 같게 만들기 위한 편집횟수가 1회 이내인지 확인하는 함수를 작성하라 예시 pale, ple → true pales, pale → true pale, bale → true pale, bake → false 문자열 매칭 수 >= 긴 문자열의 length - 1 이면 true를 반환하게 처리 import difflib def get_matching_character_count(str1, str2): matcher = difflib.SequenceMatcher(None, str1, str2) matching_blocks = matcher.get_matching_blocks(.. 2023. 8. 19.
문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메소드를 작성하라. URL화: 문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메소드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종 길이가 함께 주어진다고 가정해도 된다 (자바로 구현한다면 배열 안에서 작업할 수 있도록 문자 배열(character array)을 이용하길 바란다). URL 인코딩에 대해 궁금하다면 https://en.wikipedia.org/wiki/URL_encoding 을 참고하자. 한국어 위키에는 퍼센트 인코딩 이라고 되어있다. 이 문제를 해결하는 가장 쉬운 방법은 replace를 하는것 이겠지만, 그 것을 묻는 것은 아닐 것이다. 이 문제는 문자로 구성된 배열(character array)을 이용해 문제를 풀기를 원했고 최종적으로.. 2023. 8. 18.

티스토리툴바