BOJ

1181 전체 코드 Sort 메서드에서 comparator로 들어오는 매개함수는 반드시 Strict Weak Ordering을 만족해야 한다. A == B일 경우에는 A B도 false여야 한다는 말이다. 또, vector에서 중복을 제거할 때는 erase 와 unique 함수를 사용한다. 참고자료 Invalid comparator vector...

1259 전체 코드 처음엔 i, j 두 개 변수로 각각 증가하고 감소시켜 값을 비교했는데 틀렸다는 결과가 나왔다. 여러 테스트 값을 넣어도 달라지지 않아 구글링했더니 수의 크기 -1 - i 로 뒷자리를 계산하는 것을 보았다. 그대로 적용했더니 성공. 내가 찾지 못한 테스트 값이 있었나보다. 참고자료 https://codecollector.tist...

1436 전체코드 String 헤더에서 두 가지 함수를 사용했다. 첫 번째는 to_string 함수다. 숫자 타입을 안전하게 string 타입으로 변환한다. to_string 함수엔 많은 원형이 있는데 이는 숫자 타입에 따라 여러 형태로 함수 오버로딩(overloading) 되어서 그렇다. 두 번째는 find 함수다. 문자열 내에서 str을 ...

1654 전체 코드 시행착오 while 문으로 작성했더니 시간 초과가 떴다. 알고리즘 분류란을 열어보니 이분 탐색이 있었다. 이분 탐색은 공간을 하나하나 탐색하지 않고 중간값을 비교하여 탐색한다. 이분 탐색을 적용한 코드는 다음과 같다. 그래도 시간초과... 결국 풀이를 구글링했는데, 조건문을 더 줄이고 줄어드는 값에 middle은 제외하는 ...

1874 전체코드 코드를 짜는 내내 비효율적이라는 생각을 했다. c++로 더 짧고 간단하게 문제를 해결할 수 있을 거 같았는데, 역시나 아래 블로그엔 정말 짧고 간단한 알고리즘을 갖고 있다. 참고자료 c++

1920 전체코드 find 함수를 썼더니 시간초과가 나서 binary_search 함수를 사용했다. 그래도 똑같아서 가장 위의 두 코드를 사용해 cin, cout의 시간을 줄여줬다. 시간 초과는 해결되었으나 마지막 테스트 케이스에서 '틀렸습니다'가 나와서 인풋을 인덱스로 받아주고 bool it 을 생략해줬다. 통과! 구글링하니까 직접 이분 탐색 구...

1929 전체코드 while 문으로 하나씩 소수를 구하려고 했는데 시간 초과! 알고리즘 분류란을 열어보니 에라토스테네스의 체가 있었다. 이를 구글링하니 위키피디아에 c++ 코드가 그대로! 바로 가져다 쓰니 통과! 찝찝하지만 몰랐으면 절대 못 풀었을 듯. 처음 보는 개념이었다 ㅎㅎ.. 참고자료 에라토스테네스의 체

22351 처음엔 그 다음 숫자가 연속되었는지 확인했는데 2자리 숫자와 3자리 숫자를 판별하는 것이 어려웠다. 그리고 코드도 길어지는 것 같아서 구글로 답을 찾아봤다. 결론은 루프를 두 번 돌려서 같은 문자열을 찾는 것. 알고리즘 생각할 수 있으면 바로 푸는 문제! 참고자료 22531 정답!

1260 처음 DFS와 BFS 이론을 보고 그래프를 vector로 push_back으로 해당 간선을 넣었는데 테스트케이스에는 1부터 탐색하는 방향이어서 틀렸다. 그래서 1260 답을 찾아보고 이중 배열로 그래프를 처리해 앞에서부터 찾아나가는 방식으로 고쳤다. 런타임 에러 -> 틀림 -> 정답! 참고자료 DFS와 BFS 이론 1260 답

