알고리즘
스도쿠 문제 풀이 정리 (LeetCode 36 & 37)
스도쿠 문제 풀이 정리 (LeetCode 36 & 37)
2025.08.311. Valid Sudoku (문제 36)문제9×9 스도쿠 보드가 주어짐.빈 칸은 '.'로 표시.규칙:각 행(row) 은 1~9 중복 없음각 열(col) 은 1~9 중복 없음각 3×3 박스도 중복 없음아직 완성되지 않아도, 현재 보드가 유효한지 검사.풀이 아이디어행, 열, 박스별로 이미 등장한 숫자를 기록.중복이 나타나면 false, 끝까지 없으면 true.Set을 활용하면 중복 검사 로직이 매우 간단해짐.Java 코드 (Set 버전)import java.util.*;class Solution { public boolean isValidSudoku(char[][] board) { List> rows = new ArrayList(); List> cols = new ArrayL..
프로그래머스 2개 이하로 다른 비트
프로그래머스 2개 이하로 다른 비트
2025.08.17최근에 흥미로운 문제를 접했습니다. 바로 "2개 이하로 다른 비트" 문제입니다. 단순해 보이지만, 무작정 풀면 시간 초과에 빠질 수밖에 없는 유형이죠. 이번 글에서는 문제 접근 과정을 단계별로 설명하고, 규칙을 정리한 뒤 자바(Java) 코드로 구현한 방법을 공유하겠습니다.문제 요약주어진 숫자 N에 대해, 자신보다 큰 수 중에서 비트가 2개 이하만 다른 수를 찾아야 합니다.입력 범위: 1 ≤ N ≤ 10^15배열 numbers[]가 주어지고, 각 원소에 대해 조건을 만족하는 최소 수를 구해야 합니다.첫 번째 접근: 브루트포스 방식처음에는 단순하게 생각했습니다.숫자 N을 이진수로 변환한다.N+1, N+2, ... 이렇게 하나씩 증가시키면서이진수 형태로 비교 → 다른 비트 개수가 2개 이하라면 return...
LeetCode 808. Soup Servings (확률 DP 문제 풀이)
LeetCode 808. Soup Servings (확률 DP 문제 풀이)
2025.08.101. 문제 소개두 종류의 수프 A와 B가 있고, 처음에는 각각 n mL씩 들어 있습니다.게임은 다음 규칙으로 진행됩니다.매 턴, 4가지 동작 중 하나를 확률 0.25로 선택:선택A 감소량B 감소량11000275253505042575규칙A 또는 B 중 하나라도 0 이하가 되면 게임 즉시 종료줄이려는 양이 남은 양보다 많으면, 남은 만큼만 줄임A가 먼저 소진될 확률 + A와 B가 동시에 소진될 확률의 절반을 반환해야 함정답 오차 허용: 10^-5 이내2. 종료 상태 정의게임이 끝나는 경우는 3가지입니다.A 먼저 소진 → 성공 → 확률 1.0B 먼저 소진 → 실패 → 확률 0.0A, B 동시에 소진 → 절반만 성공 인정 → 확률 0.5이를 코드로 표현하면:if (a 3. 상태 공간 축소 — 25 단위로 변환문..
[코딩 테스트] LeetCode - Count Hills and Valleys in an Array (Java)
[코딩 테스트] LeetCode - Count Hills and Valleys in an Array (Java)
2025.07.27문제 링크: https://leetcode.com/problems/count-hills-and-valleys-in-an-array난이도: Easy ~ Medium태그: 배열, 시뮬레이션, 패턴 인식문제 설명정수 배열 nums가 주어질 때, "Hill(봉우리)"과 "Valley(골짜기)"의 개수를 구하라는 문제다.Hill: 현재 값이 양 옆 값보다 클 때Valley: 현재 값이 양 옆 값보다 작을 때조건: 연속된 동일 값들은 하나의 구간으로 간주해야 한다.예시Input: [2,4,1,6,5]Output: 3 초안 풀이 (좌우 확장 비교 방식)처음엔 다음과 같은 방식으로 풀었다:중복 값은 무시현재 인덱스를 기준으로 왼쪽과 오른쪽으로 같은 값을 건너뛰며 비교현재 값이 양쪽보다 크거나 작으면 Hill 또는 Va..
다양한 정렬 알고리즘 구현 및 성능 비교
다양한 정렬 알고리즘 구현 및 성능 비교
2025.04.28이번 포스팅에서는 대표적인 정렬 알고리즘을 C 언어로 직접 구현하고,100만 개 데이터를 기준으로 수행 시간을 측정해 비교해보았습니다. 실험 환경데이터 개수: 1,000,000개 (난수로 생성)측정 방법: clock() 함수를 이용해 실행 시간 계산 구현한 정렬 알고리즘각 정렬 알고리즘은 별도로 함수를 구현해 테스트했습니다.1. 선택 정렬 (Selection Sort)모든 요소를 비교하여 가장 작은 값을 선택해 앞으로 보냄시간 복잡도: O(N²)void selection_sort(int list[], int n) { int i, j, least, tmp; for (i = 0; i 2. 삽입 정렬 (Insertion Sort)이미 정렬된 구간에 새로운 데이터를 삽입하는 방식시간 복잡도: O(..
Zigzag Conversion
Zigzag Conversion
2025.04.20문제 https://leetcode.com/problems/zigzag-conversion/description/The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)P A H NA P L S I I GY I RAnd then read line by line: "PAHNAPLSIIGYIR"Write the code that will take a string and make this conversion given a number of ro..
BOJ 17612 쇼핑몰
BOJ 17612 쇼핑몰
2025.04.07개요이 문제는 우선순위 큐를 사용하는 문제지만, 정렬 방법에 대해 이해하고 있어야 하고 무엇보다 문제에서 주어진 요구사항을 동적으로 처리하는것보다 사전에 전처리하여 값을 모두 저장 한뒤 문제 요구사항에 맞게 풀어야 했었습니다. 처음에는 while 문으로 계속 돌면서 입력 받는대로 동적으로 값을 처리 해주었습니다. 결과적으로 꼬였습니다.그래서, k개 즉 카운터라고 볼 수 있는 k개에 쇼핑 카트를 모두 대기하는 값을 pq에 담게 되었습니다.그림그림을 보게 되면 어쨋든, 상품들이 1초에 하나씩 계산이 될텐데 더 적은 상품에 대해서 카운터에 배정되게 됩니다. 상품의 개수가 같다면 카운트가 더 적은 애한테 우선 할당하게 되는데 그게 인입하는 과정에서 수행하게 됩니다. 반대로, 나갈때도 마찬가지로 기본적인 더 적은..
kakao_n진수 게임
kakao_n진수 게임
2025.01.26N진수 게임튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다.숫자를 0부터 시작해서 차례대로 말한다. 첫 번째 사람은 0, 두 번째 사람은 1, … 열 번째 사람은 9를 말한다.10 이상의 숫자부터는 한 자리씩 끊어서 말한다. 즉 열한 번째 사람은 10의 첫 자리인 1, 열두 번째 사람은 둘째 자리인 0을 말한다.이렇게 게임을 진행할 경우,0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, …순으로 숫자를 말하면 된다.한편 코딩 동아리 일원들은 컴퓨터를 다루는 사람답게 이진수로 이 게임을 진행하기도 하는데, 이 경우에는0, 1, 1, 0..
DAG, 위상정렬(feat. BOJ. 줄세우기)
DAG, 위상정렬(feat. BOJ. 줄세우기)
2024.08.18위상정렬위상정렬(Topological Sorting)은 방향성 비순환 그래프(Directed Acyclic Graph, DAG)의 노드들을 선형으로 정렬하는 알고리즘입니다. 이 정렬은 그래프의 모든 간선이 방향성에 맞도록 순서대로 나열되도록 합니다.DAG = 사이클이 없는 방향 있는 그래프를 의미합니다. 선행그래프 구조를 가지고 있습니다.DAG 에서 할 수 있는 알고리즘은 위상정렬 알고리즘이 활용됩니다. BFS 알고리즘을 응용해서 구현할 수 있습니다.위상정렬에서 주목해서 봐야할 것은 순서와 큐 입니다. 이 상태에서 인디그리가 0인 상태인 얘들을 큐에 넣어줍니다. 큐 : 1,2,3 이 존재하고 (왜냐하면 1,2,3 노드로 들어오는 화살표가 0) 여기서 하나씩 빼면서 BFS 과정을 거쳐주게 됩니다.순서 :..
알고리즘 펜윅 트리
알고리즘 펜윅 트리
2024.08.11시작펜윅 트리, 세그먼트 트리에서 변형된 형태입니다. 대표적으로 구간 합 알고리즘을 O(N)보다 빠르게 풀고자 할 때 펜윅 트리를 사용합니다.일반적으로 구간 합을 구할 때 O(N) 정도의 시간이 걸립니다.펜윅 트리(BIT = Binary Indexed Tree) 이용하게 되면 O(logN) 으로 시간 복잡도를 감소 시킬 수 있습니다. 전체 노드의 부분 합 즉, 0~K 합을 구해 두게 되면 원하는 구간 합 S~D를 구하는 것이 가능해 집니다. (Start ~ Destination)O(logN) 의 수행시간 만으로 구간합을 구할 수 있게 됩니다. 구간 합 외에도 같은 원리로 업데이트도 수행할 수 있게 됩니다. 펜윅트리 구조일반적으로 펜윅 트리 구조는 아래와 같이 세그먼트 트리를 응용한 형태로 구조를 정형화..
35. Search Insert Position
35. Search Insert Position
2024.06.07문제 정의 주어진 정렬된 배열에서 목표 값을 찾고, 찾지 못하면 목표 값이 삽입될 인덱스를 반환하는 문제입니다. 이 문제는 O(log n) 시간 복잡도로 해결해야 합니다. https://leetcode.com/problems/search-insert-position/description/Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity...
979. Distribute Coins in Binary Tree
979. Distribute Coins in Binary Tree
2024.05.19You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.Return the minimum number of moves required to make every node have exactly one coin.Example 1..