코딩테스트

내가 풀이한 것

14500번 테트로미노

scanf, printf을 쓰면 자꾸 틀렸다고 나온다... cin, cout을 사용해야겠다.

백트래킹 기법이 있다. 백트래킹은 기본적으로 부르트포스 기법을 응용한 것이다. 부르트포스처럼 계속 돌면서 특정 조건이면 그쪽으로는 더이상 뻗지 않는 것이다.그래서 기본적으로 부르트포스로 코드를 짜고, if로 건너뛰게 해주자평소에도 많이 사용하는 기법인데, 구체적인 조건

이어지는 브루트포스문제이며 백트래킹으로 적절한 조건을 잘 찾아야 한다. 스도쿠문제는 1)같은 열, 2)같은 행, 3)3x3 정사각형 안에 같은 숫자가 존재해서는 안된다는 조건이 있다. 따라서 각 조건에 따라 if조건문을 만들어야 한다. int 반환형을 void 반환형으

내가 봐도 너무 비효율적으로 짠 것같다.. 나는 순열이나 조합을 재귀로 직접 구현하는 것을 선호하는데, 풀이에서는 next_permutation으로 그냥 넘겨버리는 것 같다. 나중에 이번 문제보다 약간 더 어려운 "링크와 스타트"에서 보완해봐야겠다.

맞았지만 이번에도 너무 비효율적이다. ch배열을 이용하여 이전에 방문한 지점이라면 continue했다. 하나의 점에 대해 일일이 DFS를 하고, 끝났으면 모든 ch배열을 다시 초기화하였다.

DFS을 사용하여 그래프의 사이클을 찾고, BFS를 이용하여 거리를 찾아가는 문제이다.여러 문제를 풀면서 DFS에서 반환형을 void로 할지, int로 할지 계속 고민이 많아졌다. 해당 문제가 그 궁금증을 해결해 줄 것이라고 생각한다. 재귀에서 돌아올 때, 해당 재귀가

이번 문제에서 공부할 것은 다음과 같다.1) 이분 그래프를 활용한다. 여태 제대로 배운적이 없다. 이분 그래프는 BFS, DFS둘다 이용할 수 있지만, DFS를 사용하려고 한다. 시작 노드를 RED로 하고, 시작 노드와 연결된 다음 노드는 BLUE로 지정한다. 그 다음

이미 짜인 그래프에서, 입력이 들어올 때 그 순서대로 BFS를 했을 때 통과되는지를 확인하는 문제이다. 입력이 여러개가 가능한 이유는, BFS가 하나의 점을 queue에서 빼낼 때, 그 점에서 연결된 점들 중, 어떤 순서대로 빼든지 상관이 없기 때문이다. 1\. che

정답률이 35%라서 약간 쫄았는데... 시간은 2시간 걸렸지만 결국 혼자서 풀어냈다ㅠㅠ사실 입력을 잘못 받아놓고 있어서 더 빨리 풀었을 수 있었지만 까불지말자기본적인 BFS이해만 있으면 금방 풀 수 있는 문제이다. 나같은 경우에는 map배열에 각 칸에 뱀과 사다리가 있

어려운 문제만 풀다가 쉬운 문제를 푸니까 너무 좋다.백준풀면서 처음으로 17분만에 풀었다ㅎㅎ 아직 갈길이 멀지만 예전보다는 늘은 느낌이 든다. 굿~!

음.. 처음 생각에는 일일이 3개의 벽을 세워두고 BFS를 쓰면 되지 않을까 생각했었다. 그런데 너무 비효율적이진 않을까? 라는 생각에 계속해서 고민해보았다. 그런데 그게 맞았다. 시간복잡도와 브루트포스에 대한 자신감을 가지고 해야겠다.

변하는 것과 변하지 않는 것을 잘 구별해야겠다.1\. 총 돌의 개수는 변하지 않는다. 이를 이용하여 (A,B,C) => (sum/3, sum/3, sum/3)의 점으로 이동하는 문제로 바라볼 수 있다.2\. 또 하나더, a배열을 선언하고, DFS에 넣을때 a배열이 아닌