2178 BFS로 최소 거리를 찾는 원리를 구글링해서 찾아봤다. 그 사이트에 예시 코드가 있어 그걸 바탕으로 미로에 적용시켜 pair로 좌표를 찍어 구현했다! 지금은 DFS BFS 가 어려운데 익숙해지면 코드 짜는 것도 수월해질 듯하다. 참고자료 BFS 최소 거리 원리 c++ pair c++ 입력받기 [VS scanf 오류 해결](https://p...

10718 단순한 출력!

10926

18108

10430

2588

25083 " 출력은 앞에 \ 붙이기 \ 출력은 앞에 \ 붙이기

14681

2525

2480

8393

11021

11022 printf으로 출력하는 것이 더 간단할지도?

1110

15552 c++ 시간초과 줄이는 방법 사용하기.

4344 소수 형식을 맞출 때는 divisor의 형식을 맞춰주기 scanf printf로 입출력 해보려다가 다시 돌아와 버렸다.

1074 최종 코드 구글링으로 답을 찾아봤는데 갑을 저장하지 않고 r과 c를 사분면에서 찾아 값을 도출하는 방식이었다. 굳이 값을 저장하지 않아도 해결 가능! 시간 정해놓고 푸는 게 좋을 것 같다. 시행 착오 이렇게 짜니까 메모리 초과가 왔다. 참고자료 1074 c++ 솔루션

7662 최종코드 시간 초과가 나와서 찾아보니 multiset을 사용한다고 했다. multiset은 set과 달리 중복 가능한 수를 포함할 수 있다. 원소를 넣으면 자동으로 오름차순 정렬이 되고, 트리 자료 구조로 중위 순회를 사용해서 이전 코드에서 계속 최댓값 최솟값을 찾는 것보다 빠르다. 시행착오 참고자료 7662 솔루션 c++ set 사용...

10026 저번 미로찾기에서 너무 코드를 낭비한 것 같아서 좋은 방법이 있는지 찾아봤는데 dx, dy로 상하좌우를 쉽게 검색하는 방법이 있었다. 저번에 2667번인 단지번호 붙이기를 보고 못 풀었는데 이 문제와 같은 형태인 것 같다. 다음에는 이 코드를 바탕으로 다시 풀어보기! 참고자료 10026 c++ 솔루션

2667 10026번의 코드와 거의 똑같고, 세부적인 부분만 조금 바꿨다.

15596

2606 dfs로 풀었는데 bfs로 풀었어도 될 듯?

1012 범위 이슈가 있었어요~

vector에서 지우기는 꽤 까다롭다.

한 번에 통과~

시간초과와 메모리 초과를 반복하며 겨우 삽입형식으로 풀었는데 우선순위 큐를 쓰는 문제였다!

우선순위 큐를 알아보았어요~

스택이구만!

예전에 풀었던 문제. break를 적절하지 않게 써서 틀렸다. 과거의 나는 return을 써서 풀었는데, 말랑말랑 두뇌교실이었구만..

예이~

질문 게시판에서 맞는 반례가 없었던 문제..알고보니 else if 때문에 일어난 일이었다.조건 나눌 때 조심하기.

백트래킹을 배웠다!한층 쉽게 조합을 구할 수 있게 되었다.고민했던 부분은 조합으로 삭제할 치킨 집을 구할지 아니면 유지하는 치킨 집을 구할지였는데 여러 번 수정하다가 유지하는 치킨 집 구하기로 정했다.

문제를 보고 무서워서 구글링을 했는데자세히 보진 않고 코드 길이만 보고 오~ 생각보다 짧은데 하고 풀었더니 풀렸다. ㅎㅎ1025 c++

dfs를 이용한 백트래킹.

백트래킹 다운 문제를 풀었다.한정조건을 사용했다.

처음에는 2차원 배열로 풀려고 했으나 시간이 너무 걸리고 답도 이상해서 바로 답을 찾아보았다.1차원 배열로 짧은 코드로 푸는 방법이 있어 참고했다.그럼에도 대각선에 있는지 탐색하는 부분에서 애를 먹었는데, 열과 행의 차이가 같을 때를 찾는 걸 보고 풀 수 있었다

시간 초과로 해답을 보니 알고리즘은 비슷했으나 자료형에 저장하는 작업을 거치지 않아서 빨랐다.

풀이를 그대로 가져왔습니다.. 간결하게 코드 짜기 어떻게 하는 거야~

큐에 넣고 하나씩 비교하면서 출력하니 느리긴 하지만 정답 처리가 되었다.

부분의 시작 인덱스를 pair로 받는 방법을 생각했는데 코드가 너무 복잡하고 예제도 통과하지 못해 풀이를 찾아보았다. 해당 분할 구간에서 0과 1을 확인한 후 맞는 경우 압축하고, 아닌 경우 분할을 한 번 더 진행한다.이전과의 차이점은 분할을 할 때 조건을 통과

처음 시도할 때는 lower_bound 대신 find를 사용했는데 시간 초과가 일어났다.이유는 find 함수는 시간복잡도가 O(N)을 필요로 하는데 lower_bound는 이분탐색으로 O(logN)을 가지기 때문이다.

음화화

단순히 swap을 통해 내림차순으로 정렬했는데 1%에서 바로 탈락..사전 뒷순이라 S가 여유있다면 큰 수를 먼저 끄집어 내야 한다.풀이를 보고 이해했는데 생각보다 간단했다.해당 인덱스 이후의 숫자들 중 최대값을 찾고 S값과 비교하여 앞으로 끌고 오는 것.

랜선 자르기와 유사한 문제, 이분 탐색 내부의 조건만 변경하면 된다.

풀이를 생각하기 어려운 문제.먼저 간격을 정하고 집들을 정렬한 뒤 왼쪽 집부터 차례대로 공유기를 설치한다.그리고 설치된 공유기의 개수와 제공된 공유기의 값을 비교해 간격을 이분 탐색으로 조정해나가 최대 값을 정한다.2110 c++ 풀이

1931 참고자료 1931 풀이

11399

수를 vector에 인덱스와 담아 큰 순으로 정렬하고 현재 수보다 인덱스와 값이 더 크면 해당 값과 현재 수를 뺀 값을 더하도록 했다.잘 진행되더니 83% 에서 시간 초과!풀이를 보니 거꾸로 계산하는 방식을 사용했다.바로 적용하니 성공.. 대박..

거리를 구해서 반으로 쪼개어 가면 되지 않을까 했는데 틀렸습니다...풀이를 보니 이분 탐색을 사용했다.전에 푼 공유기 설치하기 문제와 비슷해보이긴 했는데 이분 탐색이었다니

풀이를 보고 말았어요.누적합과 이분 탐색으로 푸는 방법이 있어서 참고했다.이 문제의 핵심은 우체국 좌우의 사람이 균등하게 있어야 최적해를 낸다는 것.그리디로 푸는 방법은 사람 수의 중간값을 구해 첫 마을부터 사람의 수를 더해가 처음으로 중간값과 같아지거나 커지는

DP가 기록을 이용해서 푸는 방법인 건 알고 있었는데 어떤 부분을 기록해야할지 모르겠어서 풀이를 보았다.

점화식 생각하기가 힘들구료..

알고리즘 수업 때 배웠는데 다 까먹어버렸다 ㅎㅎ

오랜만에 그래프 문제를 풀어서 이론을 다 까먹어 버렸다. ㅎㅎ...

그래프만 생각하다보니 주사위 던지는 부분을 생각하기 어려워 풀이를 보았다.생각보다 단순하게 풀이가 가능하다.세상에는 똑똑한 사람이 많아..

세울 벽을 고르는 것을 브루트포스로 하고, 바이러스가 퍼진 것을 추적하는 것을 bfs로 풀이하는 것을 알아채면 구현만 열심히 하면 된다.

시간초과가 났습니다...아기 상어가 9보다 커지면 자기 자신을 먹는 대참사가 벌어지기 때문에 처리를 해주어야 한다.

visited를 pair로 만들어서 거리와 벽을 부순 횟수를 저장하도록 했다.벽을 부순 횟수가 2보다 작으면 거리를 비교해 작은 값을 visited에 저장하고, 작은 경로만 진행하도록 했다. 하지만

bfs로 풀어버리기~

처음에는 가장 안쪽 for문의 변수를 경유 지점으로 삼았는데 순서의 문제가 있어서 가장 바깥쪽 변수를 경유 지점으로 정했다.

플로이드 알고리즘 조금 변경해서 풀었더니 낮은 값만 비교하도록 되어있다.답을 구한 후 대각선 기준으로 대칭해서 정답~

플로이드 워셜 알고리즘으로 풀었으나 시간 초과로 실패..다익스트라로 푸니까 완전 빠름!

인접 행렬로 풀었더니 시간 초과 났다.인접리스트로 바꾸니까 해결~변환하기 은근 어렵넹

어렵넹 알고리즘

16398 드디어 크루스칼, 프림 알고리즘 쓰는 문제 풀기~ 참고자료 MST 알고리즘 프림 알고리즘

1647 참고자료 크루스칼 알고리즘

왜 됨?

문제를 잘 읽도록 하자~

방향 설정하는 부분이 어려워서 풀이를 찾아보았다

반시계로 풀었더니 틀렸당시계방향으로 고치니 됐다..

뿌요뿌요~

뱀 게임을 만들었어요!

주사위 2차원 배열 만들 생각하기 힘드네용

시간 초과가 계속 나와서 풀이를 참고했다. 풀이 중 위 코드에서 초기화를 하지 않아도 되나? 하는 생각이 들어 map 자료구조를 찾아보았다. map의 연산자는 해당 key를 찾은 후 없으면 기본값을 value로 pair를 만들어 넣어준다.

토마토 숙성시간을 찾는 문제

분할 정복 리마인드 문제!

2493번 탑 문제를 풀면 비교적 쉽게 접근할 수 있는 문제.최댓값을 두 번 이상 가질 때 이를 체크해야겠다고 생각했는데, 큰 값을 저장하면서 풀면 따로 인덱스를 기억할 필요가 없었다.

문제 해석을 잘못해서 4(0) 과 4(0(1))의 다른 점을 이해하지 못했다.그 후에는 string 을 담는 stack 구조로 문제를 풀었는데 메모리 초과가 났다. ㅎㅎ.결국에는 int로 stack을 만드는 힌트를 얻고 겨우 문제 풀이 성공.. 어렵네용..

처음에는 문제의 코드를 붙여 넣어 조건 안에서 횟수를 더하도록 만들었는데 테스트 케이스가 커지고 숫자도 커지니 시간 초과가 발생했다.아무래도 단순 구현은 아닌 것 같아 기존의 값을 저장하는 방식으로 재귀를 구현했다.

처음에는 set 컨테이너랑 함수 호출 형식으로 작성했는데 시간 초과가 났다.find를 계속 돌리는 것과 함수 호출에서 느려지는 것 같았다.문제를 보니 x의 범위값이 1에서 20뿐이어서 bool 배열로 값을 저장하도록 진행했다.그리고 성공!

사전순 정렬을 해야 해서 sort 함수에 compare 함수를 보충해주었다.set 컨테이너는 레드 블랙 트리로 구현되어 있어서 삽입, 삭제, 탐색이 용이하다.레드 블랙 트리

11047 성공 코드

처음 시도했을 때 시간 초과, 2차원 벡터로 전체 합 저장하려고 보니 메모리 초과, 알고리즘 열어보니 누적 합이라고 나와서 적용했더니 틀렸습니다...마지막엔 개행 문자를 안 넣어서 생긴 문제 ㅎㅎ

바로 이분탐색으로 시작했지만, LLONG_MAX 가 컴파일 에러가 나서 실패.다음에는 경계값으로 인해 무한 루프를 돌거나 답을 못 찾아서 실패.질문 게시판의 반례는 신이야!

11651 성공코드

문자열로 숫자 판별하는 방법을 찾아보니 c++에 적합한 함수가 따로 있지 않았다.indigit 함수는 문자 하나만 판별하는 것이고, c의 atoi 함수로도 판별하는 방법이 있다.이번에는 string 의 stoi 함수를 사용하기로 했다. stoi의 함수는 int로

바로 완전탐색을 하면 시간 초과될 것 같아서 다른 방법을 생각해봤는데 마땅한 게 없었다.그냥 vector로 돌려보니 바로 통과~

딱 보니 map을 쓰면 좋을 것 같아 써버렸다!

뭔가 dp일 것 같았는데 코드를 어떻게 작성해야 할지 모르겠어서 풀이를 찾아봤다.N부터 시작하는 걸 생각했는데 N까지 도달하는 풀이였다.생각보다 엄청 짧은 풀이여서 놀랐다.규칙찾기 너무 어렵드아.

코드가 정말 길어져서 이게 맞나.. 하고 있었는데 통과했다. 잉?다른 코드들을 찾아봤더니 3,5의 배수가 3개 연속되는 경우는 없다는 사실을 알게 되었다. 그래서 완전 간결했다 ㅋㅋ...

문자열이 너무 커져서 방법을 찾아보다가 계산기로 연산 하나하나 쪼개서 연습해봤다. 곱하고 더하는 각 연산 사이에 모듈러 연산을 해도 값이 똑같이 나왔다.해싱은 알다가도 모르겠당

2와 5를 곱하면 10이 되니 두 수의 개수 중 최솟값이 정답으로 생각해서 다음과 같이 코드를 짰다. 하지만 5의 개수가 2보다 현저히 낮기 때문에 5의 경우만 생각해도 되는 문제. 시간이 넉넉해서 통과했으니 상관없다!

n을 6까지 구해봤는데 모르겠어서 답을 찾아봤다.이전의 3가지 경우를 다 더하는 거였다.점화식 찾기 쉽지 않네..

11724

완전탐색인가 했는데 종료조건을 찾기가 힘들었다. bfs로 탐색하면 최소조건을 가장 먼저 찾으니 이 방법을 사용!

11727 노트 한장 꽉 차게 써서 점화식 찾았다. ㅎㅎ 근데 이렇게 푸는 게 맞나..? 성공코드

탐색을 어떻게 해야할지 고민했다.조건과 분기점이 많아지면 쉽게 피로를 느끼는 습관을 고치는 게 좋을 듯.

요즘 간단한 문제는 코드를 올리지 않고 있는데, c++ 문자열에 대해 몰랐던 사실을 알게 되어서 작성한다.아래의 코드에서 max를 -1로 설정하고 평소처럼 str.length() 함수를 사용해서 길이를 비교하려고 했는데, 아무리 해도 비교가 반대로 적용이 되었다.

처음에는 삽입 정렬로 했다가 광탈.두 번째에는 이분탐색으로 했다가 광탈.그리고 알고리즘 분류를 확인하고 우선순위 큐인 것을 확인하고 적용했다.하나만 사용하는 것으로 생각하고 이를 중간값까지 뽑았다가 다시 넣는 방법을 생각했다.처음에는 벡터에 값을 다 저장하고 큐

dfs와 bfs를 섞어서 냈더니 시간초과.visted에 최솟값을 갱신하며 찾으려고 했는데 또다시 시간초과.풀이를 찾아보니 생각보다 간단했다. 경로 내의 최솟값으로 k와 비교한다는 것은 k보다 작은 경로로는 동영상 추천을 안 하는 것.

전혀 풀이를 생각하지 못해서 풀이를 찾아봤는데 2차원 배열로 모든 경우의 수를 기록한다. 그저 감탄.난 전혀 DP하고 있지 않아..아이디어 생각하기가 힘든 것 같다. 풀다 보면 나아지겠지?