전체 글38 [1주차-2] 코딩테스트 연습 - 연결리스트와 스택(2) 연결리스트(더미 노드 포함) 더미 노드(dummy node)를 사용하면 기존의 연결리스트에서 '특정 번째 수’를 알려주고 뒤의 노드를 삽입/삭제하는 것이 아니라 “특정 원소의 바로 다음”을 지정하여 노드를 주고 뒤의 노드를 삽입/삭제하는 방식으로 변형을 가할 수 있다. 더미 노드(dummy node)란 0번째 노드를 만들어 내용물이 들어있지 않은 노드로 이를 헤드에 추가하여 더미 노드를 포함한 연결리스트를 구현할 수 있다. 더미 노드를 사용하면 리스트의 양 끝값을 처리할 때, 코드가 간편해진다는 장점이 있다. 기존의 연결리스트를 구현하는 코드에서 변경사항이 있는데 다음 코드를 참고해보자. class Node: def __init__(self, item): self.data = item self.next .. 2023. 4. 11. [1주차-2] 코딩테스트 연습 - 연결리스트와 스택(1) 연결리스트 연결리스트는 각 원소를 줄줄이 엮어서 관리하는 방식이다. 각각의 아이템(node)에는 데이터(data)와 다음 데이터를 가리키는 링크(link)가 담겨 있다. 리스트의 맨 앞은 ‘헤드(head)’라고 하고 맨 끝은 ‘테일(tail)’이라고 한다. 연결리스트는 원소를 삭제하거나 다른 원소를 삽입하는 것이 선형배열의 경우보다 빠르다. 하지만 메모리 소요가 크고 특정 원소를 참조하는 데 선형배열보다 시간이 오래 걸린다는 단점이 있다. [기본 구조] class LinkedList: class Node: def __init__(self, item): self.data = item self.next = None def __init__(self): self.nodeCount = 0 self.head = N.. 2023. 4. 11. 프로그래머스 - 공원 산책 문제 지나다니는 길을 'O', 장애물을 'X'로 나타낸 직사각형 격자 모양의 공원에서 로봇 강아지가 산책을 하려합니다. 산책은 로봇 강아지에 미리 입력된 명령에 따라 진행하며, 명령은 다음과 같은 형식으로 주어집니다. ["방향 거리", "방향 거리" … ] 예를 들어 "E 5"는 로봇 강아지가 현재 위치에서 동쪽으로 5칸 이동했다는 의미입니다. 로봇 강아지는 명령을 수행하기 전에 다음 두 가지를 먼저 확인합니다. 1) 주어진 방향으로 이동할 때 공원을 벗어나는지 확인합니다. 2) 주어진 방향으로 이동 중 장애물을 만나는지 확인합니다. 위 두 가지중 어느 하나라도 해당된다면, 로봇 강아지는 해당 명령을 무시하고 다음 명령을 수행합니다. 공원의 가로 길이가 W, 세로 길이가 H라고 할 때, 공원의 좌측 상단.. 2023. 4. 10. [1주차-1] 코딩테스트 연습 - 선형배열과 재귀 알고리즘 파이썬에서 이미 데이터 타입을 제공하더라도 기본적인 데이터 타입만으로 해결할 수 없는 문제가 있을 수 있다. 예를 들어, 파이썬 내장함수인 max 함수는 모든 원소를 다 탐색하므로 리스트의 길이만큼의 시간이 걸린다. 즉 자료의 길이가 길어질수록 소요 시간이 오래 걸린다. 1. 선형배열 파이썬에서 배열은 리스트라는 데이터형으로 제공된다. list.append() #원소 덧붙이기 list.pop() #원소 하나 꺼내기 위의 두 작업은 시간 복잡도가 O(1)이므로 실행시간을 최소로 할 수 있다. 물론 list.pop(n)처럼 인덱스를 지정해주면 시간 복잡도가 O(n)이 된다. list.insert() #원소 삽입하기 del list[n] #원소 삭제하기 list.index() #원소 위치 찾기, 해당 원소가 .. 2023. 4. 10. [220908] SQL(postgres) 기초 2 ##join join이 필요한 이유: 필요한 정보(상품명, 유저정보, 카테고리 정보 등)가 각기 다른 테이블에 분산 저장되어 있을 때, 이를 하나의 테이블로 가져와 보기 좋게 데이터를 추출하기 위해 join의 위치 및 문법 select 컬럼명 from 테이블명 (as) a join 테이블명2 (as) b on a.컬럼명 = b.컬럼명 두 개의 테이블에서 교집합으로 나타나는 부분만 필터링되는 효과까지 있다. #inner join: 속도가 빠름 #left join: 이 두 가지가 가장 중요함 right join은 left join으로 바꾸어서 사용하면 됨 full join은 초보자 수준에서는 잘 쓰지 않음 1. 행 중복! category_id 값이 같은 값이면 중복이 일어남 2. where절 실수 where.. 2022. 9. 8. [220901] SQL(postgres) 기초 1 [모든 컬럼 추출하기] select * from (파일명) ctrl+enter를 누르면 실행됨 [특정 컬럼 추출하기] select category, yyyy, mm from (파일명) [중복값 없이 특정 컬럼 추출하기] select distinct category form (파일명) select distinct yyyy, mm from (파일명) [특정 연도의 매출 탐색: where] 1) 숫자열 select * from gmv_trend where yyyy = 2021 where yyyy >= 2019 where yyyy between 2018 and 2020 where yyyy != 2021 where yyyy 2021 ->같지 않음(!=와 같은 역할) 1) 문자열 (=, !=, like, in, n.. 2022. 9. 1. [220817] 백준 12단계/ 문자열 집합(14425) 문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다. 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. 출력 첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다. 예제 입력 1 5 11 baekjoononlinejudge startlin.. 2022. 8. 17. [220816] 백준 12단계/ 숫자 카드(10815) 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이.. 2022. 8. 16. 이전 1 2 3 다음