문제를 풀기 전에, 시간복잡도를 계산하는 것은 중요하다. 그래야 단순히 브루트포스를 사용할 수 있는지, 추가로 고려해주어야 하는지를 판단할 수 있기 때문이다.이 문제와 같은 경우에는, 벽이 최대 O(NM)일때, 하나씩 부수고 그때마다 탐색해야 한다고 치면 O((NM)^

이번에도 좋은 문제이다. 내가 바로 직전 문제에서 가지고 있었던 BFS에 대한 개념들을 기분좋게 지적해주었다. 나는 이전까지 BFS를 풀때 따로 check배열을 두고 풀면 거의 대부분 풀린다고 생각했었다. 그런데 이번 문제는 한층 더 들어가서 그룹화시키는 작업이 필요하

얻을게 많은 문제이다.시뮬레이션과 구현파트에 있는 문제인데, 결국에는 재귀(DFS)나 BFS를 사용한다.이번 문제는 재귀를 사용한다.1\. 문제를 풀때마다 들었던 의문이 있다. 이 문제는 브루트포스인가? 그리디인가? 아직까지 내가 만난 문제들은 명확한 답을 요구하기 때

제목대로 가르침받았다.. 후 너무 어렵당 다시 풀어봐야겠다.정리할게 너무 많다.우선 비트마스크는 보통 모든 부분수열을 찾을 때 사용한다. 따라서 선택가능한 K개의 알파벳중 일일이 알파벳을 선택했는지의 여부는 재귀를 통해 해결한다.해당 문제를 일일이 26개의 알파벳 중에

아 나중에 풀어야겠다..아래는 오류코드임

문제가 되게 기본적이지만 이런 문제일수록 처음에 생각한 답이 절대 아니다.일일이 해보면 되는거 아니야? 라고 생각할 수 있지만, 통과할 수 없을 것이다.이런 기초적인 문제일수록 생각해야 하는 2가지가 있다.1\. 불필요한 작업을 하고 있는가?2\. 중복되는 작업을 하고

전 문제에 이어서 약간만 수정하였다.

비트마스킹과 '중간에서 만나기'를 활용하였다.'중간에서 만나기'란 양쪽 절반에서 모든 경우를 다 해보는 방법이다.A에서 B까지 가는 시간이 60분이라고 할때, A -> C <- B 처럼 중간에서 만나면 30분만에 만날 수 있다.이렇게 시간 복잡도가 2^N => 2

벽 부수고 이동하기 1보다는 어렵고 4보다는 쉽다.. 당연한 얘기ㅎ그냥 1에서 조금만 수정해주면 된다.

2보다는 어렵고 4보다는 쉽다..밤낮을 잘 구별하는게 포인트다.

지난 번, DFS를 사용할 때(재귀)map이 계속해서 바뀌면 벡터 그대로 함수에 넣어주라고 말한적이 있다. 하지만 여기서는 BFS를 사용하겠다.키 포인트는 캐릭터가 이동하고 나서 map을 한 칸 내릴텐데, 언제 Q에 넣고, 언제 map을 내리는지가 중요하다. queue

내가 처음 올린 심바와 똑같은 문제이다. 다시 푸니까 감회가 새롭당아기 상어가 <먹이를 먹을 수 있는지>, <먹이를 찾으러 출발>부분으로 나누어서 풀었다. 코드에서 simba가 아기 상어다.

생각이 너무 복잡해서.. 실패했다. 내가 시도한 방식은 이전에 진행해온 방향을 저장하고, 그 방향대로 한칸이동, 거울 방향대로 2가지, 총 3개를 queue에 넣어주었다. 허우적대다가 실패했다.거울이라는 한정된 정보에 매달리지 말고, 똑같이 상하좌우를 탐색하는게 단순해

코딩 스킬에라토스테네스의 체라는게 있다. 소수를 찾을 때 빠르게 구할 수 있다.배열의 초기값이 false라 조금 헷갈릴 수도 있는데... 어떤 수가 소수라면(초기값은 false), 그 수의 배수는 다 소수가 아니다. 그래서 반대로 true로 설정해준다. 다 돌면 반대로

최근에 sk하이닉스 원서랑 영어때문에 코테연습을 못했었다. 쫌만 안해도 감을 잃어버리는 것 같다. 꾸준히 하자!!이번 문제는 상당히 쉽다. 건질게 있다면 영역을 구분할 필요가 있기 때문에 queue를 이용하되, 브루트포스로 하나하나 위치를 탐색하도록 감싸주는게 필요하다

set에 대해 알아보자. set은 중복제거용 체크배열로 많이 쓰이는 것 같다.처럼 해주면 된다. 넣을때는 insert를, 뺄 때는 erase를 사용한다.count는 해당 인덱스가 있으면 1, 없으면 0을 반환한다.쫌 헷갈린다. 특히 long long이 붙어야 하는 10

왜 정답 비율이 33%인지 잘 모르겠다. 그나마 주의할 것이 있다면 ch배열을 1000001로 해야한다는 것?

break를 2번 사용하였다. 더 효율적으로 쓸 수 있을 것 같은데...굳이ㅎ

어렵지만 얻어갈 것이 많다.vector 사용법에 대해서 제대로 복습할 수 있었다.문제를 해석하는 흐름이 배울게 많았다.로봇 청소기가 ix1,y1->jx2,y2로 갈 때 최소한의 거리를 di에 저장한다. 이렇게 따로 저장해두면, 1->2->3으로 갈 때나 3->1->2으

오홍.. 안보고 잘했당ㅎㅎ전 문제와 비슷한 면이 있어 잘 풀 수 있었다. 벽 부수고 이동하기랑도 비슷하다.

`

97%에서 실패했었다... 이때 반례가5 21 1 1 1 11 1 2 1 11 1 2 1 11 1 1 1 11 1 1 1 1처럼 처음부터 바이러스가 퍼졌을 때는, 시간이 0초이다. 따라서 BFS를 다 돌리고 난 다음, dist의 max값을 구해주었다.참고자료https&

호우~ 연구소 2와 비슷하지만, 바이러스가 활성화되지 않더라도, 바이러스로 친다는게 다른 점이었다. 이 때문에 모든 공간을 바이러스로 감염시키는 시간이 줄어든다.

재밌는 문제였다. for문을 2번 돌릴 때, dx\[i]가 아닌 dx\[k]로 정확히 확인하자. 이거때문에 시간 좀 잡아먹었당..

이 문제는 바로 직전 문제인, 나무 재테크와 닮아있다. 나무가 번식하는 것과 미세먼지가 확산되는 것이 공통점이다. 공기청정기에 대해 처음 생각한 것은 공기청정기의 위치를 어떻게 저장하는 것이 효율적일까?

우선 잘못된 코드이다억지로 vector map\[]\[]에 push_back으로 더 꼬아버렸다. 그냥 int map\[]\[]으로 재시도 해보겠다.

꿀잼문제삼성은 요런 문제가 많이 나오는 것 같다. 나중에 다시 한번 풀어보자. 계절을 하나로 합쳤는데, spring, summer, fall, winter의 함수로 나누어서 한번 더 풀어봐야겠다.

구현문제같은 경우, queue보다 vector를 쓰는게 시간측면이나, 흐름을 따라가는데 더 좋은 것 같다..

쪼금 더 어렵다..

아흉 어렵다

이번 문제는.. 좀 그렇다. 일일이 다 구현해야 한다니...헷갈려 죽는줄 알았다.

누가 햄버거를 몇억장씩 패티를 넣어서 파냐...ㅠㅠ

이름부터 삐뚤빼뚤 도미노스럽다.주의 할점은 비어있는 공간을 찾을때 위에서부터(0번행) 끝까지 내려간다는 것이다. 그래야 최대한 내려갔을때, 그 위는 비어있는 공간이라는 것이 보장된다.

오랜만에 easy~ 가볍게 재귀를 사용하면 된다. (나는 재귀를 사용할때 함수를 항상 DFS라고 쓴다.. 조심하시길!)

낼름~ 뱀처럼 생각하면 쉬운것 같다.

되게 단순한 문제인데 묘하게 헷갈리네ㅎㅎ

이전에 어렵게 풀었었던

처음 생각이 어렵다.참고자료 https://yabmoons.tistory.com/49

약간 노가다로 풀었는데.. 재귀로 충분히 풀 수 있을것 같다.재귀로도 도전해보자!

은근 꿀잼

맞았넹.. 벡터를 함수로 건네줄 때 call by value로 할지, reference로 할지 많이 헷갈린다..value로 주게 되면 건네주기 전의 벡터값은 바뀌지 않지만, reference로 주게되면 건네주기전의 벡터값이 바뀌기 때문에 주의가 필요할듯??

처음 시도한 방법은 90회전의 중심이 되는 점을 잡고, 일일이 이동하려고 했다. 아래는 미완성 코드.. 하지만, 규칙성을 찾아내고 좌표나 도움이 되는 값을 계속 들고 있는 것이 무척 도움이 되고, 편리하다. ex) 방향 좌표를 v벡터에 계속 저장한다. 0세대 : 0 1세대 : 0 1 2세대 : 0 1 2 1 3세대 : 0 1 2 1 2 3 2 1 이렇게 ...

오랜만에 조합을 썼당

아.. 이게 맞나.. 그냥 일일이 다했다.

테스트 케이스 하나가 자꾸 안맞은 코드... 주의다시 풀어보자...참고자료 https://yabmoons.tistory.com/303

예외처리가 좀 어려웠다..

쉬운 문제였는데, 문제 설명이 난해해 푸는데 오래걸렸다. 요런것도 잘해야겠지...

2시간 정도 걸렸다.. 아 계속 디버그에서 시간을 너무 쏟는다.. 처음에 잘하자!!!

이것도 2시간 걸렸다.. 왤캐 문제를 이해하기가 어렵지...똑바로 이해하고 코딩에 들어가자!!

오.... BFS할때 check배열을 가볍게 생각했었는데 중복개념이 들어가니까 디버그를 찾는데 엄청 시간이 걸렸다..결국 2시간 반만에 해결!

문제가 더럽게 만들지 않고 깔끔하게 주어져 가볍게 풀었다.

주의!! 75%에서 틀린 문제이다. 나중에 다시 풀기!

다시 기초로 돌아간다. 기업의 코딩테스트 문제가 생각보다 어렵지 않아서 이런건 왕빨리 풀어야한다.나머지 연산의 기본적인 방법이다.

이 있다.if(isupper(a\[i])) {...} 는 대문자 출력if(islower(a\[i])) {...} 는 소문자 출력if(isdigit(a\[i])) {...}는 숫자출력a.push_back('s') , a = a+'s'는 s문자 추가a.pop();은 마지