728x90 algorithm 썸네일형 리스트형 [백준알고리즘] 9655번: 돌 게임 -C++ [백준알고리즘] 9655번: 돌 게임 -C++ 9655번: 돌 게임 (acmicpc.net) 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 동적계획법동적 계획법 문제이지만, 동적 계획법을 코드에 직접 작성하지 않아도 풀 수 있는 간단한 문제다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 처음 문제를 봤을 때에는 마지막 돌에 두는 모든 경우가 한 사람인 건가? 싶었다. 게임을 하는데 항상 누군가 승자가 정해져있다는 느낌의 문제였기 때문에 실제로 종이에 돌의 번호를 그려보고 상근이와 창영이가 두는 번호를 생각해봤다. 그랬더니 진짜로 겹치지 않는다는 것을 알게 되었다. 예제처럼 돌이 5개 있다고 생각해보자. 상근이가 항상 게.. 더보기 [백준알고리즘] 1168번: 요세푸스 문제 2 -C++ [백준알고리즘] 1168번: 요세푸스 문제 2 -C++ 1168번: 요세푸스 문제 2 (acmicpc.net) 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net 예전에 Python으로 코테 문제를 풀었을 때 \(O(NK)\) 만에 통과하는 코드로 풀었다. 아래가 해당 글의 링크다. [백준알고리즘] 1158, 1168번: 요세푸스 문제, 요세푸스 문제 2 -Python (tistory.com) [백준알고리즘] 1158, 1168번: 요세푸스 문제, 요세푸스 문제 2 -Python [백준알고리즘] 1158, 1168번: 요세푸스 문제, 요세푸스 문제 2 -Python https://www.acmic.. 더보기 [백준알고리즘] 9184번: 신나는 함수 실행 -C++ [백준알고리즘] 9184번: 신나는 함수 실행 -C++ 9184번: 신나는 함수 실행 (acmicpc.net) 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 조건들이 다 주어졌기 때문에 되게 쉽게 풀었다. 문제에 적힌대로 저대로만 사용하면 시간이 오래 걸리기 때문에 하나의 장치를 두어야 한다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 추가해야 할 장치는 바로 메모이제이션(Memoization)이다. 메모이제이션은 재귀와 재귀를 사용하는 DFS, 동적 계획법과 같은 곳에서 많이 사용하는 방법으로, 이미.. 더보기 [백준알고리즘] 1016번: 제곱 ㄴㄴ 수 -C++ [백준알고리즘] 1016번: 제곱 ㄴㄴ 수 -C++ 1016번: 제곱 ㄴㄴ 수 (acmicpc.net) 1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net 시간 복잡도 때문에 문제 푸는데 좀 골머리를 앓았다 ㅎㅎ; 문제를 푸는 데 있어서 시간 복잡도를 생각할 부분이 두 개 있었다고 생각한다. 실제 제출해서 통과한 시간은 다른 분들이 10ms 안팎인 것에 비해 144ms라는 결과가 나왔지만, 푸는 과정은 거의 비슷했지만, 다른 분들은 다 배열을 썼기 때문에 이것은 STL을 사용했기 때문에 발생한 추.. 더보기 [백준알고리즘] 1015번: 수열 정렬 -C++ [백준알고리즘] 1015번: 수열 정렬 -C++ 1015번: 수열 정렬 (acmicpc.net) 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 이번 문제는 이해하는데 어려움이 있었다. 문제를 이해하면 푸는 건 쉽게 풀 수 있는 유형이었다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 먼저, 문제를 이해한 내용에 대해 얘기해봐야겠다. 유독 문제를 이해하지 못했는데.. 문제에서 요구하는 것은 다음과 같다. 배열 \(A\)가 주어진다. 배열 \(A\)에.. 더보기 [백준알고리즘] 1013번: Contact -C++ [백준알고리즘] 1013번: Contact -C++ 1013번: Contact (acmicpc.net) 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 비트열처럼 생긴 문자열에 대한 정규식을 처리하는 문제다. 실제 조건인 (100+1+ | 01)+는 정규 표현식으로도 맞는 조건이니까.. 처음에 노가다로 풀었는데, 풀고 C++에서 정규 표현식이 가능한지 찾아보니까 있었다. 두 코드를 모두 첨부했다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 직접 확인 먼저 해당 정규식을 일일이 확인했다. 정.. 더보기 [백준알고리즘] 1007번: 벡터 매칭 -C++ [백준알고리즘] 1007번: 벡터 매칭 -C++ 1007번: 벡터 매칭 (acmicpc.net) 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 문제를 이해하는데 어려움이 있었다. 정확히 무엇이 P이고 벡터 매칭은 무엇이며 벡터의 집합에 대한 설명, V에 대한 설명 등등 처음 봤을 때 이해하기 어려운 내용들이었다. 결국 이 부분들은 다른 질문 게시판의 글이나 다른 블로그의 글을 통해 이해하고 문제를 풀었다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 문제 이해 먼저, 문제를 이해한 내용에 대.. 더보기 [백준알고리즘] 1005번: ACM Craft -C++ [백준알고리즘] 1005번: ACM Craft -C++ 1005번: ACM Craft (acmicpc.net) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 먼저, 아래의 코드는 비효율적으로 짰다. 아래 코드량만 봐도 왜 이리 긴가 싶을 건데.. 입력의 마지막 조건인 '승리하기 위해 건설해야 할 건물의 번호가 주어진다'는 사실을 몰랐다. 그래서 모든 건물의 건설 시간을 구하는 방안으로 구했다가... 그렇게 작성했던 코드에서 조금 수정하는 방안으로 코드를 작성하다 보니 비효율적으로 됐다. 어제 새벽에 풀.. 더보기 이전 1 ··· 5 6 7 8 9 10 11 ··· 37 다음
