PS Diary - 백준

PS 백준 - 1.1 8958번: OX 퀴즈PS 백준 - 1.2 2577번: 숫자의 개수PS 백준 - 1.3 2669번: 직사각형 네개의 합집합 면적 구하기PS 백준 - 1.4 10809번: 알파벳 찾기PS 백준 - 1.5 2167번: 2차원 배열의 합PS 백준 - 1

OX 채점결과를 문자열로 받은 뒤 str.length와 str[j]로 접근하여 점수를 더하는 형식으로 코드를 작성하였다.

백준 2577번 - 바로가기엄청 간단한 문제지만, 그리고 숫자로만 풀어도 다 풀리지만 수업시간에 배웠던 것들을 사용해보고 싶어서 복잡하게 풀어 보았다.

백준 2669번 - 바로가기중복 처리를 위해 set 컨테이너를 이용하였다. 구현 방법도 다양해서 별로 어렵진 않은 문제였다.

백준 10809번 - 바로가기 난이도: 브론즈 2알고리즘: 문자열알파벳을 인덱스로 사용할 때 str.at(i) - 'a' 로 접근한 것이 포인트였다.

백준 2167번 - 바로가기 난이도: 브론즈 1알고리즘: 배열, 누적 합동적할당하기 귀찮아서 2차원 벡터를 이용해서 코드를 짰다. 이 문제는 마지막 (i, j) ~ (x, y)의 뜻이 모호해서 함정이 숨어 있었다. (1, 3) ~ (2, 3)이라 하면 (1,3), (2

백준 4344번 - 바로가기 난이도: 브론즈 1알고리즘: 수학, 배열이 문제는 출력 때문에 내용을 찾다가 새로운 것을 배웠다. cout에서 소수점을 출력해줄 때가 문제였는데, https://blog.naver.com/retican/221587346886 블로

백준 10988번 - 바로가기 난이도: 브론즈 1알고리즘: 문자열큐를 이용하여 풀어보았다.

백준 2804번 - 바로가기난이도: 브론즈 2알고리즘: 문자열

백준 10798번 - 바로가기난이도: 브론즈 1알고리즘: 문자열, 큐

백준 1120번 - 바로가기난이도: 실버 4알고리즘: 문자열

백준 16926번 - 바로가기난이도: 실버 3알고리즘: 배열옮기다보면 임의의 한 직선 위의 원소들은 시작과 끝이 동일해 덮어씌워진 수가 다시 복사되는 경우가 있다. 따라서 스타트 지점들을 따로 저장해두고 나중에 다시 불러오는 방법을 사용하였다.

백준 2607번 - 바로가기난이도: 실버 4알고리즘: 문자열나는 처음에 multiset을 이용하여 단어들을 저장한 뒤, mismatch 알고리즘으로 다른 부분을 잡아내려고 했다. 근데 이러면 잡아낸 단어를 삭제하고 다시 한번 더 돌려야 되는 번거로움이 있고, misma

백준 2309번 - 바로가기난이도: 브론즈 2 알고리즘: 브루트포스 알고리즘먼저 입력받은 9명의 키를 정렬하고, ${9}\\mathrm{C}{7}$ 씩 골라서 모든 경우를 탐색하면 된다. 7명이 골라졌을 때마다 키의 합을 매번 구해서 합이 100이면 해당 경우의 키들을

백준 2798번 - 바로가기난이도: 브론즈 2 알고리즘: 브루트포스 알고리즘브루트포스 알고리즘의 핵심은 for문으로 빠짐없이 노가다로 돌리기! 같다. 나는 각 숫자들을 3개씩 뽑아 sum이 M보다 작거나 같으면 result 벡터에 저장했고, 그 중에서 가장 큰 값을 구

백준 2231번 - 바로가기난이도: 브론즈 2 알고리즘: 브루트포스 알고리즘나의 원래 코드는 아래와 같았다. 정말 어이없게도 한참을 고민했다. 왜 프로그램이 종료가 안될까... 했는데 진짜 바보였다. i가 1 -> while문 내에서 i는 0으로 변함 -> i =

백준 3085번 - 바로가기난이도: 실버 4 알고리즘: 브루트포스 알고리즘사탕이 인접한 경우 위치를 바꾸고 먹을 수 있는 개수의 최댓값을 검색한다. 이 때 위치를 바꾸는 것도 가로 / 세로 방향 두 가지 경우가 있고, 먹을 수 있는 개수를 탐색할 때도 가로 / 세로 방

백준 1018번 - 바로가기난이도: 실버 5 알고리즘: 브루트포스 알고리즘$8\\times8$ 크기의 네모판으로 모든 체스판을 잘라내서, 지그재그로 'W'와 'B'의 개수를 센 다음 이 값들 중 최솟값을 고르면 된다. 지그재그로 개수를 세는 함수는 checkNum()

백준 2503번 - 바로가기난이도: 실버 5 알고리즘: 브루트포스 알고리즘아이디어 자체는 그렇게 어렵진 않았다. 모든 숫자들마다 스트라이크, 볼 개수가 같지 않은 케이스를 제거하여 마지막에 남은 숫자의 개수를 출력하면 된다. 마치 아리스토텔레스의 체를 만드는 듯한 기분

백준 1065번 - 바로가기난이도: 실버 4알고리즘: 브루트포스 알고리즘두자리 숫자는 전부 한수니까 그대로 출력하고, 세자리 숫자일 때만 등차수열인지 확인하는 과정을 거쳤다. 지금 생각해보니 굳이 % 10, /10으로 안하고 문자열로 형변환한 후에 2-1과 1-0 만

백준 7568번 - 바로가기난이도: 실버 5알고리즘: 브루트포스 알고리즘별 생각 없이 정의대로만 풀면 된다.

백준 10448번 - 바로가기난이도: 브론즈 2알고리즘: 브루트포스 알고리즘1000 이하의 삼각수를 모두 구하고, 삼중 반복문으로 세 수를 선택해 더해서 ${n}\\mathrm{C}{3}$ 가지 경우 모두를 탐색했다.

백준 1436번 - 바로가기난이도: 실버 5알고리즘: 브루트포스 알고리즘1부터 모든 문자열에 "666"이 있는지 검사하고, count를 증가시켜서 찾았다. 브루트포스 알고리즘 문제들은 신기하게 시간 초과가 날 것 같은 코드라 생각했는데도 대부분 통과가 됐다.

백준 1057번 - 바로가기난이도: 실버 3알고리즘: 브루트포스 알고리즘어마어마하게 삽질한 문제다. 처음에는 홀수 짝수로 나눠서 문제를 풀었는데, 그냥 / 2 하니까 알아서 나눠지는 것을 왜 이렇게 늦게 깨달았을까.. 게다가 부전승도 엄청 복잡하게 생각해서 if 문으로

백준 17085번 - 바로가기난이도: 실버 1알고리즘: 브루트포스 알고리즘이번 알고리즘 문제들 중 제일 킬러 문제였다. 그래도 아무 도움 없이 50분만에 풀어내서 정말 뿌듯했다. 내가 생각한 아이디어는 아래와 같다.bool 이차원 배열 선언하여 2. 가능한 모든 크기의

백준 585번 - 바로가기난이도: 브론즈 2알고리즘: 그리디 알고리즘그리디는 큰 것부터 차례대로 탐색하는 알고리즘인것 같다. 500보다 크거나 같으면 카운트 증가시키고 500 줄이고, 100보다 크거나 같으면 카운트 증가시키고 100 줄이고... 를 0이 될때까지 줄여

백준 2839번 - 바로가기난이도: 브론즈 1알고리즘: 그리디 알고리즘이전의 거스름돈 문제와 비슷한 문제지만 조금 더 함정이 있었다. 큰 것부터 없애고 싶어서 5 단위로 5 미만이 될때까지 자르고 3 단위로 자르면 답이 제대로 안나온다. 따라서 브루트포스처럼 3이 0개

백준 2828번 - 바로가기난이도: 브론즈 1알고리즘: 그리디 알고리즘사과가 바구니의 바깥에 있으면 닿을 때까지 한칸씩 움직이면 된다. 근데 처음에 푼 코드는 좌표끼리 차이를 구해서 움직였는데 왜 틀린건지 잘 모르겠다.. (아래 코드)위 코드를 보완해서 한 칸씩만 움직

백준 1789번 - 바로가기난이도: 실버 5알고리즘: 그리디 알고리즘가장 작은 숫자부터 더해지는게 가장 많이 더하는 방법일거라 생각하고 1부터 차례대로 더해보았더니 $\\frac{n(n+1)}{2}$ 단위로 개수가 올라가는 것을 발견하였다.$10=1+2+3+4$$11=

백준 4796번 - 바로가기난이도: 실버 5알고리즘: 그리디 알고리즘버스타고 친구 만나러 가는 길에 모바일로 코드를 짜서 풀었다. 그냥 단순한 몫, 나머지 연산 문제라 정말 쉽게 풀었다. 캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜

백준 11047번 - 바로가기난이도: 실버 2알고리즘: 그리디 알고리즘이 문제도 버스타고 가는 길에 풀었다. 사실상 거스름돈 문제의 일반화 버전이라.. 코드도 정말 쉽게 짰다.

백준 1541번 - 바로가기난이도: 실버 2알고리즘: 그리디 알고리즘처음에는 괄호는 한 쌍만 쳐야되는지 여러개 써도 되는지도 헷갈려서 상황 자체를 잘 이해하지 못했다. 아무 긴 수식을 써보니까 조금 이해가 됐다. $$50-35+30+20+30-25-20+20+40$$$

백준 1449번 - 바로가기난이도: 실버 3알고리즘: 그리디 알고리즘먼저 물이 새는 위치들을 벡터에 대입하고 정렬했다.첫번째 위치부터 테이프의 길이만큼 갔을 때 어느 위치까지 커버가 되는지를 찾고, 해당 범위에 포함되어 있는 구멍들을 모두 벡터에서 지웠다. 테이프에 포

백준 2138번 - 바로가기난이도: 실버 2알고리즘: 그리디 알고리즘생각보다 어려웠다. 처음에 나도 모르게 브루트포스로 접근했다가, 10개짜리만 되도 프로그램이 무한 루프에 돌아서 틀려버렸다. 도저히 안되서 질문글의 블로그를 찾아서 아이디어를 얻을 수 있었다. 전구 i

백준 11399번 - 바로가기난이도: 실버 3알고리즘: 그리디 알고리즘이전 문제(전구와 스위치)는 난이도에 비해 정말 어려웠지만, 이 문제는 난이도에 비해 너무 쉬웠다. 첫 번째 사람이 최대한 빨리 나와줘야 다른 사람들의 시간도 전체적으로 감소하므로, 가장 작은 숫자를

백준 1931번 - 바로가기난이도: 실버 2알고리즘: 그리디 알고리즘이 문제는 삽질을 너무 많이 했다. 처음에 생각한 아이디어는 끝나는 시각이 제일 짧은 것을 찾고, 그 시각이 처음 시각과 같아질 때까지 index를 증가시키는 것이였다. 근데 문제는 이걸 너무 복잡하게

백준 13904번 - 바로가기난이도: 골드 3알고리즘: 그리디 알고리즘이전 문제 (회의실 배정) 에서 삽질을 해서 그런지 이 문제는 훨씬 쉽게 풀었다. 크기가 최대 1000이라서 먼저 각 날짜별 점수를 담을 배열을 만들었다.입력을 받은 과제의 날짜에 배열 값이 비었으면

백준 1700번 - 바로가기난이도: 골드 1알고리즘: 그리디 알고리즘이 문제도 골드치고 수월하게 푼 문제였다. 콘센트 구멍으로 사용할 배열 holes와 전기용품 순서를 나타내는 배열 products를 생성하였다.먼저 빈 구멍에 전기용품들을 꽂는 과정을 거친다. 빈 구멍

백준 1780번 - 바로가기난이도: 실버 2알고리즘: 분할 정복※ 분할 정복 문제들은 재귀를 사용하기 때문에 divideConquer 라는 재귀함수를 정의하여 문제를 풀었다. 분할 정복을 처음 풀어볼 때 풀기 좋은 문제인 것 같다. 이 문제를 풀면서 딱 이런게 분할 정

백준 1629번 - 바로가기난이도: 실버 1알고리즘: 분할 정복10번이나 틀린 짜증나는 문제였다. $A, B, C$ 가 $2,147,483,647$ 이하의 자연수라서 일반적인 거듭제곱 꼴로는 문제를 풀 수가 없다. 이 문제는 블로그의 도움을 미리 받고 시작해서 아이디어

백준 1992번 - 바로가기난이도: 실버 1알고리즘: 분할 정복문제의 출력 결과를 이해하는데 시간이 좀 걸렸지만, 이해하고 나니 생각보다 쉽게 풀렸다. 문제 풀이 알고리즘은 4.1 종이의 개수 문제와 거의 비슷했다.분할 정복 함수는 먼저 (starty, startx)

백준 1074번 - 바로가기난이도: 실버 1알고리즘: 분할 정복이 문제는 숫자들의 규칙성을 파악하는 것이 관건이였다. 먼저 가로 칸들을 보면 1칸 단위로 1만큼, 2칸 단위로 4만큼, 4칸 단위로 16만큼, 8칸 단위로 64만큼 증가한다. 따라서 아래와 같은 식이 성립

백준 5904번 - 바로가기난이도: 실버 1알고리즘: 분할 정복이 문제는 내가 백준을 초반에 풀기 시작했을 때 무턱대고 덤볐다가 틀려서 6개월간 방치해두었던 문제이다. 근데 이번 스터디를 하면서 분할 정복을 배우고 푸니까 한번에 맞았다!moomooomoomoooomoo

백준 14600번 - 바로가기난이도: 골드 5알고리즘: 분할 정복"샤워실 바닥 깔기" 문제는 Large 문제와 Small 문제로 나뉘어져 있다. Large 문제는 바닥의 크기가 128까지 늘어나지만 Small 문제는 2, 4인 경우밖에 없다. Large처럼 분할 정복

백준 2571번 - 바로가기난이도: 골드 3알고리즘: 분할 정복이 문제는 분할 정복으로 접근하다가 실패하고.. 그 외에도 여러 방향으로 도전해봤지만 결국 브루트 포스 (6중 반복문)으로 풀게 되었다. 먼저 $100\\times100$ 배열을 0으로 초기화하고, 색종이

백준 1463번 - 바로가기난이도: 실버 3알고리즘: 다이나믹 프로그래밍다이나믹 프로그래밍(DP)을 접하면서 가장 처음 부딪히게 된 문제이다. 아직은 전혀 DP가 뭔지 감이 안 잡혀서 DP 블로그를 보면서 거의 똑같이 코드를 따라 써보았다. DP에는 탑다운과 바텀업 방

백준 9465번 - 바로가기난이도: 실버 2알고리즘: 다이나믹 프로그래밍이 문제도 DP 블로그의 코드를 그대로 가져와서 풀었다.Parameters col: 스티커 열 status: 0이면 왼쪽에 아무 스티커 포함x, 1이면 왼쪽 상단 스티커 포함, 2이면 왼쪽 하단 스

백준 2294번 - 바로가기난이도: 실버 1알고리즘: 다이나믹 프로그래밍이 문제도 DP 블로그의 코드를 그대로 가져와서 풀었다. 아이디어 자체가 엄청 까다로웠던 문제였다.Parameters n: 동전의 종류 (순서)k: 나타낼 가치base case 동전을 다 쓰고난 후

백준 2193번 - 바로가기난이도: 실버 3알고리즘: 다이나믹 프로그래밍Parameters n: 이진수의 길이digit: 첫번째 자릿수base case 이진수 길이가 1일 때 첫번째 자릿수가 1이면 0 리턴, 0이면 1 리턴Logic 이친수는 첫번째 자릿수가 0일 경우

백준 1904번 - 바로가기난이도: 실버 3알고리즘: 다이나믹 프로그래밍이제부터 나오는 문제들은 대부분 앞의 $4$문제 ($5.1 \\sim 5.4$) 와 코드가 거의 비슷하다. DP 1 문제들은 거의 동일한 유형이라 보면 된다.Logic n=$1$부터 $5$까지만 나

백준 11726번 - 바로가기난이도: 실버 3알고리즘: 다이나믹 프로그래밍Logic 이 문제도 1 또는 2로 분할하여 더하는 문제기 때문에 앞의 5.5번 문제와 로직이 완전히 동일하다. 따라서 5.5번에서 나머지만 10007로 변경하면 된다.

백준 11727번 - 바로가기난이도: 실버 3알고리즘: 다이나믹 프로그래밍Logic 이 문제도 1 또는 2로 분할하여 더하는 문제지만, 2로 분할할때 가로 세로 두 방향이 존재한다. 따라서 앞의 5.6번 2\*n 타일링 문제에서 2로 분할하는 경우에 곱하기 2만 해주면

백준 1699번 - 바로가기난이도: 실버 3알고리즘: 다이나믹 프로그래밍이 문제는 5.3 동전 2 문제에서 동전 값들이 제곱수로 바뀐 문제다. 이 때 k의 상한선이 10만 즉, $316<\\sqrt{100000} <317$ 이므로 배열 squares의 크기는

백준 1890번 - 바로가기난이도: 실버 2알고리즘: 다이나믹 프로그래밍이 문제도 Moo 게임과 같이 수개월간 틀렸었던 문제다. 예전에 풀었을 때는 DP의 개념을 몰라서 메모이제이션을 하지 않아 <span style="color:Parameters r: 행 좌표