C++/문제풀이 기록 (19) 썸네일형 리스트형 [BOJ 33040, 33041 (조금 어려움)] 마작 거신병 (C++) 개인적인 난이도 :아이디어 - 조금 어려움구현 - 쉬움재미 - 재밌음. 추천해요 https://www.acmicpc.net/problem/33040https://www.acmicpc.net/problem/33041 길이가 W인 수열들 H개로 탑을 쌓아 거신병을 만드는데, 위에 있는 수열의 원소들의 합이 아래에 있는 수열의 원소들의 합보다 크면 안 된다.수열의 원소로는 C개의 1과 D개의 9가 존재하는데, C와 D를 남김없이 써야 한다. 개인적으로는 33041을 먼저 풀고 33040을 나중에 풀었다면 더 쉬웠을 것 같다. 33040의 문제풀이를 주류로 설명하도록 하겠다.기본 아이디어마지막에 for문을 이용해 한 행씩 출력하는데,각 행에는 n개의 9와 W-n개의 1이 포함되어 있을 것이고 원소들이 출력되.. [BOJ 17357, 무난함] 자동차가 차주 김표준의 차를 들면? (C++) solved.ac 마라톤 뛰다가 튀어나왔는데 부동소수점 오차때문에 피똥싼 문제다나같은 사람이 또 있나 궁금해서 구글링해 봤는데 없길래 내가 글을 쓴다https://www.acmicpc.net/problem/17357 이 문제를 풀려면 세가지를 알아야 한다.분산에 대한 지식 (제곱의 평균 - 평균의 제곱)으로 분산을 빠르게 구할 수 있다평균을 빠르게 구하기 위해 누적합을 사용하는 방법부동소수점 오차 줄이기1. 표준편차(분산) 빠르게 구하기표준편차의 제곱은 분산이고, 이 문제에서는 표준편차의 대소비교를 요구하는데표준편차a 표준편차a의제곱 그러니까 표준편차끼리 비교할 필요 없이 분산끼리 비교해도 충분하다.분산의 = 제곱의 평균 - 평균의 제곱 이라는 공식을 활용하면 그나마 빠르게 계산이 가능하다.2. 평균 빠.. [BOJ 26076, 무난함] RPG Extreme (C++) 구현량으로 유명한 문제다정말 구현만 하면 되는 무난한 난이도이지만 실수 한번 하면 익스트림한 경험을 하게 된다어떤 경우에 스파게티 코드가 생기는지 잘 알 수 있었다하지만 차근차근 구현하고 자잘한 실수를 하지 않는다면 어렵지 않은 문제이다 그래서 아래의 과정을 거쳐 코드를 작성하며 실수를 하면 안된다. 1. 끝까지 읽고 계획하기2. 실수 줄이기3. 적절한 테스트 코드 삽입과 디버깅 ps가 아닌 실제 개발 프로젝트 진행 시에는 더욱 그렇기 때문에다이어그램 / 명세서 / OOP / 테스트방법론 / 디버깅 툴 등등을 활용하는 것 같다....코드를 다 짰는데 어느 부분에서 틀렸는지 모르겠어요 ㅠㅠ만일 당신이 디버깅을 위해 이 글을 검색해 들어왔다면 내 글엔 별로 도움될 내용이 없으니 백준 질문게시판이나 뒤져봐라어.. [BOJ 26076, 조금 어려움] 곰곰이의 식단 관리 2 (C++) 제일 알고리즘 공부 열심히 하던 시기에 꼭 풀고싶었는데 못풀었던 문제다0-1 bfs에 대해 공부중 관련 문제에 이게 뜨기도 했고무조건 될 거 같은 아이디어가 생각나서 풀었음 일반적인 bfs와 다른 발상이 필요한 문제다 보니 아이디어를 떠올리기 다소 어렵다고 생각한다.https://www.acmicpc.net/problem/26076 가장 기본적인 bfs문제는 1,1 점에서 N,M점까지 이동하기 위해 최소 몇칸을 이동해야 하는지 계산한다.그렇지만 이 문제는 발상을 반대로 해서, 1,1점에서 N,M 점까지 절대 이동하지 못하게 하기 위해최소 몇개의 벽을 놓아야 하는가에 대해 계산하는 문제이다. 간단한 관찰을 거치면 답은 0,1,2중에 무조건 존재함을 알 수 있다.(그래서 애드혹 태그가 붙은듯)그리고 아이디어.. [BOJ 1918, 조금 어려움] 후위 표기식 (C++) 유명한 문제지만 나처럼 푼 사람은 아무도 없는 것 같아서 내 풀이를 가져왔다 개인적 난이도 : 조금 어려움 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 알파벳을 넣어줄 queue를 사용한다 연산자를 넣어줄 stack을 사용한다. 연산자와 그 연산자의 우선순위를 pair로 집어넣는다. 연산자의 우선순위 비교를 편하게 하기 위해, map을 사용했다. + 와 - 의 우선순위는 0으로 놓는다 * 와 / 의 우선순위는 1으로 놓는다 ( 여는 괄호.. 백준 제 1회 와쿠컵 후기(12솔) + 27965, 27972 풀이 (C++) 의도나 문제나 난이도나 전체적으로 매우 만족스러운 대회였다 충분히 코딩테스트에 나올 수 있는 문제들로, 초~중급 알고리즘의 대부분을 다루고 있다. 어려운 문제만 풀려고 덤빌 게 아니라 실버~골드 문제 랜덤 디펜스를 좀 해봐야겠다는 생각이 들었다 후기 : A번 - 사칙연산 B번 - 비트연산(xor) or 1차원 배열. 좋은 문제 C번 - DP는 안되니까 규칙을 찾아내서 접근해야 함. 복제로 항상 이득을 볼 수 있으므로, 이진수의 자릿수 구하기 문제가 된다. 계속 2로 나눠주면 되고, 0일때의 예외처리가 필요하다. 좋은 문제 C번 문제를 재밌게 풀었다면 https://www.acmicpc.net/problem/11058 이 문제도 풀어보길 바란다. D번 - substring 2개를 만들어서 그 두개의 처음부.. [BOJ 27502, 쉬움] 가난한 고흐와 붓 (C++) 개인적인 난이도 쉬움 인터랙티브 문제는 난이도에 비해 solved.ac 티어가 후하게 달리고, 풀면서 재미가 있다 인터랙티브 문제가 처음이라면?? 이거 푸셈 : https://www.acmicpc.net/problem/23306 https://www.acmicpc.net/problem/25907 전략을 잘못 세워서 똑같은 이유로 2번 틀렸다 문제 이해 : 어떻게 하면 고흐를 가난하게(고흐가 붓을 많이 사용하게) 할 수 있을까? 일단 이 문제는 설명만 대충 읽어 보아도, 그래프 문제 같음 근데 몇 가지 경우만 따져봐도 답이 보인다 위 그림처럼 짝수개의 카드와 짝수개의 박스가 있다. 박스에 카드를 최대 한장씩 넣을 수 있고, 모든 카드를 박스에 넣어야 게임이 종료된다. 박스에다가 카드를 이렇게 넣었다고 하면.. 백준 단계별로 풀어보기 - 시간 복잡도 (24262,24263,24264,24265,24267,24313) (C++) 얼마 전에 [백준] - [단계별로 풀어보기] 에 [시간 복잡도] 단계가 추가되었다. 미리 알아야 할 부분) 알고리즘 문제들을 풀다 보면, 시간제한이 빡빡한 문제들이나 주어지는 N의 범위가 매우 큰 문제들이 있다. 이러한 문제들을 풀기 전에 생각을 하고 코드를 짜야 시간 낭비 없이 문제를 풀 수 있다. 시간복잡도를 정확하게 계산할 필요는 없고 우리는 대략적으로 파악한다. 대략적으로만 알아도 충분하다. 그 방법을 Big-O 표기법이라고 하고, 어떤 코드가 작동하면서 계산이 몇번 이루어지는지 다항식으로 표현한 뒤 최고차항의 차수만 따와서 표기하는 것이다. [백준] - [단계별로 풀어보기] - [시간 복잡도] 를 풀어보면, 시간 복잡도를 대략적으로 파악하는 능력을 기를 수 있다. 그래서, 시간복잡도를 대략적으로.. [BOJ 11444, 약간 쉬움] 피보나치 수 6 (C++) 개인적인 난이도 약간 쉬움 알면 풀고 모르면 못푼다 모르겠어서 아이디어 부분을 구글링하고 구현만 내가 했다 복습) 피보나치 수열을 컴퓨터로 표현하는 방법은 여러 가지가 있다. 1. 재귀함수를 이용해 계산한다 2. dp를 이용해 계산한다 3. (오늘 배울 방법) : 행렬의 거듭제곱을 이용해 계산한다. 1. 기본적인 모듈러 연산의 성질을 알아야 한다. 모듈러 연산의 합/차/곱에 대해 교환법칙과 분배법칙이 성립함을 알고 있으면 된다. 입력과 출력 사이의 과정에서 매우 큰 수를 다뤄야 할 때 자주 나온다. 2. 분할정복을 이용한 거듭제곱을 할 줄 알아야 한다 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A.. [BOJ 25907, 쉬움] 양과 늑대 (C++) 개인적인 난이도 쉬움 인터랙티브 문제가 처음이라면 https://www.acmicpc.net/problem/23306 이 문제를 먼저 풀어보길 바란다 인터랙티브 문제는 머리가 아프지만 실제 난이도에 비해 티어가 높게 잡히는 것 같기도 하고 풀어보면 재미있다. 개꿀임 성공한 풀이) 내가 컴퓨터고 컴퓨터가 사람이라고 생각한 뒤, 이분탐색을 이용해 컴퓨터랑 스무고개를 한다고 생각하면 된다 양의 숫자와 늑대의 숫자가 같아지기 위한 조건은, 어떤 짝수의 날짜 D에 대해 양의 숫자가 정확히 D/2만큼 존재하는 것이다. 우리는 그러한 날짜 D를 찾아내 ! D로 출력하면 된다. 양의 숫자가 D/2보다 많다면, 그 이후에 늑대와 양의 숫자가 같아지는 어떤 날이 존재할 것이다. 양의 숫자가 D/2보다 적다면, 그 이전에 .. 이전 1 2 다음
