Blog for Programming

1. 문제 및 예제 이게 무슨 유형의 문제인가... 구현인가 싶었는데 재귀가 정답이었다. 배열에 그리는 문제를 전에 만나봐서 예외 처리 빼고는 어렵지 않게 설계할 수 있었다. 재귀함수 잘 쓰고 싶다.. 지금은 그냥 써야될 때 쓰는 수준? 책에서 본 알고리즘 풀이들은 재귀함수를 마치 무기처럼 자유자재로 쓰던데 그 경지에 도달할 때 까지 연습하고 싶다. https://school.programmers.co.kr/learn/courses/30/lessons/68645 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 문제를 나누는게 참 중요하다는걸 ..

1. 문제 및 예시 실행 결과 solved.ac의 CLASS가 올라갈수록 모르는 알고리즘이 많다. 어제 토스 코테 한번 찍먹하고 많이 반성하게 됐다. 모르는 것을 공부하는게 맞는 것 같다. Union-find를 활용한 크루스칼 알고리즘을 공부하고 적용해보았다. 한큐에 초록 글자가 떠서 너무 좋았다. 출처: https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 2. 풀이과정 문제를 잘게 나눠봤다. 1. 문..

1. 문제 및 예시 실행 결과 투 포인터를 활용하는 문제... 나름 재밌었다. 보통 이런 경우는 이분탐색 처럼 구현을 하게 되는데 그 과정은 어렵지 않지만 어떤 문제로 접근해야하는지 찾는 과정이 이분탐색 혹은 투 포인터 문제의 핵심이라는 생각이 든다. 출처: https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 2. 풀이과정 문제를 잘게 나눠봤다. 1. 입력 2. 이분탐색 진행 왼쪽과 오른쪽으로 부터 시작하여 두 값의 합이 0보다 크면 음수쪽이..

1. 문제 및 예시 실행 결과 간단한 다익스트라 문제이지만, 경로를 출력해야한다. 처음에는 문자열을 옮기는 방식으로 풀었는데, 원인을 알 수 없는 이유로 틀렸다는 문자만 계속 떴다. 그래서 경로를 배열에 저장하는 방식을 사용했다... 문자열도 같은 원리인데 대체 왜 그러는지 참... 출처: https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 풀이과정 문제를 잘게 나눠봤다. 1. 입력 2. 다익스트라 진행 3. ..

1. 문제 및 예시 실행결과 다익스트라 문제라는 것을 처음부터 알게 되었다. 문제 잘 읽고 푸는 습관을 들여야하는데... 부등호하나 잘못써서 두번의 틀렸습니다가 찍힐뻔 했다... 다익스트라가 손에 조금 익어서 해당 알고리즘을 사용하고 있는데 플로이드 워셜로 나중에 공부해서 적재적소에 사용할 수 있으면 좋겠다. 출처: https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 2. 풀이 과정 문제 쪼개기 1. 입력 2. 모든 노드를 시작점으로 설정 - cache..

1. 문제 및 예시 실행결과 BFS문제인 것은 파악했는데 visited 배열을 처리하는 과정에서 조금 힘들었다. 논리적으로 길을 먼저 세워 풀면 되는 문제를 너무 급하게 덥벼든 것 같다. visited를 배열에 삽입하기 전에 처리하는 것이 좋을 수 있지만(Queue가 커지는 것을 방지) 이 문제 처럼 같은 depth의 중복을 처리해야하는 문제는 queue에서 노드를 꺼내서 visited처리를 하는게 좋을 수 있다는 것을 깨달았다. 다음은 예외 케이스이다. 1 3 출처: https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)..

1. 문제 및 예시 실행결과 구현과 시뮬레이션 문제이다. 어우 힘들어... 구현은 아무래도 높은 집중력과 예외처리를 위한 설계가 중요시 되는 것 같다. 한번 오류나면 멘탈이 나가서 문제 난이도가 생각보다 높게 느껴진다. 재능있는 사람들은 처음부터 오류없는 코드를 잘 작성하겠지만, 나는 그런 것 같지는 않으니 최대한 고심해서 코드를 짠다. 그래서 이리 힘든 것인지... 출처: https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 2. 풀이 과정 알고..

1. 문제 및 예제 담은 귤의 종류가 적다는건 갯수가 많은 종류를 순서대로 나열해 순서대로 박스에 넣어주면 된다. 귤의 종류와 그 갯수를 저장할 자료구조 하나 그리고 그것을 갯수로 정렬할 알고리즘을 생각하면 별로 어렵지 않은 문제이다. C++의 sort()를 사용했으니 시간복잡도는 O(NlogN)이다. https://school.programmers.co.kr/learn/courses/30/lessons/138476 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 처음 내가 이 코드를 작성하고 제출을 했을 때 분명 더 좋은 풀이법이 있을거라 ..

1. 문제 및 예제 완전탐색이라고 그냥 너무 무식하게 다 비교하면 안된다는걸 알게된 문제. 처음에는 모든 높이와 넓이를 매칭시키고(여기서 나온 시간복잡도는 O(N*N) 이걸 모든 명함과 비교하는 방법.(결과적으로 총 시간 복잡도는 O(N*N*N)... 내가 미친거지 아주) 생각해보면 참 답이 없다 싶었다... 아직도 이런 문제로 해매다니... 자괴감 들었지만 그래도 다른 풀이들 참고하면서 풀었다. 개인적인 의견으로 수학 못 하는 나에게 이 문제는 레벨1 문제는 아닌듯... 출처: https://school.programmers.co.kr/learn/courses/30/lessons/86491 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고,..

1. 개요 구현 문제단원을 풀어보는 과적엥서 문자를 찾아 지우는 erase()함수는 있어도, 인덱스를 기준으로 삭제해주는 함수가 없기에 만들어보면 유용할 것 같다는 생각이 들었다. 인덱스를 기준으로 문자 하나를 입력했을 때 해당 자리의 문자를 제거해주는 함수를 만들어 보았다. 2. 이론 구현 이론은 간단하다. 해당 인덱스까지의 문자열을 자르고 그 뒤의 인덱스를 다시 잘라 기존 전자의 인덱스와 더해주면 된다. 3. 코드 - 인덱스 기준의 문자 제거 코드 string erase_char(string str, int index) { string buff; buff = str.substr(0, index); buff += str.substr(index + 1, str.size() - (index + 1)); r..