삽질도사

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한다는 의미입니다. 레이저가 지나가는 빨간선,녹색선의 왼쪽을 기준으로 막대의 갯수를 세는 것이 핵심입니다. 레이저가 지나가면 위의 사진..

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

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

전형적인 그리디유형의 문제입니다. 모르면 어지간해서는 절대 못풀고, 알면 쉽게 풀 수 있는 문제입니다. 난이도 측정이 심하게 잘못되어서 원래 실버2? 쯤에 있었는데, 이 문제는 이후에 골5쯤에서 나오는 센서와 동일한 문제입니다. 바로 앞에 있는 숫자와의 차를 모두 배열에 집어넣습니다. 이는 새로운 배열에 할당한다고 생각하시면 됩니다. (코드에서는 배열을 재활용했음) 배열을 모든 인덱스에 대해서 2개짜리 묶음으로 묶었다고 생각하시면 편합니다. 그리고 그 묶음에서 n-k만큼 뽑으면 됩니다 ( 묶음끼리 겹치게 되면 한묶음이 된다고 생각! ) 그림그려보면 이해가능하지만, 일반인의 머리로는 백지상태에서 절대로 쉽게 풀 수 있는 문제가 아닙니다. 이러한 유형은 만났다면, 반드시 풀이를 기억해서 또 만나면 똑같은 방..