HOME

파티 풀이과정 다익스트라 알고리즘을 이용해 문제를 해결하였다. 이 문제를 풀기 전에 같은 다익스트라 문제인 1753번, 1916번 문제를 먼저 풀어보는게 좋다. 다익스트라 알고리즘 간선의 가중치가 모두 양수일 때 사용하는 알고리즘이다. 항상 최소 비용을 비교하여 갱신한다. 최단 거리가 정해진 노드는 더 이상 방문하지 않는다. 간선(도로)의 정보를 저장한다. x 도시에서 y 도시로의 최단 거리를 저장할 이차원 배열 dist를 생성하고 기본값을 INT의 최대값으로 설정한다. dist[x][y] 는 x에서 y로의 최단 거리이다. 각 도시에 대해 다익스트라를 수행한다. 우선순위 큐(최소힙)를 이...

DFS 복면산?! 풀이과정 dfs를 이용한 순열 구하기와 비슷한 문제이다. 입력된 알파벳에 0~9까지의 숫자를 모두 할당한 후 복면산인지 확인해야하므로 재귀함수를 이용한 dfs로 문제를 해결하였다. 전체 과정은 다음과 같다. 입력된 문자열에 대해 알파벳을 골라낸다. A~Z 까지의 알파벳 중 입력된 알파벳이면 alphabet 배열에 넣는다. alphabet의 원소에 0~9까지의 숫자를 할당한다. 숫자를 모두 할당하면 할당한 숫자로 복면산을 만들 수 있는지 확인한다. 복면산을 만들 수 있으면 isBokMyunSan = true로 플래그 값을 바꿔준다. 코드 #include &l...

DFS BFS 적록색약 풀이과정 방향을 나타내는 배열을 만들어 상하좌우를 탐색한다. 입력받은 그림정보를 가공하여 적록색약인 사람에 대해 탐색한다. 색깔이 G인 경우 R로 바꾸고 탐색 함수의 재귀를 이용해 DFS를 수행한다. 코드 #include <stdio.h> #include <string.h> using namespace std; int n, cnt = 0; char photo[100][100]; bool isVisited[100][100] = { false }; int dx[4] = { 0,0,-1,1 }; int dy...

어댑터 패턴(Adapter Pattern) GoF 디자인 패턴 중 구조 패턴에 해당한다. 클래스의 인터페이스를 사용자가 기대하는 다른 인터페이스로 변환하는 패턴이다. 호환성이 없는 인터페이스 때문에 함께 동작할 수 없는 클래스들이 함께 작동하도록 해준다. 안드로이드 개발 시 자주 보게 되는 패턴 중 하나이므로 개념 정리를 해보았다. 사용법 기존 클래스를 사용하고 싶은데 인터페이스가 맞지 않을 때 기존에 만들어 놓은 것을 재사용하고 싶은데 그것을 수정할 수 없을 때 구조 클래스 어댑터(Class Adapter) Adaptee는 변환이 필요하다. Adaptor가 Adaptee를 ...

44. 마구간 정하기 인프런의 it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 수강하여 공부한 내용을 기록한 포스트입니다. 문제는 공개하지 않습니다. 풀이과정 43번 문제와 마찬가지로 이분검색 문제이다. 이분검색 문제에서는 이분검색할 범위를 찾는 것이 중요한 것 같다. 이분검색할 최대 범위를 찾는다. 이 범위는 배열의 크기가 아니므로 프로그래머가 찾아야한다. 그 값이 조건에 타당한지 검사 후 계속 이분검색을 수행하여 답을 찾는다. 이 문제는 이분검색할 범위를 입력의 최대값으로 정해야 해서 먼저 sort()를 통해 오름차순으로 정렬해주었다. 1~(입력의최댓값...

43. 뮤직비디오 인프런의 it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 수강하여 공부한 내용을 기록한 포스트입니다. 문제는 공개하지 않습니다. 풀이과정 이분검색을 응용하는 문제이다. 처음 문제를 보고 DP나 Brute Force를 사용하는건가 싶어서 막막했는데 아니었다 ㅠㅠ 이분검색을 이용하는 결정 알고리즘이라고 한다. 주어진 입력 내에서 가능한 최대 녹화 길이를 찾는다. 1 ~ 1,000*10,000 이분검색을 통해 가능한 녹화 길이를 결정한다. 코드 #include <stdio.h> #include <vector>...

옵서버 패턴(Observer Pattern) GoF 디자인 패턴 중 행위 패턴에 해당한다. 객체의 상태 변화를 관찰하여 변화가 발생하면 변화를 통지받고 자동으로 갱신될 수 있게 한다. 주로 분산 이벤트 핸들링 시스템을 만들 때 사용한다. 사용법 어떤 객체의 변화로 인해 다른 객체가 변경되어야 하는데, 프로그래머들은 얼마나 많은 객체들이 변경되어야 하는지 몰라도 될 때 외부에서 발생한 이벤트에 대해 결과를 처리해야 할 때 구조 데이터의 변화가 발생할 Subject는 Observer들을 알고 있다. Subject는 변화가 발생하면 Observer에게 notify한다. 장점 ...

팩토리 메소드 패턴(Factory Method Pattern) GoF 디자인 패턴 중 생성 패턴에 해당한다. 수퍼클래스에 알려지지 않은 클래스에 대해 서브클래스에서 어떤 객체를 생성할 지 결정하도록 하는 패턴이다. 수퍼클래스는 추상메소드 create를 정의하고, 서브클래스가 이를 재정의하여 객체를 생성한다. 이 때의 create메소드를 팩토리 메소드라고 한다. 추가로, 서브클래스는 수퍼클래스를 상속하지만 확장하지는 않는다는 점에 유의해야 한다. 사용법 어떤 클래스가 자신이 생성해야 하는 객체의 클래스를 알지 못할 때 객체의 생성을 서브클래스에게 위임하고 싶을 때 구조 Creator...

빌더 패턴(Builder Pattern) GoF 디자인 패턴 중 생성 패턴에 해당한다. 빌더 패턴은 복잡한 객체를 생성하는 클래스와 표현하는 클래스를 분리하여, 동일한 절차에서도 서로 다른 표현을 생성하는 방법을 제공한다. 사용법 객체의 생성 알고리즘이 조립 방법에 독립적일 때 합성할 객체들의 표현이 서로 다르더라도 생성 절차에서 표현 과정을 지원해야할 때 구조 Builder추상클래스를 정의하고 이를 상속받은 ConcreteBuilder서브클래스를 구현한다. Product의 일부가 build될 때마다 Director는 Builder에 통보한다. Builder는 Director...

싱글톤 패턴(Singleton Pattern) GoF 디자인 패턴 중 생성 패턴에 해당한다. 어떤 클래스의 인스턴스는 하나임을 보장하는 패턴이다. 또한 그에 대한 전역적인 접근점을 제공한다. 주로 공통된 객체를 여러 곳에서 참조해야 하는 경우(ex. 데이터베이스 참조)에 사용한다. 자바에서는 생성자를 private으로 선언하고 getInstance()와 같은 함수를 통해 인스턴스를 제공해주는 것이 일반적이다. 코틀린에서는 싱글톤 패턴을 보장해주는 object 키워드가 존재한다. 사용법 클래스의 인스턴스가 하나임을 보장해야 할 때 구조 Singleton 클래스는 getInstance()...