iyungui
aboutpostsalgorithms

Algorithm Notes

Problem solving approaches and code implementations.
Documenting the journey through various algorithm challenges.

17 Problems Solved0 Difficulty Levels0 Topics Covered

Difficulty

Topics

All

17 Problems

(중복순열 3가지 방법) 이모티콘 할인행사 - Swift 문제풀이

(중복순열 3가지 방법) 이모티콘 할인행사 - Swift 문제풀이

문제 링크 카카오 코딩테스트: 이모티콘 할인행사 문제 분석 먼저 이 문제는 중복순열을 활용해야 하는 문제로서, 각 이모티콘마다 rates 적용한 경우의 수에서, 문제에 제시된 두 목표일 때의, (이모티콘 플러스 서비스 가입 수와 이모티콘 매출액) 값을 갱신시켜나가야 하는 문제다. 이 문제의 경우, 중복순열을 여러가지 방법으로 구현해보는 연습을 해보았다. 특히 비트마스킹의 경우, 지금까지 2^n 가지 경우의 수 문제. 즉 2가지 선택을 n번 반복하는 경우에 대해서, 적용하는 문제에만 적용해왔는데, 4^n 의 경우에는 1비트가 아니라…

Algorithm
주난의 난 - Swift 문제풀이

주난의 난 - Swift 문제풀이

문제 링크 백준: 주난의 난 문제 분석 이 문제는 가중치가 같을 때 최단거리 탐색에 사용하는, 일반적인 bfs와는 조금 다르다. 왜냐하면 “0”을 만나면, 해당 queue를 계속 진행해야 하고 그 이외에는 다음 탐색 사이클에서, 새로운 시작점으로 저장해두어야 한다. 즉 queue가 두 개 필요하다. 메인 큐: 현재 탐색하고자 하는 위치 담은 큐 배열. 만약 0이 있으면 그 다음 위치도 계속 탐색하게 됨. temp 큐: 다음 사이클에서 메인 큐 시작점들 담은 배열 (이번 점프에서 쓰러트린 친구들의 위치를 담았다고 볼 수 있다.) 그…

Algorithm
표현 가능한 이진트리 - Swift 문제풀이

표현 가능한 이진트리 - Swift 문제풀이

문제 링크 카카오 코딩테스트: 표현 가능한 이진트리 문제 분석 이 문제는 구현 문제 먼저 십진수를 이진수로 변환한다. 포화이진트리의 정점의 개수는 2^k - 1 이다. 만약 이진수의 자릿수가 6이고, 포화이진트리는 7이라면, 1개의 0을 이진수 문자열에 붙여준다. 포화이진트리를 보면, 루트노드는 항상 왼쪽 서브트리의 루트노드와 오른쪽 서브트리의 루트노드의 딱 중간이다. 그렇기 때문에, 재귀함수로 f(start, end) 이분탐색을 구현한다. 만약 101 처럼 루트노드가 0인데, 자식노드 중에 1인 것이 하나라도 있다면, 그 숫자는…

Algorithm
택배 배달과 수거하기 - Swift 문제풀이

택배 배달과 수거하기 - Swift 문제풀이

문제 링크 카카오 코딩테스트: 택배 배달과 수거하기 문제 분석 멀리 있는 집을 먼저 방문하는 것이 이득이기 때문에, 이 문제는 딱 봐도 “그리디다!”를 떠올렸다. 그러나, 스택을 쓰는 것까지는 도달하지 못했다. 배달 및 수거할 택배 상자가 남은 가장 먼 집부터 택배를 배달 및 수거합니다. 트럭이 물류창고에서 출발해 가장 먼 집으로 이동할 때는 배달만 하고, 다시 물류창고로 돌아올 때는 수거만 합니다. 트럭이 물류창고에서 출발할 때 항상 택배를 최대 개수만큼 배달하고, 물류창고로 돌아갈 때 최대 개수만큼 수거합니다. 집 번호와 해당…

Algorithm
개인정보 수집 유효기간 - Swift 문제풀이

개인정보 수집 유효기간 - Swift 문제풀이

