백준 삼성기출 풀고 혼자 끄적인 것

09/15 구슬탈출 2의 교훈

 

백준 정답률 24.7% 3537 / 24362

구현 난이도 꽤 았는 문제?? 로 누가 평가

 

일단, 끝까지 풀면 된다.는걸 알게되었고

최대한 반복할 수 있는 걸 염두해두고 코딩하는 것이 좋음. (그거 고민하느라 손도 못대는 건 가장 끔찍한 일이니 잘 고민하고)

끝까지 잡고 디버깅하면 풀리긴 풀린다. 더 꼼꼼하게, 테스트케이스 자기가 만들 수 있게 열심히하자

 

09/18 2048(easy) 의 교훈

 

3462 / 23508 23%

 

나눌 수 있는 만큼은 나누자 (k를 통해 나누던지 left right 최대한 공통적인 부분은 비슷한데 두어 같이 feedback 할 수 있게

 

초기화를 제때 잘해야한다.

 

09/18 뱀 교훈

 

65분소모 (노트알고리즘체크 8분)

logic별로 함수 만드는건 귀찮지만 매우 유효했다.

 

logic별로 나누니 어떤걸 어디에 배치해야할지만 고민하면 되어서 디버깅이 매우 쉬웠다. 이런 습관을 가지자

 

09/19 시험감독 교훈

 

45분소모 (노트알고리즘체크 4분)

long long...

정말 정답이라고 생각하면 자료형이 다를 수 있다는 것을 생각 선택지에 넣자.

 

09/19 주사위 굴리기 교훈

 

100분소모 (노트알고리즘체크 10분)

x, y좌표를 입력단부터 헷갈리게 할 수 있다..

row 는 행 (y의 개념. 위에서 떨어진 양)

col 는 열 (x의 개념. 왼쪽에서 떨어진 양)

명심

 

문제 잘 읽는 것 중요.

 

단위 나눠서 move, check 등 이렇게 나눠서 푸니까 굉장히 도움

 

09/19 테트리미노 교훈

 

82분 소모 (노트알고리즘체크 7분)

문제 제대로 읽지 못해 조건 못찾고 컴파일

너무 복잡한 코드 탓에 잘못한게 많음

 

09/20 퇴사 교훈

 

56분 소모 (노트알고리즘 5분)

코너케이스 잘 찾자.

유일한 기출중 dp였으나 완전탐색으로 처리 가능했음.

 

09/20 연구소 교훈

 

43분 소모 (노트알고리즘 3분)

무난하게 풀림. 순열 같은 것 잘 찾는 것 중요

next_permutation 여기서 쓰진 않았지만 사용법 알기

bitset도

 

09/20 로봇청소기

 

59분 소모 (노트알고리즘 3분)

무난하게 풀림.

논리정연하게 풀자. 이대로 되면 될 수 밖에 없는 것으로

함수화를 통해 그 논리를 생각하기 쉽게 하자.

 

09/20 연산자 끼워넣기

 

30분 소모 (노트알고리즘 8분)

순열로 쓰면 더 쉬웠을 수도

dfs로 순열 만들기를 했따. 계속 쓸 수 있게 익히던가 next_permutation 알기

 

09/21 스타트와 링크

 

52분 소모 (노트알고리즘 6분)

이것도 순열 잘 써야할듯

순열 10개 줄세워야하는 경우 있었음. 크기 순서 무시하면 메모리초과.

크기 순서 추가하는 방법은 dfs 진행될 때 인덱스 인자로 넣기 (1020 조합 말하는 것)

 

void find_cases(int start_idx, vector<int> temp) {

if (temp.size() == N / 2) {

cases.push_back(temp);

return;

}

for (int i = start_idx+1; i < N; ++i) {

if (visited[i] == false) {

visited[i] = true;

temp.push_back(i);

find_cases(i, temp);

temp.pop_back();

visited[i] = false;

}

}

}

 

09/22 경사로

 

58분 소모(노트알고리즘 5분)

노트알고리즘을 너무 간단히 했다.

여기도 상승과 하강 두가지 경우 있는데 하나의 for문으로 합치는 걸 해보면 좋겠다.

좀더 검증 잘 해서 했으면 더 빨리 끝났을 듯. 디버깅만 30분

 

09/22 톱니바퀴

 

39분 소모(노트알고리즘 5분)

무난하게 했다. 경우의수를 너무 나누긴 했지만 적당한 정도였다. 남들어떻게했는지 한번 볼 필요는

 

09/23 감시

 

65분소모(노트알고리즘 8분)

알고리즘이 맞다면 정확한 코딩으로 구현가능

머리속으로 대충 때려맞추지 말고 제대로 검증하고 구현하자.

 

09/23~09/24 사다리조작

 

10시간은 쓴듯

시간줄이기도 신경써야하고 (가지치기방식으로)

애초에 심각한 for문 문제 있었다. -> y먼저 체크하는 거였는데 x로갈때 y가 0부터 다시 경우의수를 셈. 여기서 가지치기위해 y=sy같은 걸 해서 0~sy-1까지 무시해서 답이 틀림

다시금 느끼는건 알고리즘이 맞았으면 코드가 잘못되었다. 디버깅 잘 할 수 있는걸 염두해서 짜야한다. 코드 짜는데 20분 더 걸려도 디버깅 잘 할수 있게 짜놔야

3시간안에 디버깅이 가능하다.

 

09/25 회전하는큐 (not 기출)

 

쉬운문제인데도 1시간 20분정도 사용

index 대충 머리속으로 이렇게하면되겠지? -> 무조건 틀린다

항상 손으로 정리하고 검증하는 습관. 제발 가지자. 이게 아니면 무조건 통과 못한다.

 

09/25 연산자 끼워넣기(2) (not 기출)

 

40분소모

max_min 이 10억 -10억 인데 999999999 라고 함(9억)

 

09/25 외판원 순회2 (not 기출)

 

20분소모

 

09/25 드래곤커브

 

노트알고 20분 총 75분

문제굉장히 어려울 것 같았는데 일단 답은 무조건 구할 수 있다는 생각으로 규칙을 찾았다.

규칙대로 그대로 정확하게 구현하려 하니까 한번에 구현이 된 듯.

중간중간 디버그 용이하게 print 문과 print용 함수도 잘 구현함.

 

09/25 치킨배달

 

노트알고 8분 총 24분

조합 뽑고 그대로 시뮬레이션. 그렇게 어렵지 않은데 드래곤커브보다 정답률을 낮았다.

특이한 것은 먼저 조합알고리즘 정리후 구현 -> 다음 문제 정답을 위한 구현 방법으로 접근

나쁘지 않았다.

 

09/26 큐빙

 

3시간 23분

무식한 구현문제. 중간 인덱스 틀려서 계속 문제 생겼음.

디버깅하기도 엄두가 안나서. 큐브 좌표계 디버깅위주로 작성하는 것도 괜찮아 보임.

좌표를 종이에 다 써넣고 생각하는 게 특이점.

눈으로 디버깅 잘하자.

 

09/26 나무재테크

 

57분

생각한대로 구현하면 되는 무난한 문제였음.

봄여름가을겨울 있는데 봄,여름 사이에 디펜던시가 없고 가을 겨울끼리 마찬가지여서 함께 묶어 구현했다는 것이 특이점.

 

09/26 아기상어

 

2시간 14분

dfs로 했다가 시간초과, bfs로했다가 메모리초과. 조건 하나 잘못봐서 while 종료조건을 생각해놓고도 그대로 동작하지 못해 시간을 많이 날림.

생각한 건 종이에 정리하거나 제대로 구현되었는지 확인하는 습관.

일단 이건 메모리 다른사람보다 훨씬 많이 써서 한 경우라 다른사람 코드 확인이 필요함.

 

10/18 아기상어 2번째 1시간

다시 푸니까 너무 쉽다. 위의 시도에서는 메모리, 시간 많이 썼는데 두번째에선 0ms 에 메모리 최소 사용했다.

실력이 늘긴 는듯

 

 

09/27 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (not기출)

 

20분

dfs 중간 최적화가 필요했음.

순열 이나 조합 넣을 때 1 ,2 3 이라면 탐색 vector에 3,2,1 로도 넣어주어야 모든 경우를 찾을 수 있다.

 

09/27 인구이동

 

22분

하라는 대로 하면 무난히 구현되는 문제.

 

09/27 미세먼지 안녕!

 

57분

좌표계 잘 써야

특이점은 미세먼지확산, 공기청정기 작동 두가지 동작으로 나뉘는데

완전히 분리해서 만들어서 확산 디버깅 다로 공기청정기 따로 디버깅 했다는게 특이점. 매우좋은방법.

 

하나 주석치고 잘 동작하는지 확인하면서 check

 

 

09/27 낚시왕

 

83분

크게 두가지로 나눌 수 있었음. 문제에서 나와있었기 때문에 쉽게 나눌 수 있었음. 안그런 문제라도 그렇게 나누자.

좌표 1부터시작하는지 0부터 시작하는지,

vector empty 되는 타이밍 언제인지

 

cmp함수 짠 것도

 

 

참고.

 

09/28 이차원 배열과 연산

 

54분

시키는 대로 구현하면 되었었음.

1중포문안의 sort는 데이터 사이즈가 100 이내일때 0ms 의 결과가 나올 정도로 써도 용이해보임

 

09/28 연구소3

 

3시간

시간초과때문에 힘들었다. 가지치기가 핵심. 가장 크리티컬한 요소를 찾고 그걸 해결할 방법 생각. A형 수준이면 알고리즘이 필요한 게 아니라 간단한 아이디어가 중요

처음 bfs로 구현, 더 좋은 아이디어 같아 dfs로 구현, -> 더 느렸음

이후 질문검색에서 나는 2중포문을 돌면서 바이러스가 퍼지지 않은 곳을 찾아 비효율적이었는데

bfs가 방문한 횟수를 세서 방문횟수랑 빈공간이랑 일치하면 다 돈것으로 판단하는 효율적인 것을 봄.

바로 내 것에 적용하긴 힘들어서 최소 빈공간 만큼와 일치하거나 더 많이 일치하면 2중포문을 돌며 체크하는 원래 함수를

쓰도록 가지치기함.

 

09/28 괄호 추가하기

 

1시간 30분

생각보다 복잡하게 생겼는데 논리적으로 맞게 작성하니까 제대로 돌아갔다.

특이한 점은 9^10 을 곱하면서 오버플로우가 날 수 있다.

또 최댓값 구하는 문제인데 초기값을 -1로 주고 만약 값이 음수가 최댓값이 될 수 있으므로 -1이나오면 이부분 생각해보자.

 

 

09/28 파이프 옮기기1

 

40분

구현하는 대로 구현하면 됨. 특히 오른쪽 아래방향으로만 진행하기 때문에 visited 도 필요없고 쭉 진행하게 두면 dfs 가 알아서 찾아주었음.

특이점은 pipe이동경로에서 애매한 부분이 있었기 때문에 for문화 시키지 못하고 일일히 구현. 하지만 양이 적은 것을 알고 있었기 때문에 의식하고 짠 것임. 더 좋은 코드 참고해보기

 

09/29 캐슬 디펜스

 

65분

 

아래와 같이 기능별로 구분이 되는 코드를 짜서 디버깅이 쉬웠음.

• 같은 거리일 때 왼쪽 우선순위가 있었는데 bfs 탐색 순서를 dx, dy배열을 통해 왼쪽 먼저 탐색하도록 하고 돌린 결과 따로 왼쪽이 먼저인지 구현 안해도 올바르게 작동함.

•  

  이건 이 수식 구현하라는게 아니라 bfs 탐색 순서대로라면 자연스럽게 depth가 거리가 된다는 것을 알게됨.

 

 

 

 

 

09/29 색종이 붙이기

 

3시간.

 

• 뭔가 꼼수처럼 브루트포스를 쓰지 않고 더 효율적인 방법을 찾는 것은 삼성 문제에 맞지 않음. 반례가 있기마련

• 여기서는 왼쪽위부터 가장 큰 색종이를 먼저 붙이면 될 것으로 생각. 25퍼에서 컷

• 그래서 왼쪽위와 아래오른쪽 에서 탐색하는 걸 찾음 50퍼에서 컷.

• 모든 경우의 수를 다 따져야 해서 모든 조합을 생성 후 하나 씩 돌림 (매우 비효율적으로 안돌아감)

• 방법은 매 좌표마다 판단을 하는 것. 중요함

 

09/30

⚾

 

94분

• 간단한 문제였지만 뭔가 말렸다.

• 8개 숫자중에서 8개 순열 구하는 건 1초 시간내에 충분했다.

• 거기서 시간초과가 날 것이라 먼저 염려하고 다른 방법 강구하다가 이 다른방법이 꼼수에 가까워 진다는 것을 보고 포기했다.

• 다시 원래 모든 경우를 탐색하는 방법을 생각해보니 딱히 문제될 건 없었다.

• system("pause") 혹은 cin 을 통해 pause를 걸고 확인해 보았다.

• 테스트케이스하나를 온전히 프로그램으로 돌려보면서 에러부분을 찾았다. 여기선 변수 초기화 타이밍을 놓친 것.

 

09/30 Brain_fuck interpreter (실패)

• 잘 디버깅하면 될 것 같지만 뭔가. .복잡하고 못할 것 같은 기분

• 나중에 다시 해보자

 

10/1 배열 돌리기4 85분

• 찬찬히 잘 하니까 되었다.

• 처음에 배열 돌리는 걸 바깥 가장자리만 돌아가게 생각해서 망했다 했는데 모듈화를 잘 시켜서 size만 1씩 감소시키는 걸로 처리가 가능했음. 모듈화 핵심

•  

10/1 게리맨더링 210-85 = 135분

• 코너케이스 잘 생성하기

• 디버깅 정말 오래 걸렸다. 함수 기능별로 구현해 두고 하나하나 보면서 뭐가 잘못되었는지 명확하게 따지자.

• 코너케이스 가지고 찾는게 좋다.

• cin도 많이 사용.

 

10/18 다리만들기2 116분

• 생각하는 그대로 구현하기

• 디버깅은 체계적으로.

 

10/1 Brain_fuck interpreter 성공

• 조건에 대해서 굉장히 간단하게 구현할 수 있는 문제였지만 생각을 덜 해서인지 시간이 촉박해서인지 그렇기 하지 못했다.

• 정말 아이디어가 중요한 문제였다. 그렇지 않으면 계속 복잡해진다.

• 모든 조건을 완벽하게 맞춰야 하기 때문에 가장 간단하고 확실한 방법을 생각하자.

 

10/1 숫자고르기 KOI

• 사이클찾기

• int 로 visited를 한다음 첫 시작점 dfs에 넣어주고 visited == 2 되면 한 사이클 돈 것으로 침

• 애초에 이런 유형 나올거라 생각도 못해서. 사이클도 답 찾는 관점 안에 넣어두자

 

10/2 아맞다우산 A형대비 BFS+빡구현 81분 30초

• 최단거리 탐색은 두가지 방법이 생각난다.

• 1. dfs로 모든 경우 다 찾은 후 depth작은걸로

• 2. bfs로

• 무조건 bfs로 접근하려 하자. 시간차이난다.

• 간단하게 DP 적용할만한 포인트가 있어 적용했다.

 

10/2 아맞다우산 A형대비 BFS+빡구현 60분

• 사이클 느낌 나면 dfs로 사이클 찾아야 한다.

• bfs로 사이클 찾는 방법도 알아두면 혹시 모를 때 유용할 듯

• 깊이 우선 검색은 폭 넓은 첫 번째 검색보다 메모리 효율이 높으므로 더 빨리 되돌릴 수 있습니다. 또한 호출 스택을 사용하는 경우 구현하기가 더 쉽지만 스택 오버플로가 발생하지 않는 가장 긴 경로에 의존합니다.

• 위와 같으므로 굳이 찾을 필요는 없을 듯

 

10/2 움직이는 미로탈출 A형대비 BFS+빡구현 24분

• 정답률 24%에 푼사람도 별로 없어서 긴장하고 풀었는데 쉽게 풀림

 

• #이 벽인데 이 벽에 닫지 않게 왼쪽맨아래부터 오른쪽 맨위로 도달해야 1을 출력하는 문제

• 백트래킹을 테이블 전체로 적용. 벽을 한번 내렸다가 백트래킹 타이밍에 다시 벽을 올리는 코드를 적용

• visitedcheck가 까다로웠을 법 한데 왜냐하면 방문한 곳 여러번 방문해야 하기 때문.

• 그 방문한 것의 최대값이 모든 벽이 다 꽉차있을 때(사람이 위치하는 좌표 col만 제외) 로 생각, 한곳에 7초과로 머물필요는 없다.

• 이걸 visited 조건으로 추가하니 풀림.

 

10/2 움직이는 미로탈출 A형대비 BFS+빡구현 24분

• 정답률 24%에 푼사람도 별로 없어서 긴장하고 풀었는데 쉽게 풀림

 

• #이 벽인데 이 벽에 닫지 않게 왼쪽맨아래부터 오른쪽 맨위로 도달해야 1을 출력하는 문제

• 백트래킹을 테이블 전체로 적용. 벽을 한번 내렸다가 백트래킹 타이밍에 다시 벽을 올리는 코드를 적용

• visitedcheck가 까다로웠을 법 한데 왜냐하면 방문한 곳 여러번 방문해야 하기 때문.

• 그 방문한 것의 최대값이 모든 벽이 다 꽉차있을 때(사람이 위치하는 좌표 col만 제외) 로 생각, 한곳에 7초과로 머물필요는 없다.

• 이걸 visited 조건으로 추가하니 풀림.

 

 

10/2 성곽 A형대비 BFS+빡구현 50분

•  

• 이게 시간초과 안났다 2초 제한에 376ms로 통과

• M, N 제한이 50미만인데 50^4 에 dfs한번씩하는 시간인데 테스트케이스가 양반으로 나온듯

 

 

10/2 Maaaaaaaaaze A형대비 순열과 조합 97분

• 3차원 벽을 훑는 줄 알고 이상한 고민을 많이 함. (실제 그런 구현이 나오면 어떡하냐)

• 판때기돌리는 것 매우 비효율적으로 노가다 했음 (15분정도 걸림) 그래도 한번에 신뢰할 수 있는 값이 나옴.

• 판크기가 5x5니까 가능했지 그 이상이면 비효율일수도.

• 이것도 시간초과가 날 듯 한데 안났다. 실제 피시로 돌렸을 때 실제시간으로 시간초과라도 그건 프로세서 점유하는 시간 따라 차이나니 채점 서버에선 다를 수 있다.

• 빡구현이었다.

 

 

10/2 Baaa aaaaaaduk2(Easy) A형대비 순열과 조합 51분

• 정말 많은 cout 을 통해 디버그를 하나하나 잡아가며 해결한 문제.

• dfs 조건 맞을 때 바로 나가게 해버리면, 들어온 조건에 대해 visit을 적당히 진행하고 남겨두고 나가기 때문에 제대로 안됨. 바로탈출하는건 시간 크리티컬 하거나 상황 잘 고려해서 하기.