'Algorithm' 카테고리의 글 목록

[백준] 2239 - 스도쿠

2239. 스도쿠 풀이난이도: Gold IV문제 주소: https://www.acmicpc.net/problem/2239문제 풀이이 문제는 9x9 보드에서 빈칸(0)으로 주어진 부분을 1부터 9까지의 숫자로 규칙에 맞게 채워넣어야 하는 문제이다.일단 1부터 9까지 하나하나 다 넣어보는 백트래킹 방식을 사용해야지라고는 마음 먹었는데문제는 0에 지금 이숫자를 넣을수 있는지 를 체크하는거보다 일단 다 채우고 수도쿠가 성립하는지 체크하는 방식으로 갔더니 코드가 끝나질 않아서 풀이 방식을 지금 이 칸에 이 숫자를 넣어도 되는지 체크하는 방식으로 갔다 bool solve(int seq){ if (seq == 81) return true; int r = seq / 9; int c = seq % 9; ..

2026. 4. 14.

[백준] 5525 - IOIOI

5525. IOIOI 풀이난이도: Silver I문제 주소: https://www.acmicpc.net/problem/5525문제 풀이이 문제는 I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성해야 하는 문제이다.문제를 처음 봤을때는 생각보다 어려워 보여서 풀이를 고민하는데 시간이 걸렸다뭔가 DP를 써야할거 같이 생긴거 같아서 이쪽을 고민해보다가 바로 아닌거같아서 넘기고 다음에는 n에 해당하는 길이의 문자열이 존재하는지 문자열 전체를 순회하는 식으로 가야할까 했지만 시간복잡도 때문에 넘기고 떠올린게 투포인터였다 while (ed = m) break; if (str[ed + 1] == 'O' && str[ed + 2] ..

2026. 4. 12.

[백준] 12015 - 가장 긴 증가하는 부분 수열2

12015. 가장 긴 증가하는 부분 수열 2 풀이난이도: Gold II문제 주소: https://www.acmicpc.net/problem/12015문제 풀이이 문제는 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS)의 길이를 구해야 하는 문제이다.처음에는 이전 LIS문제처럼 이중 반복문을 사용한 동적 계획법(DP) 을 생각했지만 배열의 크기가 최대 1,000,000까지 주어지기 때문에 일반적인 O(N^2) 방식으로 코드를 작성하면 안돼겠다 싶었다대충 배열 크기상 이분탐색을 사용해야겠다고는 싶었는데 이분탐색을 어떻게 활용해야할지 처음에는 도저히 감이 잡히지 않았다한시간쯤 고민이 넘어가닌까 이건 힌트가 필요하다 싶어서 ai를 이용해 힌트만을 받아봤다그렇게 얻은 힌트는 최장 길이 수열의 원소는 찾을..

2026. 4. 8.

[백준] 11404 - 플로이드

11404. 플로이드 풀이난이도: Gold IV문제 주소: https://www.acmicpc.net/problem/11404문제 풀이이 문제는 제목에서도 나와있듯이 플로이드 알고리즘을 연습해 보기위한 문제이다for (int i = 0; i > a >> b >> c; city[a][b] = min(city[a][b], c);}for (int i = 1 ; i 처음에는 2차원 배열 city의 모든 값을 INT_MAX로 초기화했다. 버스 노선의 정보를 입력받을 때 주의해야 할 점은 시작 도시와 도착 도시를 연결하는 노선이 하나가 아닐 수 있다는 것이다. 따라서 중복되는 노선이 주어질 경우 min 함수를 사용하여 더 적은 비용만 배열에 저장되도록 처리하고 자기 자신으로 가는 비용은 모두 0으로 설정해 두..

2026. 4. 3.

[백준] 9663 N－Queen

9663. N－Queen 풀이난이도: Gold IV문제 주소: https://www.acmicpc.net/problem/9663문제 풀이이 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. 1 이상 15 미만의 자연수 N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성해야 한다.처음에는 2차원 배열과 재귀 함수를 활용하여 모든 방향을 탐색하는 방식으로 코드를 작성했다. bool check(int r, int c){ bool check = true; for (int i = 1; i N || y N) continue; if (chess[y][x] == 1) return false; } } return..

2026. 4. 1.

[백준] 10814 - 나이순 정렬

10814. 나이순 정렬 풀이난이도: Silver V문제 주소: https://www.acmicpc.net/problem/10814문제 풀이이 문제는 회원들의 정보를 나이 오름차순으로 나이가 같으면 가입한 순서대로 정렬하는 문제다.문제에서 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서를 만족시키기 위해 입력된 데이터의 상대적 순서를 유지하는 Stable Sort가 필요하다.그리고 바로 정렬에 넣으면 나이순 정렬이 완료 된 후 이름의 사전 순 정렬이 발생하기 때문에 사전 순 정렬이 발생하지 않도록 나이만으로 정렬하게 하는 비교함수를 작성했다 bool compair(pair x, pair y){ return x.first stable sort는 나이가 같은 요소들의 경우 입력된 순서 를 정렬 후에..

2026. 4. 1.

[백준] 10942 - 팰린드롬?

