CSE 전공노트

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 난이도: 플래티넘 4 사용언어: JAVA 풀이 SCC와 위상 정렬을 함께 고려해야 하는 문제입니다. 언뜻보면 SCC 문제가 아닌것 같지만, 도미노들의 SCC를 구하고 구해진 SCC들간에 위상 정렬을 해서 다른 SCC로 부터 영향을 받지 않는 SCC들을 골라내면 정답을 도출 할 수 있습니다. SCC의 풀이 중 코사라주 알고리즘을 이용했고, 코사라주 알고..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 난이도: 플래티넘 5 사용언어: JAVA 풀이 이름 그대로 Strongly Connected Component(SCC) 문제의 가장 기본적인 유형입니다. 저는 코사라주 알고리즘을 이용하여 문제를 해결하였습니다. 코사라주 알고리즘은 아래의 링크에서 더 자세하게 확인..

코라사주 알고리즘은 SCC(Strongly Connected Component) 문제를 해결하기 위한 알고리즘입니다. SCC란 강한 연결 관계라고 번역될 수 있습니다. 1. 강한 연결 관계? SCC는 그래프에서 노드 간의 연결 관계가 주어질 때, 정점들의 최대 부분 집합으로, 부분 집합에 들어있는 서로 다른 노드 u와 노드 v에 대하여, u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 뜻합니다. 위의 그래프에서 1, 2, 3번 노드는 각각 서로의 노드로 갈 수 있는 노드가 모두 존재합니다. 예를 들어, 1번 노드에서 3번 노드로 가는 경로가 존재하고, 3번 노드에서 1번 노드로 가는 경로도 존재하죠. 하지만 4번과 5번의 경우, 1, 2, 3번 노드로부터 갈 수는 있으나 4 또는 ..

JVM은 Java Virtual Machine의 약자로 자바 프로그램을 OS 환경과 상관없이 구동될 수 있도록 해주는 가상 머신입니다. 1. JVM의 역할 1. OS에 구애받지 않는 실행 사용자가 작성한 자바 코드는 자바 컴파일러에 의해 자바 바이트 코드로 컴파일되고, JVM은 이 자바 바이트 코드를 사용자의 컴퓨터가 어떤 OS를 사용하든 상관없이 돌아가게끔 만들어줍니다. 즉, 원래 프로그램은 Windows에서 개발되었다면 Mac이나 Linux에서는 구동할 수 없습니다. 하지만 자바는 JVM만 실행 환경에 맞추어 준비해 놓는다면 어떤 OS를 사용하든지 상관없이 구동할 수 있다는 뜻입니다. Windows에서 개발되었더라도 Mac에 맞추어 JVM을 준비만 해 둔다면, 충분히 Mac에서도 실행이 가능합니다. ..

앞의 글에서 우리가 코딩 시에 사용하는 언어들은 컴파일 언어와 인터프리터 언어로 구분할 수 있다는 사실을 알게 되었다. 다시 기술하자면, C, C++, Go 등의 언어는 컴파일 언어이고, Python, R, JavaScript와 같은 언어들은 인터프리터 언어이다. 앞의 글은 아래의 링크에서 확인할 수 있다. https://jooona.tistory.com/156 [프로그래밍 언어] 컴파일 언어 vs 인터프리터 언어 우리는 고급 언어를 이용해 프로그램을 짜곤 한다. 여기서 고급 언어란 우리가 사용하는 Java, C, Python 등의 언어를 뜻한다. 이 고급 언어는 크게 컴파일 언어와 인터프리터 언어로 구분할 수 있다 jooona.tistory.com 그렇다면, Java는 왜 예시에 포함되지 않는 것일까?..

우리는 고급 언어를 이용해 프로그램을 짜곤 한다. 여기서 고급 언어란 우리가 사용하는 Java, C, Python 등의 언어를 뜻한다. 이 고급 언어는 크게 컴파일 언어와 인터프리터 언어로 구분할 수 있다. 오늘은 둘 간의 차이점을 알아보고자 한다. 1. 컴파일 언어 컴파일 언어는 내가 작성한 소스 코드 전체를 컴퓨터가 알아먹을 수 있는 기계어로 번역한 뒤, 이 번역된 코드를 한번에 실행하는 두 단계를 거쳐 진행된다. 즉 번역과 실행이 완전히 따로 이루어진다는 뜻이다. 번역은 컴파일러를 통해 수행되고, 대표적인 예시로는 C, C++, Go 등이 있다. * 특징 * 1. 컴파일은 오래 걸릴 수 있다! --- 힘겹게 만든 코드를 5시간에 거쳐 컴파일을 했다고 가정해보자! 그런데 변수 이름에 오타가 나서 에러..

Android Studio에서 차트를 그리기 위해서 Github의 MPAndroidChart를 사용했다. Github 주소는 아래와 같다. https://github.com/PhilJay/MPAndroidChart GitHub - PhilJay/MPAndroidChart: A powerful 🚀 Android chart view / graph view library, supporting line- bar- pie- radar- bubb A powerful 🚀 Android chart view / graph view library, supporting line- bar- pie- radar- bubble- and candlestick charts as well as scaling, panning and a..

관계형 데이터베이스 관계형 데이터베이스: 데이터가 테이블에 저장되며, 각 테이블은 행과 열 (Tuple & Attribute)로 구성. 이러한 일련의 테이블을 정의한 것을 스키마(Schema)라고 부른다. 키(Key) 테이블에서 특정 행을 유일하게 식별할 수 있게 하는 특정 열 또는 여러 열의 모음. 보통 키 중 하나를 프라이머리 키(Primary Key)로 지정. --> 테이블 각 행에는 프라이머리 키 값이 반드시 있어야 하고, 유일해야 한다. 프라이머리 키 예시) 학생 테이블의 학번. 이름은 중복된 경우가 있을 수 있어 사용 불가. 외부 키를 이용하여 다른 테이블과 링크시키는 것이 가능. 모든 외부 키 값이 참조하는 테이블의 값으로 존재한다면, 그 데이터베이스는 참조 무결성 조건을 만족. SQL SQ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 난이도: 골드 2 사용언어: JAVA 풀이 크루스칼 알고리즘을 사용하는 최소 스패닝 트리 문제입니다. 전형적인 최소 스패닝 트리 문제에 각각의 발전소와의 연결 여부만 추가적으로 확인해 주면 정답을 받을 수 있습니다. 각 발전소와의 연결 여부는 각 발전소의 부모와 해당 도시의 부모를 비교해보면 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 구현 문제는 하라는 대로 다 해주면 되죠? 제가 처음 구현할 때 간과했던 부분만 짚고 넘어가겠습니다. 1. 얼음을 삭제할 때 Queue에 담아서 삭제해 줄 것. 그렇지 않으면 이전에 삭제한 얼음이 다음 얼음에 영향을 미칠 수 있다. 2. 얼음을 0 이하의 정수로 감소시키지 ..