본문 바로가기

분류 전체보기

 (351)
[BOJ] 16987. 계란으로 계란치기 Python https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 1. 해결방법 문제를 이해하면 백트레킹이라는 것을 알 수 있지만, 이해도 어렵고 문장도 길어서 어떤 알고리즘인지 찾아내기가 꽤 어려웠다. 문제 이해하는데만 20~30분 정도는 걸린 것 같다. 이 문제에 대한 접근은 왼쪽부터 계란을 집어서 다른 계란을 때리는 것이다. 이 때, 내구도와 무게에 따라 들고있는 계란이 깨지는지 다른 계란이 깨지는지의 경우를 고려해야한다. 조건을 생각해 보면..
[BOJ] 4358. 생태학 Python https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 1. 해결방법 파이썬 딕셔너리를 활용해서 해결하는 방법이 가장 적절하다. 1. while문으로 나무의 종을 입력받고, 그것을 딕셔너리에 저장한다. 2. 저장할 때, 입력받은 나무가 이미 딕셔너리에 있다면? => 해당 나무의 value를 + 1 한다. 3. 시간복잡도를 고려해서 while 문 안에 나무를 입력받으면서 idx 총 개수를 카운팅한다. 4. 알파벳 순으로 정렬. 5. 정렬한 딕..
[BOJ] 2075. N번째 큰 수 Python https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 1. 해결방법 음... 솔직히 heapq 알고리즘에 대해서 완벽히 이해와 시간복잡도 또는 메모리에 대해서 잘 알고 있지 않는 이상 과연 heapq 를 떠올릴 수 있을까?? 이 문제는 뇌빼기 코딩으로 2차원 배열을 저장하고 2중 for문을 한번 더 돌아서 리스트에 저장한 다음, 정렬해서 찾으려고 한다면 시간복잡도는 어떻게든 되겠지만 메모리라는 벽에 부딪혀 버린다. 가장 중요한 포인트는 heapq 라이브러리..
[BOJ] 11279. 최대 힙 Python, Java https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 해결방법 heapq 우선순위 큐 문제이다. python 의 우선순위 큐가 있는지는 공부 역량이 부족해서 잘 모르지만, heapq로도 가능하다. 1. heap이라는 리스트를 빈 값으로 생성. 2. 입력받은 정수 x가 0이 아닌 정수라면, heap에 삽입. 3. 삽입할 때, 문제의 목적이 최대 값을 뽑아야 하므로 -x를 삽입한다. 4. x가 0일 때, heap이 빈 상태라..
[DB] INDEX 인덱스 1. 데이터베이스에 있어서 인덱스란? 데이터베이스의 모든 테이블을 검색해서 원하는 결과를 가져오려면 시간이 오래 걸린다. 그래서 컬럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어서 검색 및 정렬 속도를 향상시키는 목적으로 만든다. 인덱스는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는데는 빠르지만 새로운 값을 추가하거나 수정, 삭제하는 경우에는 쿼리문 실행 속도가 느려지는 문제가 있다. 즉, 인덱스는 DB에서 데이터의 저장 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능이다. 인덱스의 장점 테이블의 검색 및 정렬 속도 향상 그룹화 작업의 속도 향상 인덱스의 단점 파일 크기가 늘어난다 데이터의 CUD 성능 감소 인덱스 생성 후 데이터 변형이 계속 이루어지면, ..
[DB] SQL과 NoSQL 데이터 베이스란 간단하게 말하면 데이터의 모음을 의미한다. 우리는 데이터를 체계적으로 관리하고 싶을 때, 이러한 데이터베이스를 활용하게 된다. 데이터를 조직화하여서 관리하게 되면, 대량의 데이터도 효율적으로 관리할 수 있는 장점이 생긴다. 그렇다면 데이터베이스는 어떤 것들이 있으며, 어떤 형태들이 있을까? 대표적으로 관계형 데이터베이스와 비관계형 데이터베이스가 있을 것이다... 1. 관계형 데이터베이스 RDB 엑셀과 유사한 2차원의 테이블 형식으로 구성되며 속성과 값을 이용하여 데이터를 정의하고 저장, 관리하는 데이터베이스다. 관계형 데이터베이스는 테이블의 구조와 데이터 타입 등을 사전에 정의하고 그에 맞는 형태를 가진 데이터만 삽입할 수 있다. 관계형 데이터베이스 관리 시스템 (RDBMS) 종류 MyS..
[DB] 트랜잭션의 격리수준 1. 트랜잭션 격리 수준 동시에 DB에 접근할 때 그 접근을 어떻게 제어할지에 대한 설정 레벨(고립도)이 높아질수록 고립도가 올라가서 더 확실한 처리가 가능해지지만 동시에 수행될 수 있는 트랜잭션을 순서대로 처리하게 되어 속도가 느려지게 된다. 2. 트랜잭션의 격리 수준 단계 (1) Read Uncommitted 트랜잭션에서 처리 중인 아직 커밋되지 않은 데이터를 다른 트랜잭션이 읽는 것을 허용한다. SELECT 문장이 수행되는 동안 해당 데이터에 Shared Lock이 걸리지 않는다. 발생할 수 있는 문제점 Dirty Read Non-Repeatable Read Phantom Read (2) Read Committed 트랜잭션이 커밋되어 확정된 데이터만 다른 트랜잭션이 읽도록 허용한다. 발생할 수 있는..
[BOJ] 1620. 나는야 포켓몬 마스터 이다솜 Python, Java https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 1. 해결방법 이 문제에서 포인트는 시간복잡도이다. 리스트에 대한 시간복잡도와 파이썬의 딕셔너리의 시간복잡도를 이해하는지에 대한 의도가 드러나있다. 리스트의 경우, 자주 쓰이는 append와 pop과 같은 경우에는 O(1)의 시간복잡도를 가지지만, list.index()와 리스트 탐색의 경우에는 O(N)의 시간복잡도를 가진다. 해당 문제는 isdigit() 메서드까지 ..

티스토리툴바