10942. 팰린드롬？ 풀이난이도: Gold IV문제 주소: https://www.acmicpc.net/problem/10942문제 풀이이 문제는 칠판에 적힌 자연수 N개에 대해 S번째 수부터 E번째까지 수가 팰린드롬을 이루는지 묻는 질문을 총 M번 처리해야 하는 문제이다. 처음에는 재귀 함수와 메모이제이션을 활용한 Top-down DP 방식으로 코드를 작성했다. int palindrom(int s, int e){ if (s >= e) return 1; if (recall[s][e] != 0) return recall[s][e]; if (num[s] == num[e]) return recall[s][e] = palindrom(s + 1, e - 1); else return r..

2026. 3. 23.

[백준] 2166 - 다각형의 면적 풀이

2166. 다각형의 면적 풀이난이도: Gold V문제 주소: https://www.acmicpc.net/problem/2166문제 풀이이 문제는 2차원 평면상에 주어진 N개의 점으로 이루어진 다각형의 면적을 구하는 문제이다. 좌표값은 절댓값이 100,000을 넘지 않는 정수로 주어진다.이 문제는 신발끈 공식을 사용하면 풀 수 있지만 공식을 모른다면 어려울거 같다 주의할 점은 좌표 범위가 굉장히 크기 때문에 범위가 작은 자료형을 사용하면 틀릴수도 있을거 같아서 이를 방지하기 위해 계산에 사용할 변수 xy와 yx를 long double 자료형으로 선언하여 소수점 연산의 정확도를 높였다그리고 신발끈 공식을 코드에 적용할 때 마지막 점과 첫 번째 점이 다시 교차해서 곱해져야 하는데 이 부분을 처리하기 위해 배열..

2026. 3. 22.

[백준] 12851 - 숨바꼭질2

12851. 숨바꼭질 2 풀이난이도: Gold IV문제 주소: https://www.acmicpc.net/problem/12851문제 풀이이 문제는 수빈이가 동생을 찾는 가장 빠른 시간과 그 방법의 수를 구하는 BFS 문제이지만 기존의 단일 최단 경로 찾기처럼 풀면 문제가 발생할 수 있는 문제이다. 처음에는 다음 구조로 코드를 작성했다. for (int next : next_pos) { if (next >= 0 && next next_time) { anw = {next_time, 1}; } else if (anw.first == next_time) { anw.second++; ..

2026. 3. 19.

[백준] 12865 - 평범한 배낭

12865. 평범한 배낭 풀이난이도: Gold V문제 주소: https://www.acmicpc.net/problem/12865문제 풀이이 문제는 DP 문제이지만 루프 순서와 기존의 실버 난이도 DP풀던거처럼 풀면 문제가 발생할 수 있는 문제이다.처음에는 다음 구조로 코드를를 작성했다vector > V;for (int i = 0; i > w >> v; V.push_back(make_pair(w, v));}for (int i = 1; i = 0) { dp[i] = max(dp[i], dp[i - V[j].first] + V[j].second); } }} 이런 구조로 문제를 풀게되면 시간 복잡도는 문제가 없고 예제도 통과를 해서 문제가 없을줄 알았지만 이렇게 풀게 ..

2026. 3. 17.

[백준] 11053 - 가장 긴 증가하는 부분 수열

11053. 가장 긴 증가하는 부분 수열 풀이난이도: Silver II문제 주소: https://www.acmicpc.net/problem/11053문제 풀이가장 긴 증가하는 부분 수열(LIS})을 구하는 전형적인 DP문제다수열의 크기 N이 최대 1,000이기 때문에 O(N^2) 으로 비교적 널널하게 해결 가능하다풀이방식각 원소 그 자체만으로도 길이 1인 증가하는 부분 수열이 되므로 dp 배열의 모든 값을 1로 채운다이중 반복문으로 현재 위치 i를 기준으로 0부터 i-1까지의 이전 원소들을 j로 탐색한다만약 num[j] 전체 dp 배열 중 가장 큰 값이 수열의 최대 길이라 마지막에 정렬을 이용해 최댓값을 찾았다문제 자체는 정말 쉬운데 정렬을 안한상태로 dp[n - 1]을 출력했다가 한번 틀렸다....이런..

2026. 3. 13.

[백준] 1654 - 랜선 자르기

1654. 랜선 자르기 풀이난이도: Silver II문제 주소: https://www.acmicpc.net/problem/1654문제 풀이이분 탐색을 활용하는 문제다주어지는 랜선의 길이는 최대 2^31 - 1로 굉장히 길고 필요한 개수 N도 1,000,000이나 되기 때문에 단순히 하나씩 길이를 조절하며 답을 찾는 건 시간 초과가 나기 때문에 이분탐색을 이용해야한다1부터 가장 긴 랜선의 길이 사이에서 중간값인 mid를 정하고 그 길이로 잘랐을 때 나오는 랜선 개수가 N보다 크거나 같은지 확인하는 식이다. 만약 개수가 충분하다면 길이를 더 늘려서 최댓값을 찾아보고 부족하다면 길이를 줄여가며 범위를 좁히면 된다.이분탐색 문제를 풀어본적이 있으면 굉장히 쉬운 문제인데 너무 오랜만에 이분탐색 구현하는거라 생각보..