아네스의 공부일지

코딩테스트 연습 - [1차] 추석 트래픽입력: [ "2016-09-15 20:59:57.421 0.351s", "2016-09-15 20:59:58.233 1.181s", "2016-09-15 20:59:58.299 0.8s", "2016-09-15 20:59:58.688 1.041s", "2016-09-15 20:59:59.591 1.412s", "2016-09-15 21:00:00.464 1.466s", "2016-09-15 21:00:00.741 1.581s", "2016-09-1programmers.co.kr아이디어일단 string에 대한 처리를 해주어야한다. 로그 기록이 하루치기에 input으로 주어지는 9월 15일이라는 정보는 중요하지 않다. 시간이 주어지고, 처리시간이 주어지는데  최소 단위..

코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 아이디어 처음엔 삽질을 좀 했다. string의 character를 하나씩 확인하면서 양쪽 투포인터를 써서 팰린드롬인지 확인해 나갈건데 1. "abbba" 와 같은 경우 2번 인덱스의 b 기준으로 양쪽으로 퍼지면 된다. 그래서 l과 r을 i로 설정하여 양쪽으로 보내면 되는 것인데, 다음과 같은 경우를 보자. l,r = i,i 로 설정하면 이런 반례가 생겨버린다. 2. "abccba"의 경우 l,r을 (i,i)..

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 아이디어 go_party = 사람 : [파티 1,2,3,4 ... ] 어느 사람이 어느 파티에 가는지 input 받으면서 저장해둡니다. 파티를 확인했는데 진실을 아는사람이 있다면 해당 파티에 온사람들은 진실을 알고있으므로 온사람들을 True로 해줘야 하는데, 온사람들이 가는 파티를 방문해가면서 (BFS) 온사람들이 가는 파티의 인원들도 True처리 해줍니다. 파티에 진실을 아는 사람이 없는 경우에만 정답을 출력해줍니다. 예를들어 이러한 경우에 1번 사람이 진실을 알고있으니..

10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 아이디어 백곰의 위치를 구하는거 보다 얼음 위치가 난잡하게 input으로 들어와서 일단 오름차순으로 정렬 한 후에 각 얼음을 가장 왼쪽으로 두고 백곰의 왼손 위치라고 생각하면 오른손은 왼손 위치+ K*2에 위치 할 수 있기 때문에 범위를 합한다고 생각하고 접근했다. 그래서 범위를 표시할 수 있는 왼쪽, 오른쪽 포인터만 생각하고 문제를 풀다가 해당 범위를 더하는 과정이 길었는지 시간초과가 났었다. 추가 아이디어 조건을 충족할 때마다 for문으로 얼음 무게 합을 구하지 말고 미리 합을 구해..

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 처음에 상, 좌, 우, 하 순으로 움직이게 하면 만족 할 줄 알았으나, 출처) https://coding-w00se.tistory.com/20 위와 같이 빨간 원에서 초록색을 먹어야하지만 파란 색을 먹는 사태가 벌어져서 거리만큼 bfs를 실행하고 먹을 수 있는 물고기들을 거리순, x,y순으로 정렬하여 선택해야한다. ''' https://www.acmicpc.net/problem/16236 N * N, 물고기 M마리, 한칸에 최대 한마리 처음 상어크기 2 아..

21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 처음에 max_count, max_like 를 저장해가면서 x,y변수만 저장해가면서 했는데, 안되더라... 왜안됐을까.. 그리고 2차원 배열 만들 때 X처럼 만들면 옅은복사 문제가 생기니 쓰지 말 것. board = [[0]*N]*N # X board = [[0 for _ in range(N)] for _ in range(N)] # O ''' 상어 초등학교 https://www.acmicpc.net/problem/21608 1.상하좌우 (인접) 2.좋아..

이전에 1로 만들기 1을 풀었던 터라, 그대로 가져와서 백트레킹만 구현해서 제출했다. C++ 풀이 #include using namespace std; int dp[1000001]; vector v; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N,cnt =0; cin >> N; dp[1] = 0; //1부터 시작해서 for(int i = 2; i

와 문제 엄청길다 ㅠㅠ KMP문제인데 이해하는데도 한참걸렸고, 사실 이해한건지 만건지 아직 잘 모르겠다. KMP를 사용하지 않으면 O(n*m)의 시간복잡도를 가지지만, 패턴을 미리 만들어두면 거의 O(N)의 속도로 패턴 매칭을 찾을 수 있다. 간략하게 말하면 makeTable에서 접두사와 접미사에 대한 Table을 미리 만들어 두고, 이를 활용하여 kmp를 진행한다. KMP에 대한 설명은 알고리즘 카테고리에서 다시한번 보도록 하자. C++ 풀이 #include using namespace std; string n,m; int result =0; vector result_vec; vector makeTable(string pattern){ int patternSize = pattern.size(); vec..

아이디어 post의 가장 오른쪽 원소를 inorder에서 찾아서 나누면서 분할 정복. C++풀이 #include using namespace std; int n; int inorder[100001]; int postorder[100001]; void solve(pair idx_in, pair idx_post) { int post_left = idx_post.first; int post_right = idx_post.second; int in_left = idx_in.first; int in_right = idx_in.second; cout

아이디어 플로이드 와샬 알고리즘 사용. 동빈나 센세의 글보고 이해하자. 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver.com C++풀이 #include using namespace std; int n, m; int board[101][101]; void floyd(){ //플로이드는 중간에 거쳐가는것이 핵심이다. for(int k = 1 ; k n >> m; memset(board,0x1f,sizeof(board)); for(int i = 0 ; i> s >> e >> w; if(board[s][e] > w)..