참.. 한칸 마다 '가로 or 세로' 두가지 선택지가 있다고 비트마스킹이라니..이런 유형 정말 쉽지 않다 ㅋㅋ/*[백준]14391, 종이 조각[문제파악]영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다.행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다.길이가 N인 조각은 N자리 수로 나타낼 수 있다.가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.아래 그림은 4×4 크기의 종이를 자른 한 가지..

초기 문제 분석 괜찮게 시작!('문제분석' → 이 부분은 확실히 많이 푸니까 '아 이건 어떻게 풀어야겠다' 생각나는게 좋았음!)DFS vs 비트마스킹 이었는데 좀 더 약한 방법으로 풀어보자 했음그래도 어려웠다문제[백준]2800, 괄호제거[문제파악]어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.이 수식은 괄호가 올바르게 쳐져 있다.예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.예를들어 (2+(2*2)+2)에서 괄호를 ..

백트래킹은 수학적 사고를 많이 요하는듯...그래도 예전과 달리 이해는 할 수 있으니까 조금씩 늘고는 있구나~ 싶다다행!package Algorithm_2025;/*[백준]9663, N-Queen[문제파악]N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.[입력]첫째 줄에 N이 주어진다. (1 ≤ N - 이것도 그냥 수학적 방법이다- 예를들어 시작점이 (0, 0)이라고 하면 대각선의 점들은 ~, (-1, -1), (1, 1), ~가 된다 이 말인 즉, Math.abs(-1-(1)) = Math.abs(1-(-1))은 항상 같다는 명제가 성립한다 (대각선을 구하는 것과 같음)- 그러므로?..

최근 문제를 풀 일이 있었는데 내가 최소공약수, 최대공배수를 어떻게 구하는지 모르더라;;노트 펴놓고 구하라고 하면 습관대로 구하는데 코드로 어케 짜야하는지 감을 못잡음..야매로 풀긴 풀었는데 이건 아니다 싶어서 끝나고 공부해보니 LCM, GCD라는 개념이 있더라공부하면서 정리한 시간을 가지면서 문제 하나를 풀어서 정리해둔다배울게 짱많음!문제/*[백준]11688, 최소공배수 찾기[문제파악]세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다.[입력]첫째 줄에 a, b, L이 주어진다. (1 ≤ a, b ≤ 106, 1 ≤ L ≤ 1012)[출력]첫째 줄에 c를 출력한다. 만약, 가..

진짜 트리만큼은 친해지기 너무 어려운 것 같다그럼에도 이번에 느꼈다다른건 그래도 어느정도 풀 수 있거나 시도라도 해볼 수 있지만 트리는 그게 안된다는 것을그러니까 당분간은 트리만 주구장창 파는거다 ^^더 이상 도망 못감 ㅇㅇpackage Algorithm_2025;/*[백준]5639, 이진 검색 트리[문제파악]이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다.후위 순회 (왼쪽-오른쪽..

와..! 1년만에 재도전해서 성공!package Algorithm_2025;/*[백준]16923, 다음 다양한 단어[문제파악]다양한 단어란 모두 다른 알파벳 소문자로만 이루어진 단어를 의미한다.예를 들어, "codeplus", "coding", "algorithm"은 다양한 단어, "baekjoon", "startlink"는 다양한 단어가 아니다.다양한 단어 S가 주어졌을 때, 사전 순으로 S의 바로 다음에 오는 다양한 단어를 구해보자.[입력]첫째 줄에 길이가 26보다 작거나 같은 다양한 단어 S가 주어진다.[출력]사전 순으로 S의 바로 다음에 오는 다양한 단어를 출력한다. 바로 다음에 오는 단어가 없는 경우에는 -1을 출력한다.[구현방법]- 일단 철자들을 하나씩 검사해서 사용하지 않은 철자가 있으면 앞..

우와.. 몇 년전만해도 '이걸 어케 풀어하는걸' 한큐에 해냈당다만 초중반에 제대로 풀고 있나 방향은 확인했음 지난 몇년 동안 막연히 목표로만 잡아뒀던 티어에도 드디어 등판...감개무량하네 정진하자..문제에 대한 고찰/*[백준]20057, 마법사 상어와 토네이도[문제파악]마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다.위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다.토네이도는 한 번에 한 칸 이동한다.다음은 N = 7인 경우 토네이도의 이동이다.토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 ..

나한테는 발상의 전환이 필요했던 문제도형을 통째로 돌릴 생각만 했는데?너무 어렵더라고요.. 대체 어떻게 구현해야하나 싶고 그래서 찾아봤더니?이 방법이 전혀 아니고 List를 만들어서 좌표를 역순으로 따라가며 돌릴 생각은 대체 누가 한걸까...그저 신기함../*[백준]15685, 드래곤 커브[문제파악]드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다.좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다.아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝..

내가 평소에 얼마나 쓸데없이 복잡하게 생각하는지 알 수 있었던 문제음.. 제대로 찾아온 것 같군당분간 구현 + 그리디 문제 열심히 풀면 되겠다문제 분석/*[백준]1339, 단어수학[문제파악]민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다.이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다.같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437..

패턴을 못찾아서... 세상 복잡한 풀이 시도하던 문제(단 세줄로 끝나다니 현타 띵!) 당분간은 시뮬레이션 & 구현, 그리디에 집중해야할 것 같다패턴 파악, 추상화가 아직 약한듯(대체 그럼 강한게 뭔ㄷ..읍읍)package Algorithm_2025;/*[백준]1018, 체스판 다시 칠하기[문제파악]지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다.어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다.지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다..

알고보면 되게 쉬운 문제였는데 단순화가 안되어서 애먹은 문제그간 알고리즘 풀면서 막힌거, 오류들 확인하고 공부했던거 패턴 분석 했는데 아래 것들이 좀 부족한듯 싶다- 일단 그리디, DP (걍 어려움;;)- 개념적 단순화 필요 (넘 어렵게 생각함 + 간단한 예제 손으로 직접 다 써보기)- 구조적 성질 파악부터 하기 (문제 안에 숨어있는 규칙, 제약, 불변성, 대칭성 발견해서 풀이 단순화하기) Deque에 막힌 이후로 거의 2주 가량 Deque만 풀었으니까 이젠 파트를 좀 바꿔서 약한 부분 보완해봐야겠다package Algorithm_2025;/*[백준]1464, 뒤집기 3[문제파악]세준이는 어떤 문자열 S를 뒤집으려고 한다. 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자.i만큼을 뒤집는다는 소리는 ..

Deque 동작 방식 여태 Queue랑 똑같은줄 알았더니 전혀 아니었다;;;Deque의 push, pop은 Stack과 똑같이 동작하되 맨 뒤가 아닌 맨 앞에서 이뤄진다...이걸 몰라서 압축(C)하는 과정에서 틀렸던 것! 즉, Deque는 명령어에 따라 Stack처럼 쓸 수도, Queue처럼 쓸 수도 있는 것이다!(주의해야함)push, pop - Stack처럼 사용add, poll - Queue처럼 사용Stack 동작 방식import java.util.ArrayDeque;import java.util.Deque;import java.util.Stack;public class Test { public static void main(String[] args) { Stack temp = ne..

이번주 내내 덱 문제만 풀면서 LinkedList가 무적이라고 생각했는데 아님 (파이썬... 보고 싶어 ㅠ)특히 깜빡 잘못 생각한 포인트는 LinkedList는 앞, 뒤 노드에 해당하는 주솟값이 들어있으니까 remove하면 O(1)이겠다!바보냐..? 주솟값이 있댔지 인덱스가 아니잖아그러니 5번째 인덱스를 remove를 하려면, 1번부터 5번 인덱스까지 순차적으로 타고 들어가야한다각각의 노드들은 내 다음 노드 주소만 알고 있을 뿐, 5번 인덱스의 정확한 주소를 알고 있진 않으니까..그렇기 때문에 O(N)이 걸림헷갈리는거 보아하니 개념 한번 정리하고 가야겠다package Algorithm_2025;/*[백준]28066, 타노스는 요세푸스가 밉다[문제파악]N마리의 청설모가 1번부터 N번까지 순서대로 시계 방향..

요즘 덱 문제를 풀일이 있었는데 이걸 풀면서 알게된 점이 하나 있다바로 내가 인덱스를 다루는 문제에서 은근 약하다는 것!그래서 당분간은 난이도 낮은 덱 관련 문제만 풀면서 감을 익히기로 했다 그리고 또 하나 배운게 자료구조 개념을 정확히 이해하고 써야한다는 뻔한 것을 절실히 체감했다단순히 첫 풀이가 for문이 4개나 되길래 '이렇게 비효율적이라고...? 줄이자!' 싶었다근데 LinkedList에 직접 구현하는 방식으로 바꾸니, LinkedList는 순차탐색 방식이라 더 비효율적이었다!!(LinkedList는 오히려 최악의 경우 O(N^2)이 걸리기 때문에, 배열을 사용해 O(1) 동안 구해버리는게 더 나았다!!)단순히 반복문 갯수를 줄인다고 능사가 아님을 깨달았다휴 배울게 진짜 많다문제 풀이 고민/*[백..

슬라이딩 윈도우를 온전히 이해하고 풀었던 첫 문제물론 아이디어를 한번에 도출해내진 못했고 구현하고도 놓친 부분이 세개 있었지만...할수록 늘테니까 뭐...package Algorithm_2025;/*[백준]22862, 가장 긴 짝수 연속한 부분 수열 (large)[문제파악]길이가 N인 수열 S가 있다.수열 S는 1 이상인 정수로 이루어져 있다.수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제를 할 수 있다.예를 들어, 수열 S가 다음과 같이 구성되어 있다고 가정하자.수열 S : 1 2 3 4 5 6 7 8수열 S에서 4번째에 있는 4를 지운다고 하면 아래와 같다.수열 S : 1 2 3 5 6 7 8수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 ..

순서 정해서 차근차근 풀면 풀만했던 문제근데 아이디어를 못 떠올렸음 핵심은 두가지1) BFS로 각 노드끼리의 최단 거리를 모두 구해둔다2) 순열로 조합을 구해서 해당 노드 순서대로 최소 거리를 구한다 내가 간과한 것은 두가지1) 챙겨야할 물건(=X)가 최대 5개라는 것은 '없을 수도 있다'는 것2) 방문처리는 Q에 집어넣을 때 해야 중복되는 것들이 Q에 또 들어가는 것을 방지할 수 있다는 것 간과한 2번이 메모리 초과의 원인이었다 (방문처리를 잘해야함)package Algorithm_2025;/*[백준]17244, 아맞다우산[문제파악]경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다.필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다."아 맞다 우산!!!"..

이 문제는 와 세상 어렵다!! 이 정도는 아니다근데 한번에 못 풀었음;; (처음엔 탐색 문제 아닌가? 이러면서 헤맸음..) 문제를 한번에 풀지 못한 이유는 크게 세가지1) 너무 어렵게 생각해서 (사실 자리 스왑만 하면 되는 문제다)2) 큰 문제를 작게 나눌줄 몰라서 (top-down, down-top 두 방향으로 ???가 있는 행까지 탐색하면 된다)3) 나누더라도 어떻게 나눠야할지 몰라서이다 알고리즘 풀다가 막혔거나, 어려웠거나, 찜찜하면 포스팅을 하곤하는데 오늘은 애매해서 포스팅을 남긴다경험의 부재인듯한데 이건 뭐 더 다양한 문제풀면 됨 ㅇㅇ뭐 어쩌겄어 가서 더 풀어package Algorithm_2025;/*[백준]2469, 사다리타기[문제파악]k명의 참가자들이 사다리 타기를 통하여 어떤 순서를 결정..

아직 고난이도 구현 문제를 풀면 뒷심이 풀려버리는 이슈가 있다 ㅠ그리고 좀 더 치밀한 단계를 세워서 푸는 연습이 좀 더 필요함하나씩 놓쳐가지고 통과가 안된다이번의 경우엔 10회를 넘는 경우 -1을 출력해야하는데 이걸 깜빡해서 64%에서 계속 막힘../*[백준]13460, 구슬 탈출 2[문제파악]스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다.구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다.가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다.빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가..

애매하게 알아서 애매하게 어려웠던 문제에라토스테네스의 체로 소수를 구하고, 투포인터로 범위를 이동해가며 풀면되는 문제다다만 일반적인 투포인터 문제랑 살짝 다르게 모든 경우의 수를 다 찾아야하기 때문에 이동 방향이 고정이다start와 end 모두 왼쪽으로만 이동한다이 두가지 사실 모두 애매하게 알아서 애매하게 어려웠음...이해하고 보면 쉬운데... 다만 일반적으로 O(N^2)이 아닌 O(N log log N)가 걸리는 에라토스테네스의 체 공식은 외워둘법한 것 같다크게 어려울 것은 없고(?!), 그냥 한번 계산한 것들은 그 이후 배수들까지 미리 처리해버리면 된다(N = 1,000,000 기준으로 O(N^2)은 약 1조(10¹²)번 연산, O(N log log N)는 약 2천만(2×10⁷)번 연산으로 꽤 유의..

오늘 내가 간과한 점은 Map을 List로 전환할 부드러운 사고를 못한 것정렬을 할 때 여러 조건부가 걸린 상황이라면?Map.Entry 써가지고 List로 만든 뒤, sort로 조건부를 할당하면 된다는 것이다...(이렇게 쉬운걸!!!)package Algorithm_2025;/*[백준]20920, 영단어 암기는 괴로워[문제파악]화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다.그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다.화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.0) 자주 나오는 단어일수록 앞에 배치한다.1) 해당 단어의 길이가 길수록 앞에 배치한다.2) 알파벳 사전 순으로 앞에 있는 단..