본문 바로가기

전체 글

 (351)
[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() 메서드까지 ..
[BOJ] 2206. 벽 부수고 이동하기 Python https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. 해결방법 일단 체감상 어떻게 해결해야할지 감은 오지만 조건을 맞추는데 어려워서 굉장히 많은 시간을 함께 보낸 문제이다. 하지만 좋은 문제인 것 같다. 전형적인 BFS 문제이며 , 벽을 딱 한번 부술 수 있는 특징이 있는 문제이다. 방문 체크를 2차원으로 해버리면, 이미 벽을 부순 노드가 빈 공간을 방문하다가 이동할 수 없는 상황일 때, 다녀면 위치가 다 방문 체크가 ..
[DB] 트랜잭션 1.트랜잭션 데이터베이스가 데이터를 읽거나 쓰는 최소 단위 데이터베이스의 상태를 변화시키기 위해 수행하는 작업 단위 데이터베이스에 접근하는 방법은 장고의 ORM을 이용한 쿼리가 있는데, 이 쿼리들이 하나로 묶인 단위 2. 트랜잭션 특징 (1) 원자성(Atomicity) 트랜잭션 연산은 데이터베이스에 모두 반영되든지 아니면 전혀 반영되지 않아야 함 트랜잭션 내의 모든 명령은 반드시 완벽히 수행되어야 하며, 어느 하나라도 오류가 발생하면 트랜잭션 전부가 취소되어야 함 (2) 일관성(Consistency) 트랜잭션이 실행을 성공적으로 완료시 언제나 일관성 있는 데이터베이스 상태로 변환됨 시스템이 가지고 있는 고정 요소는 트랜잭션 수행 전과 트랜잭션 수행 완료 후의 상태가 같아야 함 (3) 독립성, 격리성(Is..
[Java] SAX Parser 1. SAX Parser Simple API for XML Parser의 약어로, 자바 API에서 제공한다. DOM Parser와는 다르게 SAX Parser는 문서를 딱 한번만 읽는다. 다시말해, 한 번 읽는데 문서를 순회하면서 event가 발생하면 순차적으로 파싱을 하게 된다. 즉, XML 문서를 읽어들여서 어떤 태그를 만나면 그에 따라 이벤트를 생성한다. 하지만 딱 한번 순회하므로 다양한 형태로 처리할 수 없지만, 가볍고 파서가 간단하다는 장점이 있다. 2. SAX 구조 모델 : 이벤트 기반 인터페이스 XML 문서를 읽을 때 SAX 파서는 어떻게 이벤트를 발생하게 될까? 위 예시 처럼 특정 위치에서 이벤트를 발생시키는 메서드들이 존재한다. (1) startElement() : 태그를 처음 만나면, ..
[BOJ] 2146. 다리만들기 Python https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 해결방법 BFS 문제이다.. 쉬울줄 알았는데 어려웠다. 2개의 큐를 사용해야 하고, 시간 복잡도를 고려해야 한다. 시간나면 다시 한번 풀어봐야겠다. 1. 각 섬을 구분짓기 위해 bfs1을 돌아서 각 섬들이 고유의 번호를 갖기 위해 값을 하나씩 증가시켜 maps을 저장했다. 2. 2중 for문으로 특정 섬부터 시작해서 두 번째 bfs2를 돈다. 3. 유효성 검사를 하고 자신의 섬이 아닌 다른 섬을 ..
[DB] 데이터 베이스 정규화 1. 정규화(Normalization) 테이블 간에 중복된 데이터를 허용하지 않는다는 것이다. 중복된 데이터를 허용하지 않음으로써 무결성을 유지할 수 있으며, DB 저장용량 역시 줄일 수 있다. 이러한 정규화는 테이블을 분해하는 단계가 있는데, 테이블을 어떻게 분해되는지에 따라 정규화 단계가 달라진다. 디비의 정규화가 진행되면 기존의 릴레이션이 분해가 된다. 하지만 분해된 릴레이션은 무손실 조인을 무조건적으로 보장해야한다. 여기서 무손실 조인은 분해된 릴레이션은 다시 결합하더라도 분해 전 결과랑 같아야 한다. (1) 제 1 정규화 테이블의 컬럼이 원자값(Atomic Vlue, 하나의 값)을 갖도록 테이블을 분리하는 것. 취미 테이블에서 추신수와 박세리는 여러 개의 취미를 가지고 있기 때문에 제 1정규형을..
[DB] 데이터 베이스(Database)의 기본 1. 데이터 베이스 데이터 혹은 정보를 체계적으로 관리하기 위해 저장되어있는 데이터의 집합이다. 2. 데이터 베이스의 특징 독립성 물리적 독립성 : 데이터베이스 사이즈를 늘리거나 성능 향상을 위해 데이터 파일을 늘리거나 새롭게 추가하더라도 관련된 응용 프로그램을 수정할 필요가 없다. 논리적 독립성 : 데이터베이스는 논리적인 구조로 다양한 응용 프로그램의 논리적 요구를 만족시켜줄 수 있다. 무결성 여러 경로를 통해 잘못된 데이터가 발생하는 경우의 수를 방지하는 기능으로 데이터의 유효성 검사를 통해 데이터의 무결성을 구현하게 된다 보안성 인가된 사용자들만 데이터베이스나 데이터베이스 내의 자원에 접근할 수 있도록 계정 관리 또는 접근 권한을 설정함으로써 모든 데이터에 보안을 구현할 수 있다. 일관성 연관된 정..
[BOJ] 13549. 숨바꼭질 3 Python https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 해결방법 DFS인줄 알았으나, 재귀에러에 두들겨 맞고 BFS로 풀었다. 왜 bfs인지는 문제를 풀면서 느낌;; 1. 현재 인덱스 위치랑 time을 q에 append 한다. 2. x * 2, x - 1, x + 1의 경우에는 가중치가 0 그리고 1로 다르므로 bfs를 이용하여 3가지 모두 탐색을 한다. 3. 유효성 검사와 방문체크도 하고, 새로운 인덱스 위치와..

티스토리툴바