아네스의 공부일지

코딩테스트 연습 - [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.좋아..

아이디어 presum을 미리 구해두고 (나는 dp라고 명명) 빨간색 구역의 합은 dp[r2][c2]에서 주황색 두부분을 빼고, 초록색 영역을 다시 더해줌으로써 구할 수 있다. C++풀이 #include using namespace std; typedef long long int ll; int R,C,Q; int board[1000][1000]; int dp[1001][1001]; int r1,c1,r2,c2; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> R >> C >> Q; for(int i = 0 ; i> tmp; board[..

아이디어 맨처음엔 visited를 bool타입으로만 풀려고해서 한번 실패하고, 백트래킹 해두고 visited를 다른 숫자로 바꾸는 방식으로 해서 차이를 두려고 했더니 시간초과가 나서 아예 매 bfs마다 다른숫자를 사용하는 것으로 고쳤다. 기존 문제점 위에꺼 처럼 visited true로만 처리하게 되면 아래 그림에서 2,3,4일때 visited true인걸 계속 만나서 count가 증가하기 때문에 구분해줬다. C++ 풀이 #include using namespace std; int N,M; int board[1000][1000]; int visited[1000][1000]; int dx[4] = {-1, 0 , 1 , 0}; // U, R, D , L; int dy[4] = {0, 1, 0, -1 }; ..

아이디어 일단 입력을 받은 후에 , 오름차순 정렬을 해둔다. 정렬 후 dfs(0)으로 배열의 첫부분부터 dfs를 시작해서 dfs들어갈 때마다 vector res에 push_back을 하며 진행한다. vector에 L개 만큼의 charater가 들어오면 자음 모음의 수를 체크하고 조건에 맞다면 출력한다. C++풀이 #include using namespace std; typedef long long int ll; int L,C; vector v; vector res; bool check() { int moum = 0; for(int i = 0 ; i< L ; i++) { if(res[i] == 'a' || res[i] == 'e' || res[i] == 'i' || res[i] == 'o' || res[i..

아이디어 solve함수에서 1인 곳을 찾고 bfs탐색하여 visited=true로 만들어주며 탐색한다. C++풀이 #include using namespace std; //input변수 int N; int board[25][25]; bool visited[25][25]; int cnt = 0; // 단지 수 카운트 int dx[4] = {-1,0,1,0}; //시계방향 탐색 int dy[4] = {0,1,0,-1}; queue q; // {x,y}값 넣을 큐 vector res; // 각 단지마다 개수 저장 vector void bfs(void) { int cnt = 0; while(!q.empty()){ int x = q.front().first; int y = q.front().second; cnt+..