본문 바로가기

반응형

알고리즘 문제풀이

(57)
[ 프로그래머스 Lv2] 멀쩡한 사각형 (Javascript) https://school.programmers.co.kr/learn/courses/30/lessons/62048 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제의 핵심은 최대공약수를 사용하는 것이다. 왜 최대공약수를 사용해야 하는지 그 이유를 살펴보자. 이 문제를 이해하기 위해서는 닮음비의 개념을 알아야 한다. 문제에서 사각형만 다루므로 사각형으로 예시를 들겠다. 닮음비란 두 도형이 닮음일 때, 거기서 대응하는 변의 길이의 비를 말한다. 좀 쉽게 말하면 가로, 세로 길이에 n을 곱한 것을 말한다. n을 곱함으로써 도형이 n배 커질 수 있고, 반대..
자바스크립트 코테 꿀팁 하나씩 모아가는 꿀팁 리스트... 1. 문자열 슬라이싱 - slice는 음수를 허용하기 때문에 substr보다 좋다. // 구문 str.slice(beginIndex[, endIndex]) // 파이썬과 비교 str.slice(n) = str[n:] str.slice(n, m) = str[n:m] str.slice(-n) = str[-n:] str.slice(-n, -m) = str[-n:-m] 인덱스 초과시 빈 문자열 반환 2. min, max // 배열 최대값 Math.max(...[1,2,3,4,5]) // 최소값 Math.min(4, 5) 3. 객체 순회 const obj = { 'a': 1, 'b': 2, 'c': 3 } // 1. 객체를 배열로 변환 Object.entries(obj) //[ ..
[ 코테 꿀팁 ] set, unordered_set (C++) set과 unordered_set은 코테 보면서 사용할 일이 그닥 많지 않다. 근데 모르면 못 써먹기 때문에 간단한 특징과 함수들을 정리해봤다. 1. 특징 1) Set - 균형 이진탐색트리 구조 - 탐색, 삽입, 삭제 모두 O(logN) 보장 - 정렬된 상태 - 값 중복 X 2) Unordered_set - 해시테이블 구조 - 탐색, 삽입, 삭제 모두 O(1) - 원소가 너무 많아지면 리헤싱 과정을 거치는데 이는 O(N) 시간 소요 - 정렬되지 않음 - 값 중복 X 균형 이진탐색트리가 뭔지, 해시테이블이 뭔지에 대한 설명은 생략하도록 한다. 이 둘의 공통점은 키(key) 값으로 접근한다는 점이다. 따라서 Key의 존재여부만을 판단할때 사용하면 좋다. 2. 함수(둘 다 똑같다) 기본 선언 : set s; ..
[ 백준 3197 ] 백조의 호수 (C++) https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 효율성을 고려해야 하는 문제다. 푸는데 꽤 오래 걸렸다... 문제를 읽어보면 알겠지만 얼핏 보면 어려운 문제로 보이지 않는다. 그냥 bfs 또는 dfs를 계속 사용하면 테스트 케이스는 통과한다. 그런데 그렇게 풀면 무조건 시간초과에 걸릴 것이다. 이 문제는 단 한번의 bfs로 해결해야 하는 문제다. 전체적인 알고리즘은 '경로탐색 -> 얼음 녹이기'를 반복하면 된다. 그..
[ 백준 2933 ] 미네랄 (C++) https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 내 수준에서는 좀 어려운 문제였다. 단순 구현 문제긴 하지만 머리를 좀 써야 한다. 우선 큰 그림부터 그려보자. 문제를 풀기 위한 큰그림과 사용하는 변수는 아래와 같다. 1. 막대기로 미네랄 캔다 2. 붕 뜬 클러스터가 있으면 내려준다 char map[101][101] -> 입력값 저장 int visit[101][101] -> 방문 배열 (dfs에서 사용) int sticks[100] -> 막대기 배열 int ..
[ 백준 11559 ] Puyo Puyo (C++) https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net dfs를 이용한 재밌는 구현 문제였다. 규칙을 만들고 그대로 구현하기만 하면 되는 문제라 크게 설명할 것은 없다. 인접한 동일 색깔의 개수를 count라고 했을때, dfs 결과 count가 4 이상인 것은 map에서 삭제해주고 붕 떠 있는 것을 아래로 내려주면 된다. 말로 하면 좀 헷갈리니 사진으로 확인하자. 아래는 문제의 테스트 케이스를 돌렸을때 첫 번째 연쇄 과정이다...
[ 백준 8911 ] 거북이 (C++) https://www.acmicpc.net/problem/8911 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 www.acmicpc.net 단순 구현 문제다. Turtle 이라는 클래스를 만들어서 풀었다. 정답으로 출력해야 하는 직사각형의 넓이는 거북이의 이동경로에서 가로/세로 최대/최소값의 차이를 곱하면 된다. 문제에서 주어진 네 개의 함수는 그대로 구현했고, 여기에 init() 라는 함수를 추가했다. 이 함수는 거북이가 이동할때마다 x, y의 최대 최소값을 초기화해주는 함수다. 문제가 어렵지 않으므로 바로 정답 코드... #include #..
(C++) sort 커스터마이징 , STL vector 멤버 함수, 문자열 find 1. sort 함수 커스터마이징 bool comp(const type& A, const type& B); sort(vec.begin(), vec.end(), comp); sort(ary, ary + n, comp); // n은 ary 배열의 크기 sort 함수는 라이브러리에 있는 메소드로 벡터나 배열을 정렬할때 사용된다. 기본적인 사용 방법은 위와 같다. 여기서 comp 함수를 따로 정의해주면 정렬을 사용자 입맛대로 할 수 있다. comp 함수는 두 개의 매개변수를 가지는데, 타입은 string, struct, class, int 등 모두 사용 가능하다. 정렬되는 순서는 true가 되는 규칙을 따른다. 사실 이게 끝이다. 예를 들어보자. 매개변수 타입이 string이라고 가정해보자. 만약에 아래와 같다면..

반응형