무지성 코딩뉴비

학교 에타에서 이런게 있다는걸 알게 되어 지원하게 되었다. 먼저 지원서에는 간단한 지원동기와 자신의 인적사항을 적으면 되었는데 대충 적어서 냈다. 지원서 접수가 완료 된 후 6일 동안 5문제를 자유롭게 풀어내면 되는 입과 테스트가 있었는데 앨리스 코딩이란 사이트에서 할 수 있도록 링크를 메일로 보내준다. 지금 입과 테스트 문제가 기억 나지는 않고 작성했었던 코드는 저장 해 놓아서 코드 작성한 것을 보았는데 1번은 완전탐색 2번은 깊이 우선 탐색을 이용한 백트래킹 3번은 너비 우선 탐색 4번은 너비 우선 탐색 + 깊이 우선 탐색 + 백트래킹 5번은 dp 문제 였던거 같다 6일중에 첫째날에 1번을 둘째날에 2 3 4번 셋째날에 5번을 풀었고 다섯 문제를 모두 맞아 500점 만점으로 입과 테스트에 붙어서 온라..

https://www.acmicpc.net/problem/20541 20541번: 앨범정리 지혜는 컴퓨터에 있는 사진들을 정리하기 위해 앨범정리 프로그램을 만들었다. 지혜가 만든 앨범정리 프로그램은 기본적으로 "album" 앨범이 존재하며 "album" 앨범은 절대로 삭제할 수 없다. www.acmicpc.net 코드 //20541번 #include #include #include #include #include #include using namespace std; class Album { private: Album* parentAlbum; string albumName; int photoCnt; int albumCnt; set photoSet; //사진이름 map albumMap; //자식 앨범이름 ,..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제해석 문제를 보면 dp 문제임을 어렵지 않게 알 수있는데 나는 탑다운 형식으로 dp를 작성하였다. 예시와 같은 문제일때 1일 부터 확인하는게 아닌 7일부터 확인해야한다. 1일을 확인해보자 1일 상담을 하면 2일 3일은 상담을 할 수 없다. 즉 1일 상담의 금액 P[0]과 4일부터 상담했을때 최대 이익 =dp[3] 5일부터 상담했을때 최대 이익 =dp[4] 6일부터 상담했을때 최대 이익 =dp[5] 7일부터 상담했을때 최대 이익 =dp[6] 의 합중 가장 큰것이 답이 된다. 즉 dp[0]=max(p[0]+dp[4],p[0]+dp[5..

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 문제해석 예전에 이 문제를 처음 봤을때 생각 났었던 아이디어는 백트래킹이 떠오르긴했는데 막상 직접 구현을 하기에 빡세게 느껴졌어서 언젠가 풀어야지하고 미루다가 얼마 전에 풀게 되었다. 실제로 백트래킹을 이용한 깡구현 문제인데 아이디어는 이렇다. 먼저 4x4 공간이기 때문에 상어의 현재 위치와 방향에 따라서 물고기를 최소 0개에서 최대 3개를 먹게 되는경우가 생긴다는걸 알 수있다...

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제해석 먼저 전역 변수로 dice를 선언해주었다 순서는 어떻게 하든 상관없지만 나는 앞 위 뒤 바닥 왼 오 순서대로 작성하였다. 현재 주사위의 위치와 방향이 주어지면 방향에 맞게 그 다음의 위치로 주사위를 돌려주고(turn) 다음 그 위치의 지도에 0인가 아닌가에 따라 문제에 설명 되어진 대로 구현한 move함수를 구현하였다. 참..

https://www.acmicpc.net/problem/1069 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net 문제해석 이 문제는 기하문제 라고 생각하고 풀었다. 먼저 걸을때와 점프 하는 것이 있는데 점프 없이 걸어갈때 만을 먼저 살펴보자 그렇다면 1초당 1만큼 움직이므로 집까지의 걸리는 시간은 거리 d=sqrt(X*X+Y*Y)이다. 그런데 시작 점에서 점프를 섞어서 집으로 가는 방법 역시 존재 할 수있다. 처음에 빨간색 처럼 점프거리가 집 까지의 거리 보다 짧아 안 닿는 경우와 초록색 처럼 ..

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제해석 전에 풀어봤던 3151번 합이 0 문제와 비슷한 문제 같다는 느낌을 받았다. https://www.acmicpc.net/problem/3151 다만 3151번은 3개 합이 0이 되는 쌍의 갯수를 찾는 것 이고 이 문제는 4개 합이 0이 되는 쌍의 갯수를 찾는 것 이다. 그냥 모든 경우를 확인해버리면 배열의 크기가 최대 4000개 이므로 4000^4 이므로 이렇게 풀면 시..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제해석 문제에 나온 설명처럼 빗금이 없는 부분의 영역을 구하여 오름 차 순으로 출력하면되는데 빗금이 있는곳을 1 없는곳을 0으로 세팅한 후 dfs또는 bfs를 사용하여 각 영역의 넓이를 오름차순으로 출력하여 풀었다. 문제에선 좌표로 x,y좌표로 나타나있는데 배열로 풀 경우 행 열로 표현이 편하기 때문에 뒤집어 풀었다. 무슨 말이냐면 윗 그림과 아래 그림은 동치인데 편의상 아래..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제해석 전형적인 dp문제인데 4 1 5 6 7 입력이 위 처럼 들어왔다고 가정해보자 카드 4장을 구매하는 경우는 1+1+1+1 1+1+5 1+6 7 5+5 이렇게 5가지가 존재하고 이 중 5+5가 가장 큰 값이 되므로 이것이 답이된다. 위의 5가지 경우를 식으로 나타내면 dp[4]=max({dp[3]+p[1],dp[2]+p[2],dp[1]+p[3],dp[0]+p[4]})가 되고 점화식을 일반화 하면 j..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제해석 이 문제는 예전에 풀어봤던 2696번 중앙값 구하기 https://www.acmicpc.net/problem/2696 이것과 같은 문제이다. 아이디어는 이렇다. 우선순위큐 두개를 선언하는데 하나는 오름차순 하나는 내림차순으로 한다. 항상 왼쪽 우선순위 큐 내의 모든숫자의 숫자는 중앙 값보다 작은 값이 오른쪽 우선순위 큐 내의 모든숫자는 중앙 값보다 크게 조절을 하자 입력을..