조용하지않는개발Blog

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 첫번째부터 IOI가 나오는지 비교하면서 있다면 IO만큼 2칸씩 이동한다. 그리고나서 다시 IOI가 나오는지 비교하면서 그때 n의 개수와 IOI 나온 개수가 일치하면 결과값으로 1개씩 추가하고 IOI나왔던 개수를 1개 빼주는 형식으로 진행한다. IOI가 아니면 다시 초기화 해주는 느낌으로 문제를 ..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 딕션너리를 이용하여 찾는 문제이다. 리스트를 이용하여 저장하고 찾게 된다면 2중 for문을 통해 찾아야 하기에 많은 시간이 소모 된다.시간 초과가 나올 가능성이 높음. 하지만 딕션너리를 사용하면 O(n)이기 때문에 빠르게 문제를 풀 수 있다. import sys input= sys.stdin.readline n,m= map(int,..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 전체적으로 읽고 예제 입력, 출력을 보고 이해하고 풀 수 있었던 문제이다. 단순하게 푼다면 정렬을 하면서 풀수있겠지만, 그렇게 푼다면 정렬할때마다 시간이 소요되기에 시간초과가 나올것이다. 그렇기에 값을 넣거나 뺄때 바로 정렬이 되는 heap을 사용하면 해결할수 있는 문제이다. 여기서 약간 문제를 꼬았는데 바로 절대값을 넣어서 조금 어..

그래프의 표현 그래프 표현하기 인접리스트 표현 (Adjacency list representation) 인접행렬 표현 (Adjacenry-matrix representation) 인접리스트 표현 (Adjacency list representation) 점점 하나당 리스트 하나인 크기가 v인 배열 정점 하나에 인접한 모든 정점을 리스트에 저장 비방향성 그래프에서는 방향성 그래프로 변환해서 저장, 단점으로는 방향성 그래프에 비해 2배의 공간이 필요 인접행렬 표현 (Adjacenry-matrix representation) 크기가 v*x인 행렬 두 정점 i와 j를 잇는 간선이 있다면 행렬의 (i,j)는 1, 아니면 0 v의 제곱개의 공간 필요 무방향성은 양방향으로 간선이 존재하므로 하위 삼각행렬이 상위 삼각 ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 처음에 문제를 보고 단순하게 큰 값부터 계산하고 주변을 0으로 두면서 풀면 될까? 라는 생각을 가졌지만 여러 계산을 해보니 그렇게 풀면 발생하는 오류들이 많이 있어서 이것은 dp로 풀어야하는 문제라는 것을 파악하였다. 두개의 스티커를 1부터 차례대로 계산을 하면서 증가시키면 되는 문제였다. 1 2 3 4 5 1 50 30+10=40 max(30,100..

1. 그래프 기초 그래프 G 그래프G는 (v,e)의 쌍이다. 이때 v는 정점(vertex)의 집합(set)이고 e는 간선(edge)의 집합이다. 정점은 독립된 개체(stand-alone object)로 동그라미로 표현한다. 간선은 두 정점을 잇는 개체로 선이나 화살표가 있는 선으로 표현한다. 방향성 그래프(Directed graph) 방향성이 있는 간선을 가지고 있는 그래프 간선이 방향을 가지기 때문에 화살표가 있는 선(arrows)을 사용한다. 각 간선은 한 정점을 떠나서 한 정점으로 들어간다. 일반적으로, 각 정점은 숫자나 이름으로 구분한다. 각 간선은 간선이 떠나고 도착하는 정점의 쌍을 순서대로 적은 것으로 구분한다. 방향성 그래프에서 두 개의 정점에 대해 최대 2개의 간선이 존재한다. 무방향성 그..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 이 문제는 정해진 숫자를 차례대로 출력 될수있게 하면 되는 문제이다. 백트래킹과 dfs를 이용해서 풀면 쉽게 풀린다. 또한 그냥 itertools의 permutations을 통해 풀면 간단하게 풀수있다. # dfs와 백트래킹 import sys input= sys.stdin.readline def dfs(x,y): if m==y: print(*x) el..

학습목표 1. open Addressing 방법에 대해 이해하고 장단점을 파악 할 수 있습니다. 2. Linear probing, Quadratic Probing, Double hashing 방법에 대해 이해할 수 있습니다. 1. Open-Addressing 개요 오픈 어드레싱(open Addressing) 오픈 어드레싱이란? Collision을 피하기 위한 다른 방법으로 key를 hash table에 직접 저장 오픈 어드래싱의 장점 포인터를 사용하지 않아도 되므로 구현이 간편하다. 포인터를 사용하지 않으므로 추가 메모리 공간 사용이 가능하다. 공간의 충돌 문제가 줄어들며 자료 검색이 미세하게 빨라진다. 선형 프로빙(Linear probing) 특정 조건이 주어졌을때 선형 프로빙으로 key값을 테이블에 ..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 처음에 문제를 잘못 이해해서 고생했지만 위 4개를 이어붙인 모습으로 최대가 되는 값을 찾는 문제였다. 백트래킹을 활용하면 문제를 풀 수 있지만. 문제가 되는 부분인 ㅗ,ㅜ,ㅓ,ㅏ 이 모양을 어떻게 만드느냐가 중요한 사항이다. 처음에는 4가지를 코드로 구현해서 결과를 출력해보았다. import sys dx = [0,0,1,-1] dy = [1,-1,0,0] inp..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 보고 간단하게 푸는 방법으로는 조합을 출력되게하면 끝이 나겠구나? 생각이 들었다. 파이썬에는 itertools의 combinations 가 존재하기에 이것을 이용하면 엄청 쉽게 풀 수 있다. import sys from itertools import combinations input= sys.stdin.readline n,m = map(int,input..