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를 만들어 넣어준다.