본문 바로가기

Algorithm

 (38)
Algorithm/LeetCode LeetCode #206 - Reverse Linked List(역순 연결 리스트) 풀이 문제 문제의 내용을 요약하면, 연결 리스트를 역순으로 재구성한 후 반환하여야 한다. 풀이 이 문제는 21. Merge Two Sorted Lists와 같이 새로운 노드를 생성하는 방식으로 해결하는데, 문제에서 주어진 예시로 과정을 나타내보면 다음과 같다. 더미 노드 생성 현재 노드(current)를 연결 리스트의 head로 정하고, 새로운 노드(node를 None으로 초기화한다. current, node = head, None 반복하며 스와핑 현재 노드 즉, 기존 연결 리스트의 head가 되는 모든 노드를 탐색하며 새로운 노드로 값을 넘겨준다. 이 과정을 다음과 같이 나타낼 수 있다. 첫 번째 반복 current: ListNode: [1 -> 2 -> 3 -> 4 -> 5] 1) next = ListNo..
Algorithm/LeetCode LeetCode #021 - Merge Two Sorted Lists(두 개의 연결 리스트 병합) 풀이 문제 문제내용을 살펴보면, 정렬된 두 개의 연결 리스트의 노드를 결합하여 다음 그림과 같이 하나의 정렬된 연결 리스트로 병합하여야 한다. 본 내용은 leetcode에서 제공한 아래 그림을 토대로 작성하였기 때문에 그림 1(node2로 이동), 그림 5(node1로 이동)와 같이 값이 동일한 경우 포인터를 어디로 변경할 것인지 헷갈릴 수 있다. 결론만 말하자면, 두 개의 노드 값이 동일한 경우 node1, node2 중 아무거나 선택해도 무방하다. 풀이 문제에서 주어진 예시(list1 = [1, 2, 4], list2 = [1, 3, 4])를 그림으로 나타내면 다음과 같다. 이 둘은 노드의 값을 기준으로 오름차순으로 정렬되어 있으며, 가장 왼쪽에 있는 노드가 각 연결 리스트의 head라고 할 수 있다. 그..
Algorithm/개념정리 자료 구조(Data Structure)의 큐(Queue) 개념 정리 들어가며 지난 포스팅에 이어서 이번에는 큐에 대해 공부한 내용을 정리해보았다. 큐 스택과 달리 큐(queue)는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out) 방식으로 데이터 입/출력을 처리한다. 선입선출은 신선도를 고려한 편의점과 마트의 상품 진열 방식을 생각하면 이해하기 쉽다. 즉, 데이터를 맨 뒤에서 넣고 앞에서 꺼내는데, 이를 각각 인큐(enqueue)와 디큐(dequeue)라고 한다. 이와 같이 큐는 맨끝에서 맨앞으로 데이터를 밀어넣어 꺼내는 방식이며, 큐의 맨 앞의 원소를 프론트(front)라고 하고, 맨 뒤의 원소를 리어(rear)라고 한다. 예를 들어, 인큐와 디큐를 간단히 나타내면 다음과 같다. queue = [] 1. enqueue(1..
Algorithm/개념정리 자료 구조(Data Structure)의 스택(Stack) 개념 정리 들어가며 알고리즘 문제를 풀 때 리스트(이하, 배열)로는 해결하기 어려운 경우가 있으며, 이와 같은 상황에서는 스택이나 큐를 사용해야 한다. 따라서, 이번에는 스택에 대해서 공부한 내용을 정리해보았다. 스택 스택(stack)은 '마룬 풀을 쌓은 더미', '겹겹이 쌓음'을 뜻하는 단어로, 데이터가 쌓인 데이터 집합이라고 할 수 있다. 이는 데이터를 임시 저장할 때 사용하는 자료구조이며, 후입선출(LIFO, Last In First Out) 방식으로 데이터를 입/출력할 수 있다. 즉, 데이터를 맨 위에서부터 쌓고, 맨 위에서부터 꺼낸다는 의미이며, 이를 각각 푸쉬(push), 팝(pop)이라고 한다. 예를 들어, 푸쉬와 팝을 간단히 나타내면 다음과 같다. stack : [] 1. push(1) → stack..
Algorithm/개념정리 검색 알고리즘(Search Algorithm)의 해시법(체인법과 오픈 주소법) 개념 정리 들어가며 해시법에 대해 다루기 전에 한 가지 경우를 살펴보도록 하자. 만약, 아래와 같은 배열에서 a[2]에 새로운 원소 6를 추가하는 경우, 일반적인 배열에서의 처리 과정은 다음과 같을 것이다. a = [1, 7, 10, 13, 16, 22] a[0](=1)와 a[1](=7)사이에 새로운 값이 추가될 수 있도록 이진 검색으로 검색 a[0](=1) 이후의 모든 원소를 한 칸씩 뒤로 이동 a[1](=None)에 새로운 원소 6을 대입 이와 같이 데이터 추가 또는 삭제 시 배열의 원소가 이동하는데 필요한 복잡도는 O(n)이고, 이는 배열의 크기가 커짐에 따라 그 비용 또한 커질 수 밖에 없다는 것을 의미한다. 해시법 해시법은 간단한 연산을 통해 데이터 저장 위치 = 인덱스를 구하는 방법으로, 데이터 검색 뿐..
Algorithm/개념정리 검색 알고리즘(Search Algorithm)의 선형 검색과 이진 검색 개념 정리 들어가며 어떠한 데이터 집합에서 원하는 값의 원소를 찾아내는 것을 검색이라고 하고, 이를 알고리즘으로 구현한 것이 바로 검색 알고리즘이다. 예를 들어, 우리가 주소록에서 누군가를 검색한다고 가정했을 때 다음과 같은 다양한 조건으로 검색할 수 있다. 성별이 남자인 사람 나이가 20세 이상인 사람 이름에 '영'자가 포함된 사람 위 검색 조건은 성별, 나이, 이름과 같이 특정 항목에 주목하고 있는데, 검색 알고리즘에서는 이를 키(key)라고 하며, 이는 대부분 데이터의 일부이다. 성별 : key와 일치하도록 지정 나이 : key가 포함되도록 범위 지정 이름 : key에 가깝도록 지정 가장 대표적인 검색 알고리즘으로는 배열 검색, 연결 리스트 검색, 이진 트리 검색이 있으나, 본 글에서는 배열 검색에 대해서만 ..
Algorithm/개념정리 [자료구조] 이진트리(Binary Tree) 생성 개념 정리 들어가며 사이버 대학교 특성 상 직장을 다니면서 자유롭게 학습할 수 있는 환경을 제공해준다. 그러나, 직장에서 야근, 주말 출근이 잦은 경우에는 출석체크 정도만 할 수 있고, 제대로 된 공부를 할 수 없다는 큰 단점이 있다. 필자 또한 약 2년 6개월 간의 직장생활을 하는 동안 잦은 야근, 거의 매주 출근으로 인해 시험을 보기 위한 벼락치기 외에는 제대로 된 학습을 수행하지 못했다. 현재는 퇴사하고 시간이 남아돌아서 토이 프로젝트를 하며, 공부하던 중 이진트리에 대해 제대로 학습하자는 취지로 본 글을 작성하였다. 1. 이진트리 이진트리에 대한 정의는 구글에 검색하면 긴 글과 다양한 전문 용어로 잘 나와있기 대문에 따로 언급하지 않겠으나, 쉽게 말하자면 아래 그림과 같이 크게 두 갈래로 나뉜 트리라고 할 ..
Algorithm/Baekjoon 2869번(달팽이는 올라가고 싶다) 파이썬(Python) 풀이 공유 들어가며 문제의 내용을 보기 전에 꽤 낮은 정답률(28.049%)을 보고 흥미가 더 생겼던 문제이다. 그런데, 생각보다 매우 간단한 문제라서 허무하게 끝난 것 같다. 아래 그림은 어려울 것 같은 문제는 비교적 쉽게 풀리고, 쉬울 것만 같은 문제는 생각하지 못한 곳에서 오류가 발생하는 상황을 너무나도 잘 나타내주어 정말 공감된다. 문제 2869번 달팽이는 올라가고 싶다 시간 제한 메모리 제한 0.15 초(추가 시간 없음) 128 MB 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구..
Algorithm/Baekjoon 2292번(벌집) 파이썬(Python) 풀이 공유 들어가며 나를 알 수 없는 늪으로 빠지게 한 문제이다. 문과 출신이라 그런지 수학이랑 그다지 친하지는 않은데도 불구하고 가우스 공식을 코딩에 접한 이후로 공식 만드는 재미에 빠져서 공식을 세우기 위해 약 한 시간 가량을 삽질했지만, 결국에는 whlie 문으로 해결하였다. 1. 문제 2292번 벌집 시간 제한 메모리 제한 2 초 128 MB 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3..
Algorithm/Baekjoon 1712번(손익분기점) 파이썬(Python) 풀이 공유 들어가며 처음 문제에 접근했을 때에는 while 문으로 수량을 파악하려고 하였으나, 세 번째 테스트케이스를 보고난 이후에는 생각이 완전히 바뀌었다. 세 번째 테스트케이스를 적용하는 경우 약 20억 번의 반복을 수행해야 하는데, 이럴 경우에는 문제에서 요구하는 시간 제한(0.35초)를 초과하기 때문이다. 따라서, 문제에서 요구하는 손익분기점의 의미를 먼저 파악한 다음에 규칙을 찾고, 코드를 작성하였다. 1. 문제 1712번 손익분기점 시간 제한 메모리 제한 0.35초 128 MB 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다..

티스토리툴바