본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 2983 개구리 공주 출처: https://www.acmicpc.net/problem/2983 Input 7 5 ACDBB 5 6 8 9 4 13 1 10 7 4 10 9 3 7 Output 7 4 식물들의 위치는 아래와 같습니다. [Jungol] 1889 N Queen 문제에서도 이용했지만 [Jungol] 정올 1889 N Queen 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1162 Input 4 Output 2 N이 4일 때, 나오는 경우는 두 가지이다. 한 행에 놓을 수 있는 여왕말의 개수는 1개 입니다. 그렇기 때문에 행.. zoosso.tistory.com 2차원 평면에서 같은 선상의 대각선상에 위치한 것은 아래와 같이 알 수 있습니다. ▶ (x.. 2021. 2. 25.
[BOJ] 백준 3217 malloc 출처: https://www.acmicpc.net/problem/3217 Input 5 baka=malloc(214); baka=malloc(123); free(baka); deda=malloc(100); print(deda); Output 215 주어지는 명령에서 변수는 항상 4글자 소문자 이므로 특정 위치의 문자를 확인해서 명령이 무엇인지 확인할 수 있습니다. (모든 명령은 최소 6글자 이상을 보장합니다.) - 5번째 글자가 『 = 』 → xxxx=malloc(size); - 5번째 글자가 『 ( 』 → free(var); - 6번째 글자가 『 ( 』 → print(var); - 시작 번호와 할당가능한 크기를 나타내는 free block - 각 변수에 할당된 메모리 (시작 번호 + 할당된 크기) (변.. 2021. 2. 25.
[BOJ] 백준 1238 파티 출처: https://www.acmicpc.net/problem/1238 Input 4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3 Output 10 다른 정점들로부터 특정 정점까지의 최단 거리 비용을 구해야 하므로 플로이드 와샬 (Floyd Warshall) 플로이드 와샬 (Floyd Warshall) 개념 아래와 같은 가중 그래프에서 최단 경로를 찾는 알고리즘. ex) 정점 ③ → ⑤로 가는 최단 경로는 다음과 같습니다. 경로Path: ③ → ② → ④ → ① → ⑤ 비용Cost: +4 +1 +2 -4 = 3.. zoosso.tistory.com 같은 내용의 문제이지만, 다익스트라 알고리즘을 이용해서 풀이 [SWEA] 4007 간담회 참석 [SWEA] .. 2021. 2. 25.
[BOJ] 백준 2610 회의준비 출처: https://www.acmicpc.net/problem/2610 Input 8 7 1 2 2 3 4 5 5 6 4 6 6 7 7 4 Output 3 2 4 8 첫째 줄에 구성되는 위원회의 수 K 그 다음 K줄에는 각 위원회의 대표 번호를 오름차순 출력 ※ 한 위원회의 대표가 될 수 있는 사람이 둘 이상일 경우, 그중 한 명만 출력 결과 설명 - 위원회는 총 3개로 구분. - 대표는 각 연결 그래프에서 거리비용이 제일 작은 정점이며, 정점 [4], [6]이 대표가 될 수 있지만, 그 중 한개 출력 - 정점 [8] 같이 단일 정점도 위원회 소속 및 대표 가능. ① 각 정점별로 최소비용을 모두 구해야하기에 플로이드 와샬 (Floyd Warshall)으로 구현 플로이드 와샬 (Floyd Warshall.. 2021. 2. 25.
[BOJ] 백준 16466 콘서트 출처: https://www.acmicpc.net/problem/16466 Approach 합병 정렬(Merge Sort) 합병 정렬(Merge Sort) Merge Sort 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법 → O(N * logN) - 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다. - 2단계 정복(Conquer) - 해결이 용이한 수준.. zoosso.tistory.com 1차 티켓팅에서 팔린 티켓 목록을 알고 있으므로 그 티켓들을 제외하고 가장 낮은 번호의 티켓을 구하면 됩니다. 1차에서 최대 구매한 개수는 1,000,000개 이지만 티켓들의 총 개수는 231- 1 입니다 (만약 1차에서 1~1,000,000 번호까지 구매했다면 .. 2021. 2. 25.
[BOJ] 백준 7567 그릇 출처: https://www.acmicpc.net/problem/7567 Input (((( Output 25 그룻의 개수는 최소 3개 이므로 첫번째 그릇을 기준으로 시작해서 괄호 모양이 같은지 비교합니다. - 같으면 + 5 - 다르면 + 10 * 탐색할 때마다 기준(pivot)을 바로 앞에 위치한 그릇 모양으로 갱신합니다. ※ 첫번째 그릇이 놓이는 높이 10cm를 초기값으로 둡니다. #include int strlen(const char* s, int len = 0) { while (s[len]) len++; return len; } char str[50 + 5]; int main() { // freopen("input.txt", "r", stdin); scanf("%s", str); char pivo.. 2021. 2. 25.
[BOJ] 백준 5926 Cow Lineup 출처: https://www.acmicpc.net/problem/5926 Input 6 25 7 26 1 15 1 22 3 20 1 30 1 Output 4 ① Hash를 통해 중복되지 않은 소(cow)들의 종류 수를 확인합니다. ex) 1 3 7 → 총 3마리 ② 소들에게 새로운 ID를 부여합니다. (발견된 종류 순서로 부여) 1 → 1 / 3 → 2 / 7 → 3 ③ (새로운 ID까지 부여된) 소들은 x 좌표 기준으로 오름차순 정렬합니다. (merge sort) ④ end 좌표를 확장해가며 소들의 종류가 빠짐없이 포함되는 지점을 찾습니다. ⑤ end 지점을 찾은 후 start 지점을 조정하여 최적(최소) 범위를 조정합니다. 첫번째 s = 1일 때, 모든 종류의 소를 포함하려면 e = 5 하지만 s =.. 2021. 2. 25.
[BOJ] 백준 7573 고기잡이 출처: https://www.acmicpc.net/problem/7573 Input 7 10 6 2 2 2 4 6 2 7 4 3 3 5 6 Output 3 [Jungol] 1437 같은 모양 찾기문제와 달리 그물의 크기가 변합니다. [Jungol] 정올 1437 같은 모양 찾기 출처: [Jungol] 정올 1437 같은 모양 찾기 Input 10 0000000001 1110011100 0100101000 0100101000 1111111111 0000101000 0000001000 0010010000 1111110000 0010010001 3 100 111 100 Output 2 ① 이중 fo.. zoosso.tistory.com ▶ 그물의 크기는 길이 L에서 만들 수 있는 사각형 입니다. ex) L =.. 2021. 2. 25.
[BOJ] 백준 14670 병약한 영정 출처: https://www.acmicpc.net/problem/14670 Input 3 1 3 4 2 99 1 4 1 1 2 4 99 3 4 1 99 1 5 Output 3 2 1 2 3 1 YOU DIED 어떤 약의 이름, 효능과 중복되지 않음을 보장되므로 Hash Table에 약의 효능 = key, 약의 이름 = value로 두어서 증상에 대해 해결 가능한지 빠르게 확인할 수 있습니다. ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색, 삭제가 가능하다. - 매우 빠른 응답을 요구하는 상황에 유용 (Hash는 최소(최대) 원소를 찾는 것 zoosso.tistory.com STL #include #in.. 2021. 2. 25.
[BOJ] 백준 7785 회사에 있는 사람 출처: https://www.acmicpc.net/problem/7785 Input 4 Baha enter Askar enter Baha leave Artem enter Output Askar Artem ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색, 삭제가 가능하다. - 매우 빠른 응답을 요구하는 상황에 유용 (Hash는 최소(최대) 원소를 찾는 것 zoosso.tistory.com STL #include #include #include #include #include #include using namespace std; map member; int main(){ // freopen("input.tx.. 2021. 2. 25.
반응형

티스토리툴바