삽질도사

https://www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 처음 접근법: 완탐으로 4방향에 대해서 한방향씩 끝까지 탐색한다고 생각하고 각각의 타일에서 한번 더 2방향(내가 온 방향 및 그 반대 제외)을 끝까지 탐색해서 물이 세는지 확인, 4방향 각각의 최대값을 구하고 그 중에서 최소값이 시작타일의 높이보다 크다면 뺀 값이 물을 채울 수 있다는 아이디어 (틀림) -> 계속 물이 세는지 확인한다지만 예외적인 부분(탐색하지 않은 곳에서 ..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 후기 : 골드 4 수준은 절대 아닙니다~ 제 생각엔 골드 1정도. 문제 자체도 카메라가 많아서 솔직히 좀 지저분한 문제라는 생각이 들고 코드량도 많아지기 때문. 더군다나 중복체크를 허용하는 백트랙킹을 3번씩하는 것은 구현하거나 생각해내기가 상당히 어려웠다는 점에서 난이도도 있고 배울 점도 있었지만 딱~히 교육적인 문제라는 생각은 안드는 문제. (삼성에서 이런 비효울적인 문제를 테스트로 ..

https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 1년 전에 한번에 풀었던 문제인데, 이제보니까 죽어도 모르겠어서 과거의 내 답지를 한번 보고 다시 풀었는 데 그래도 몇 번 틀렸습니다 ;ㅁ; (그래도 본인 골드1인데..) 반례가 많은 문제여서 심지어 문제를 읽어보면 문제에 반례가 적혀있습니다. 하여튼 핵심은 재귀함수를 사용해서 '(' 또는 '[' 에서 내부에 괄호가 있는 지 확인하는게 핵심입니다. 그리고 괄호가 올바른 지의 유무를 따지는 것은 ..

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 저는 처음에 단순히 인덱스로 접근해서 마지막 ' ( '로 돌아갔더니 메모리초과가 나서 stack으로 풀었습니다. 일단 stack구조를 활용하는 문제입니다. ' ( ' 모양은 모두 push하고, 갈색으로 빗금친 괄호의 뜻은 ' ) ' 모양이 왔을 때에 이전의 ' ( '를 pop한다는 의미입니다. 레이저가 지나가는 빨간선,녹색선의 왼쪽을 기준으로 막대의 갯수를 세는 것이 핵심입니다. 레이저가 지나가면 위의 사진..

두가지 방법이 있는데요, 첫 번째는 구현에 가까운 풀이이구요,(눈물의 풀이입니다.) 두 번째는 좀 더 수학적(?),구조적으로 푼 방법입니다. 알면 쉽고 모르면 생각하기 좀 까다로운 문제입니다. 가능하면 두 번째 방법을 추천드립니다. 첫 번째 func() 풀이는 기준점의 기둥보다 크거나 같은 기둥을 찾아서 그 사이에 모이는 빗물을 더해주는 방법입니다. 기준점보다 크거나 같은 기둥이 없다면 그 중에서 그나마 가장 큰 기둥을 찾아서, 찾은 기둥까지 모인 빗물수 - (기준기둥크기 - 그나마 큰 기둥크기) * (사이에 있는 기둥 수) 를 반환합니다. (일단은 뒤에 큰 기둥이 있다는 가정하에 무식하게 더하다가 그게 아니니까, 그마나 큰 기둥을 기준으로 그보다 높이 쌓인 빗방울을 없애주는 겁니다.) 두 번째 func..

포문 돌릴 때 최대y는 명령갯수이고, 최대x는 스케줄마지막 날짜(제일큰 마지막 수)로 돌렸습니다. start 기준으로 정렬해서 리스트에 넣어주고 순서대로 배열에 집어넣었고 이후에 연산 엄청나게 까다로웠습니다. 그냥보고하면 이해할 수는 있는데, 짜잘한 실수가 많이 나올 수 있는 로직이었습니다. 전체적으로 포문을 돌리면서 채워진 곳을 만나면 y의 최대값을 갱신하고, 그게 아닌경우는 무시. 모든 y에서 0이라면, if문을 만나서 값을 초기화(비어있는 스케줄) 마지막에 비어있는 칸이 아닐 경우에만 dx++를 해주면 되는 간단한 방법이지만, x값은 계속 증가하나, 비어있는 칸부터 비어있는 칸 까지의 값만을 체크해주어야 하는데 이부분이 생각하기 힘들었습니다. 개인적으로 문제 난이도가 실버1인데 체감은 골3~4정도 ..

스택을 사용하면 편하게 풀 수 있는 문제였습니다. 단번에 풀기는 어렵지만, 처음에 코드를 계획할 때 잘 구상하였다면, 큰 오류없이 해결할 수 있습니다. 태그자체도 결과에 나와야한다는 조건을 뒤늦게 보는 바람에 계획이 틀어졌지만, 원래의 코드와 큰 차이가 없어서 추가적으로 코드를 작성하는 것으로써 다행히 쉽게 수정할 수 있었습니다. 또한 태그의 앞뒤로는 공백이 없이 결과값이 나와야 하기에 그 부분이 조금 애를 먹었지만, 금방 해결봤습니다. 일반적인 경우를 함수로 놓고, 태그를 만났을 때에 그 함수를 사용하는 것이 좀 더 깔끔한 코드가 될 것 같습니다만, 저는 뒤늦게 깨달아서 빨리 풀려고 이대로 제출했습니다. import java.io.BufferedReader; import java.io.IOExcepti..

배열 맵을 이용한 알고리즘은 비슷한 로직으로 움직이는 경우가 많기 때문에 피아노치듯이 툭툭 치게됩니다. 이 문제도 그런 유형의 문제인데 그중에서도 기본이 되는 문제라고 생각합니다. 이러한 유형의 문제를 바탕으로 더 다양한 문제들에 활용됩니다. 문제를 많이 풀면 익숙해져서 많이 생각하지 않아도 평소에 코드를 치듯이 치게됩니다. 하지만 처음 문제유형을 접할 때에는 생각이 복잡하고 다양한 접근을 하기때문에 어렵게 느껴집니다. 따라서 이러한 기본유형의 문제들은 적당히 익혀두었다가 난이도를 점차 올리면서 익숙해지고, 생각이 짧아지면서, 오히려 좀더 복잡하고 더 활용도가 필요한 문제를 풀 때에 좀더 가볍게 접근 할 수가 있습니다. 문제에서 배열을 돌리기위해서 배열을 양파껍데기라고 생각하고, 처음에 가장 끝에 쌓여있..