문제 링크 카카오 코딩테스트: 개인정보 수집 유효기간 문제 분석 숫자를 년,월,일로 바꾸고 [String] 배열을 순회하면서 유효기간을 계산한 뒤, 만료일과 현재 날짜를 비교하면 되는 문제라고 생각했다. 이 때 월, 일이 각각 오버플로우/언더플로우 되는 상황을 주의해야 한다. 비교는 년도 > 월 > 일 순서로 진행했다. 내 코드 그러나, 월, 일을 비교하고 오버/언더플로우를 처리하는 과정은 조금 복잡하고 실수할 수 있는 영역이기 때문에, 년도, 월을 모두 일로 변환하여 푸는 것으로 코드를 개선하였다. (이 문제의 조건 중 모든 달…

Algorithm
미로 탈출 명령어 - Swift 문제풀이

미로 탈출 명령어 - Swift 문제풀이

문제 링크 카카오 코딩테스트: 미로 탈출 명령어 문제 분석 미로 탈출 조건 격자 바깥으로 나갈 수 없다. (x, y)부터 (r, c) 까지 이동거리가 k여야 한다. 같은 격자를 두 번 이상 방문해도 된다. 탈출 경로(문자열)가 사전 순으로 가장 빠른 경로로 탈출해야 한다.예를들어 탈출 경로가 (lldud, dllrl) 가 있으면, dllrl 가 정답이다. 만약 탈출할 수 없는 경우 “impossible” 를 출력한다. 내 코드 가장 직관적인 방법 사전 순으로 가장 빠른 방향부터 선택하도록 dx, dy를 놓고 이동 횟수가 k가 되면…

Algorithm
유기농 배추

유기농 배추

문제 링크 백준 1012: 유기농 배추 문제 분석 배추밭에서 연결된 배추 그룹의 개수를 구하는 문제 각 연결된 그룹마다 지렁이 1마리씩 필요 상하좌우로 인접한 배추들은 같은 그룹 => **Connected Components 개수 구하기 문제! 각 배추에서 시작해서 연결된 모든 배추를 탐색하면 되는 문제로, 이 때 주의할 점은 한 번 방문한 배추는 다시 방문하지 않아야 함. 이 문제는 DFS, BFS 모두 가능하나, 최단 거리가 아닌 ‘연결성만 확인하면 되는’ 문제로 DFS 가 적합함. 각 칸을 최대 한 번씩은 방문하므로, O(M…

Algorithm
Balanced Binary Tree

Balanced Binary Tree

Problem Explanation What is a Height-Balanced Binary Tree? A height-balanced binary tree is one where for every node, the heights of its left and right subtrees differ by at most 1. Think of it like this. Imagine you’re building a tree structure, and you want it to be “stable” - not too lopsided in…

Algorithm
Valid Anagram

Valid Anagram

Problem First Solution using a Dictionary Approach First, the function checks if the lengths of the two strings s and t are equal. if not, the fucntion returns false as the two strings cannot be anagrams if they have diffrent lengths. Then, the function creates an empty dictionary to store the freq…

Algorithm
Invert Binary Tree

Invert Binary Tree

Problem I need to invert a binary tree by swapping the left and right children of every node. From the examples, I can see that: Each node’s left and right children are swapped This happens recursively for all nodes in the tree The root remains the same, but its entire structure is mirrored Time Co…

Algorithm
Valid Palindrome

Valid Palindrome

Question Today problem is 125_Valid Palindrome A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string , retur…

Algorithm
<알고리즘 노트 - LeetCode>

<알고리즘 노트 - LeetCode>

Merge Two Sorted Lists 1-1. 접근법 (Iterative) 더미 노드를 사용해서 결과 리스트를 구성하면서 두 리스트를 순회하기 더미노드를 만들어 시작점 설정 두 리스트의 현재 노드 값을 비교 더 작은 값을 결과 리스트에 연결 해당 포인터를 다음으로 이동 한 리스트가 끝나면 나머지를 모두 연결 1-2. Recursive 접근법 각 단계에서 더 작은 노드를 선택하고 나머지는 재귀 호출로 처리 Base Case: 한 리스트가 null이면 다른 리스트 반환 Recursive Case: 더 작은 노드의 next를 재귀 …

Algorithm
<C++/백준 16637> 괄호 추가하기

<C++/백준 16637> 괄호 추가하기

<C++/백준 16637> 괄호 추가하기 1. 누적값 + 방향 결정 지금까지의 계산 결과를 가지고 다음에 어떤 연산을 할지 결정! -> 형태로 구현 2. 매 시점 2가지 선택 괄호 없이 그냥 계산 다음 두 수를 묶어서 계산 (인덱스 주의) 코드 수도코드 문제 해결 접근법 “누적값 + 선택” 패턴 인식하기 형태 떠올리기 매 위치에서 가능한 선택지 정리 재귀로 모든 경우 탐색 비슷한 문제 수식 계산 + 괄호 추가/삭제 매 시점 2가지 이상 선택지 이전 결과로 다음 선택하는 경우 정답 코드 1. 누적값 + 방향 결정 2. 매 시점…

Algorithm
<C++/백준 1992> 쿼드트리

<C++/백준 1992> 쿼드트리

코드 해당 문제의 솔루션은 주석과 함께 정리해보았다. 해당 문제를 보고, 내가 특히 부족하다고 느낀 점은. 크게 두 가지다. 이 문제를 이해하는 데 꽤 시간이 걸렸다는 것. ( 이 시간을 단축시켜야 한다. ) 문제를 이해하고 규칙도 파악했으나, 그것을 코드로 표현하지 못했다. ( 재귀 함수를 구현하는 데 아직 경험이 부족해서 이다. ) 해당 문제를 보면, ‘재귀 함수’로 풀어야지가 떠올라야 한다. 큰 문제를 동일한 형태의 작은 문제로 나눌 수 있다는 점이 재귀의 특징이다. 파라미터를 변화시키면서, (4등분으로 나누는 패턴을 반복시…

Algorithm
<코드트리/C++> 만나는 그 순간

<코드트리/C++> 만나는 그 순간

약 10일 전 쯤 내가 풀었던 문제 같은데, 다시 보니까 못풀고 있어서, 여기에 다시 정리해보았다. [알고리즘] 만나는 그 순간 문제 해결 방향 A와 B 각각의 매 초별 위치를 배열에 기록 시간을 1초부터 검사하면서, A와 B의 위치가 일치하는 최초의 시점을 찾기. 주의할 점 전체 이동 시간이 큰 배열을 필요로 할 수 있다. (MAX_T = 1000000) A와 B의 시작 위치는 0으로 초기화되어야 한다. 만약 움직임이 끝날 때까지 만나지 않으면 -1을 출력해야 한다. 코드 내 코드 해설 코드 ⚡️ 시간복잡도 이동 기록: O(tot…

Algorithm
<알고리즘 노트> dx, dy 테크닉 기법

<알고리즘 노트> dx, dy 테크닉 기법

dx, dy 테크닉 기법 은 격자 문제나 방향 시뮬레이션 문제를 풀 때 유용하게 사용되는 기법. 방향 전환, 인덱스 고려 등을 추가로 신경 써야 하는 경우도 있다. 기본 개념 방향이 , 배열의 인덱스가 됨. 문제를 보면 먼저 격자나 그래프를 간단히 그림으로 그려보고, 각 방향에 맞는 x, y 증감값을 설정. 예시 문제 풀이 순서 , 배열을 먼저 작성. 문제의 요구사항에 맞게 방향과 이동을 구현. 방향 전환 방향 전환은 변수로 관리. 반시계 방향 90도 회전 시계 방향 90도 회전 격자 문제에서의 주의점 , 테크닉 활용하기.…

Algorithm
<알고리즘 노트> Carry 피하기 2

<알고리즘 노트> Carry 피하기 2

알고리즘 노트: Carry 피하기 2 문제 설명 문제 유형: 완전탐색 n개의 숫자 중 서로 다른 3개의 숫자를 선택하여, carry가 발생하지 않으면서 나올 수 있는 숫자 합의 최댓값을 계산하는 프로그램을 작성합니다. Carry란? 각 자리수를 더했을 때 10을 넘어가는 경우 carry가 발생합니다. 예를 들어: 3 + 6 = 9 (carry 발생하지 않음) 5 + 7 = 12 (carry 발생) 입력 형식 첫 번째 줄에 n이 주어집니다. 두 번째 줄부터 n개의 줄에 숫자가 주어집니다. 3 ≤ n ≤ 20 1 ≤ 숫자의 범위 ≤ …

Algorithm