전체 글

1. 문제 설명 링크 : https://www.acmicpc.net/problem/11672. 풀이과정문제 해결의 흐름  트리에서 임의의 두 점 사이의 거리에 대하여 가장 긴 거리를 찾는 문제이기에 임의의 두 점 사이의 거리를 모두 구해 가장 긴 거리를 찾는 방법을 떠올렸습니다. 즉, 완전탐색과 BFS를 결합하여 문제를 풀고자 하였습니다. 하지만 아래와 같은 트리 구조를 예로 들어봤을 때, 굳이 완전탐색을 적용하여 모든 점을 탐색할 필요 없이 더 간단하게 풀 수 있는 방법이 있지 않을까 고민했습니다. 1 / \ 2 3 / \ 4 5 \ 6    3. BFS는 특정 노드에서 출발하여 모든 노드를 ..

1. 문제 설명링크 : https://www.acmicpc.net/problem/15042. 풀이 과정문제 해결의 흐름 제목, 입력값, 요구사항을 파악해보면 최단 경로 문제, 그중에서도 가중치 그래프에서 특정 시작점으로부터 다른 모든 정점들까지의 최단 경로를 구하는 '다익스트라 알고리즘'을 활용하는 문제 유형임을 쉽게 파악 가능합니다. 따라서 이 문제는 다익스트라 알고리즘을 사용하며 다음 2가지 조건을 만족시키는 경우의 최단 경로를 구해야 합니다. 조건 1 : 1~N까지 이동할 때 반드시 두 정점 v1, v2를 거쳐야 한다.조건 2 : 한 번 이동하였던 정점과 간선은 다시 이동할 수 있다.위 2가지 조건을 만족하는 최단 거리는 다음 2가지 경우뿐이라고 생각되었습니다.경우 1 : 1 -> v1 -> v2..

1. 문제 설명링크 : https://www.acmicpc.net/problem/11492. 풀이 과정문제 해결의 흐름  우선, 문제 설명을 읽고 나서 DP 문제일 거 같다는 느낌이 강하게 들었습니다. 동적계획법, DP(Dynamic Programming)이란?중복되는 계산 결과를 저장하여 복잡한 문제를 더 작은 하위 문제들로 나누어 해결하는 기법입니다.이 기법은 다음 2가지 특징을 가진 문제에서 주로 사용됩니다!최적 부분 구조 : 문제를 작은 부분 문제들로 나누어 부분 문제들의 최적해를 구하여 최종적으로 전체 문제의 최적해를 구할 수 있는 구조 중복 부분 문제 : 동일한 부분 문제가 여러 번 반복되어 나타나는 구조 이 문제를 DP로 접근해야하는 이유는 이웃한 집의 색깔은 서로 달라야하는 조건 하에 모든..

1. 문제 설명링크 : https://www.acmicpc.net/problem/117232. 풀이 과정문제 해결의 흐름  처음에는 문제 제목처럼 집합 STL (std::set)을 사용하는 문제라고 생각하고 풀었더니 시간 초과로 문제가 자꾸 틀렸습니다! 입출력 시간도 줄여보고 여러 시도를 해봤지만, 이 방법은 정답이 아닌듯 보였습니다. 그래서 배열로 해결할까 고민하던 중 알고리즘 분류를 까보니 비트마스킹으로 풀어야하더라구요! 한번도 풀어본 적 없는 풀이법이라 많이 당황하였지만 CS 과목을 들으며 비트 연산에 익숙해졌기에 도전해보았습니다. 비트마스킹이란? 이진수 비트들을 활용하여 데이터를 효율적으로 저장하고 조작하는 기법메모리 절약, 속도 측면에서 엄청난 장점이 있음 비트마스킹을 통해 특정 비트를 1, 0..

1. 문제 설명링크 : https://www.acmicpc.net/problem/15829 문제에서 주어진 해시 함수 식과 주어진 문자열을 바탕으로 해시값을 계산해내는 간단한 문제였습니다!2. 풀이 과정문제 해결의 흐름 우선, 입력 문자열의 각 문자를 정수값으로 변환하는 과정을 거쳤습니다. 처음엔 int(str[i]) - 96과 같은 방식으로 변환하였는데 아래 코드와 같이 변환하는 것이 더욱 깔끔하다고 느껴 바꿨습니다. 이후 pow 함수를 사용하여 해시 함수식을 정확히 계산해 낸 거 같았는데 자꾸 50점에서 그치더라구요 ㅠㅠ. 원인은 2가지로, 입력 크기와 오버플로우 때문이었습니다. 입력 문자열의 길이 L이 최대 50으로 짧아 보였지만, r**i 값은 기하급수적으로 커져 연산 범위를 초과할 가능성이 있었..

1. 문제 설명링크 : https://www.acmicpc.net/problem/27982. 풀이 과정문제 해결의 흐름 보통 1초의 제한은 약 1억회 연산을 수행할 수 있는 기준이며, N(카드의 개수)가 최대 100개이므로 3중 for문을 사용할 경우 최대 백만회의 연산을 수행하므로 주어진 시간 내에 해결 가능하다고 판단하였습니다. 세 수의 합이 M을 초과하는 경우에는 break문을 사용하여 탐색을 중단하도록 효율을 높였습니다.#include #include using namespace std;int main() { // 0. 입력 받기 int N, M; // N(3 > N >> M; int num_lst[N]; for (int i = 0; i > num_lst[i]; } ..

전역 후 첫 학기였던 2학년 2학기, 새로운 마음가짐으로 임했다. 주변에서는 ‘컴공은 학점이 중요하지 않다’, ‘그 시간에 양질의 프로젝트를 하는 게 더 낫다’는 의견도 있었지만, 나는 ‘정말 수준 높은 CS 수업은 학교에서만 들을 수 있다’는 말에 더 공감했다. 1학년 때 높은 학점으로 성적 장학금을 받은 경험도 있어, 공부와 장학금이라는 두 마리 토끼를 잡을 수 있는 좋은 기회라고 생각했다. 그래서 이번 학기에는 최대한 최선을 다해보자는 마음으로 임했다. 물론 교과 과목에만 매달리지는 않았다. 카카오테크캠퍼스 팀 프로젝트와 세차새차 백엔드 개발 활동을 통해 꾸준히 개발 역량도 쌓았다.  공부에서는 나름의 전략을 세웠다. 우선, 교수님의 강의를 집중해서 듣고 강의 자료에 중요한 내용을 꼼꼼히 필기했다...

1.  스택 (Stack)(1) 정의와 성질 스택은 기본적으로 후입선출(LIFO, Last-In-First-Out) 방식을 따르는 자료구조이다. 즉, 프링글스 통처럼 한 쪽에서만 데이터를 넣는 구조로 가장 마지막에 추가된 원소가 가장 먼저 제거된다! 이러한 특성 때문에 스택은 데이터를 일시적으로 저장하며 저장된 역순으로 접근해야할 때 유용하게 사용된다. (2) 관련 메서드 및 구현 관련 메서드 (C++ 기준) void push(const T& value);스택 최상단에 원소를 추가한다.시간복잡도 : O(1)void pop();스택 최상단 원소를 제거한다. 시간복잡도 : O(1)T& top();스택 최상단 원소를 조회한다.시간복잡도 : O(1)bool empty();스택이 비어 있는지 확인한다.시간복잡도 ..