본문 바로가기

전체 글298

[백준 6987] 월드컵 (Swift) https://www.acmicpc.net/problem/6987Simulation + DFS6개국이 서로 한번씩 경기한다고 했을 때, 경기결과를 각 나라마다 승,무,패 횟수로 정리한 표를 보고가능한 결과인지 아닌지 판단하는 문제 접근방법처음에 브루트포스, 백트래킹이라고 써있어서 접근하기 너무 어렵다가나라별로 경기를 치르는 대진의 총 개수가 15개 라는 것을 보고한 경기의 대진을 ( A , B ) 라고 했을 때 15개의 모든 경우를 배열로 저장했다. [(1,2),(1,3),....,(5,6)] 이런식으로그리고 이제 한 경기를 하나의 노드라고 보고 dfs 탐색을 진행하면서각 노드 마다 뻗어나가는 가지는 A>B, A=B, A 세가지가 있을 수 있다고 생각하고 모든 경우를 완전탐색하는 것 그러면 모든 경기의 .. 2025. 3. 20.
[백준 2533] 사회망 서비스 (SNS) (Swift) https://www.acmicpc.net/problem/2533 DP & DFS 트리인 그래프의 노드간 연결 정보가 간선개수(= 노드개수-1) 만큼 주어지고,모든 노드는 얼리어답터이거나 아니거나 일 때, 내가 얼리어답터면 내 친구들에게 정보를 전파할 수 있음.그래프의 모든 노드가 정보를 전파 받을 수 있으려면 최소 몇명이 얼리어답터여야 하는지.구하는 문제  접근방법DP랑 DFS 같이 쓰는거 생각해내기까지가 어려운 것 같음..블로그 보고 이해하고 풀이함 key 고려사항1. 무방향 그래프 처럼 인접 그래프를 만든다.2. DP 배열은 노드수 * 2 이고,[N][0] : N 번째 노드가 얼리어답터인 경우 최소 얼리어답터수[N][1] : N 번째 노드가 얼리어답터가 아닌 경우 최소 얼리어답터수이다.3. visi.. 2025. 3. 20.
[백준 11058] 크리보드 (Swift) https://www.acmicpc.net/problem/11058 DP 왜 디피는 여전히 어려운걸까부분 문제로 열심히 머리굴리다가 안돼서 다른 블로그 참고했다.결론은 점화식을 세우는 것이었음! - 간단해보이는 문제는 점화식으로 풀려고 했었던 것 같은데 오히려 이렇게 복잡해 보이는 문제는 더 점화식으로 풀 생각을 안하는 것 같음.. Key Idea는- 우선 Ctrl-A, C, V를 한묶음으로 생각하기- 비교대상을 A누르기 vs 복사하기 에서 A누르기 vs 1번 복사하기 vs 2번 복사하기 .. .. 로 확장해서 생각하기였다. 점화식 세운 과정dp[i] = max ( dp[i-3] * (1+1),                       dp[i-4] * (2+1),                       .. 2025. 3. 19.
[Swift] 순환참조와 strong, weak, unowned 순환참조 문제변수나 상수가 참조타입의 인스턴스를 참조할 경우 따로 키워드를 지정하지 않으면 strong 즉 강한 참조를 하게 되는데, 참조타입을 증가시키는 것도 모두 이 강한참조일 때만 발생한다.이때, 두 클래스가 서로를 참조하는 프로퍼티를 모두 갖는다면, 힙에서 두 인스턴스 모두 영원히 해제되지 않는 상황이 발생한다.A의 프로퍼티가 B 강한참조, B의 프로퍼티가 A 강한참조→ B RC: 2 (생성될때, A에의해 참조될때)→ A RC: 2 (생성될때, B에의해 참조될때)A = nil, B = nil→ B RC: 1 (nil로 인한 -1, A가 메모리 상에 있으므로 A에 의해 증가한 참조횟수 1이 그대로 남아있음)→ A RC: 1 (nil로 인한 -1, 그치만 B에의해 증가된 참조횟수 1이 남아있어서 메모.. 2025. 3. 14.
[Swift] 메모리 관리 기법 (ARC) ARC (Automatic Reference Counting)힙에 할당되는 참조 타입을 해당 값이 더 이상 필요하지 않을 때, 자동으로 메모리에서 해제해주는 기법이를 통해 개발자가 직접 참조타입에 메모리 할당, 해제를 해주지 않아도 자동으로 메모리 할당과 해제가 이루어져 메모리 누수를 막을 수 있다. RC(Reference Count)를 이용한 메모리 관리 기법으로, 힙에 할당되는 인스턴스마다 RC를 갖고 있음.해당 인스턴스가 참조되고 있는 횟수를 나타내며, 0이 되면 자동으로 해제 된다.참조 횟수(RC)를 증가시키는 경우인스턴스를 새로 생성할 때 (ex. 클래스 인스턴스 생성 → 변수에 대입)기존 인스턴스를 다른 변수에 새로 대입할 때참조 횟수(RC)를 감소시키는 경우인스턴스를 가리키던(참조하던) 변수.. 2025. 3. 14.
[백준 16113] 시그널 (Swift) https://www.acmicpc.net/problem/16113 문자열 구현 문제입력이 아래와 같이 문자열의 길이와 #과 . 로만 이루어진 문자열이 들어온다. 40###..#..#.#..#..###..#..#.#..#..###..#.. 이 문자열로 5줄을 만들었을 때, #은 검은칸, .은 흰색칸으로 그리면숫자가 나온다.숫자는 세로로 5칸을 차지하고, 1의 경우 한칸의 열을 차지하는 것을 제외하면 3칸의 열을 차지한다.이런 규칙을 갖고 있는 시그널을 숫자로 해독하는 문제 접근방법딕셔너리에 이차원배열: 숫자 String 을 0~9까지 저장했다. 그리고 공백 "" 에 해당하는 5행이 모두 비어있는 배열로 이루어진 이차원 배열도 "" 이렇게 저장해줌 (빈칸이 여러개 있을 때를 대비한..) 그리고 문자열을 전.. 2025. 3. 13.
[백준 1005] ACM craft (Swift) https://www.acmicpc.net/problem/1005 위상정렬, DP, DFS (?)건물들의 건설시간과 건설 순서가 주어진다 (건설 순서 : a, b (a지은 후 b를 지을 수 있음))이때 W번 건물이 지어질 수 있는 가장 짧은 시간 구하는 문제위의 사진의 경우 4번 건물을 2와 3이 모두 지어진 후인 110초 후에 지어지기 시작해서 120초가 걸려야 지어짐 접근방법part 1. 재귀 DFS + DP로 풀어보려고 시도얼마전에 그 강 순서 구하는 것 처럼 구해야할 노드에서 시작해서 역으로 구해보려고 했는데 시간초과났음 part 2. 위상정렬선행하는 노드들이 먼저 수행되어야 내가 수행될 수 있다 -> 이전에 줄세우기 문제와 유사함위상 정렬 사용해서 풀이해야 하는 문제라서 어떻게 할지 고민하다가 .. 2025. 3. 12.
[백준 1495] 기타리스트 (Swift) https://www.acmicpc.net/problem/1495 DPN개의 곡마다 볼륨을 조정할 수 있는 크기가 주어진다. 무조건 그 곡을 연주할 때는 현재 볼륨에서 V[i] 를 빼거나 더한 볼륨으로 연주해야함시작 볼륨이 주어지고 볼륨의 최대치가 주어질 때, 마지막 곡을 연주할 수 있는 가능한 최대 볼륨을 출력하는 문제 접근방법이게 DP인지 완탐인지 모르게 풀이하긴 했다.처음에는 2차원 배열에 볼륨을 올리는 경우와 내리는 경우를 저장해서, 최대값을 갱신하는 식으로 하려고 했는데, 뭔가 고려하지 못하는 경우의 수가 있을 것 같았다..저번에 퇴사 문제 풀 때도 이렇게 풀어서 틀렸던 기억그래서 일직선에 0부터 M까지의 볼륨이 나타나있다고 가정하고, 시작 볼륨을 출발지라고 생각하면서출발지로부터 볼륨을 더하고 .. 2025. 3. 11.
[컴퓨터구조] 상호배제(Mutual Exclusion) 뮤텍스(Mutex) & 세마포어 (Semaphore) 동일한 데이터를 동시성 프로그래밍 등으로 인해 여러 프로세스, 여러 스레드가 동시에 접근할 수 있다면, 다른 프로세스에 의해서 변경되거나 삭제된 값으로 인해 다른 프로세스에서 오류가 발생할 수 있다.여러 프로세스가 동시에 접근하는 데이터 영역을 임계 영역(Critical Section)이라고 부르고 이를 최소화할 수 있도록 프로그램을 설계하는 것이 중요하다.동일한 데이터를 여러 프로세스가 동시에 접근해서 사용한다면 오류가 발생할 수 있기 때문에, 한 프로세스가 해당 자원을 사용하고 있을 때 다른 프로세스의 접근을 막는 상호배제(Mutual Exclusion) 방법이 필요하다. 이 상호 배제 방법에는 세마포어와 뮤텍스가 있다. 두 방법 모두 자원에 대해서 mutex, semaphore에 관한 명령어를 호출.. 2025. 3. 10.
[컴퓨터구조] CPU 아키텍처 (x86, ARM) CPU 아키텍처를 설명하기 전에 ISA 개념을 알고 있으면 좋을 듯 ISA: Instruction Set Architecture는 CPU가 이해할 수 있는 명령어 집합이다.이게 각각의 CPU 아키텍처마다 다름.따라서 응용 프로그램이 해당 CPU에서 실행될 수 있도록 컴파일 할 때 맞는 CPU의 ISA, CPU 아키텍처에 따라야함. CPU 아키텍처는 CPU의 설계(내부 구성요소, 데이터 버스, 레지스터)와 명령어 집합 (ISA)를 정의한다.이는 다른 하드웨어와 소프트웨어 간의 상호작용에 사용되는 인터페이스 역할을 함 CPU 아키텍처 종류x86 아키텍처 (CISC: Complex Instruction Set Computing 계열)이름대로 복잡하고 다양한 명령어를 지원함. 그래서 한 개의 긴 명령어로 여러 .. 2025. 3. 10.
[컴퓨터구조] 캐시 메모리 (개념, 역할, 매핑, 지역성) 캐시 메모리의 개념과 역할에 대해 설명해주세요.데이터를 임시로 저장해두는 메모리디바이스간 처리 속도 차이를 해소하기 위한 버퍼 역할 (주기억장치와 CPU사이에 위치)ex. 한번 사용한 데이터를 캐시에 저장해두고 이후에 동일한 데이터를 불러올 때 하드 디스크에서 불러오지 않아도 되도록 하여 처리 시간을 단축시킴.캐시 성능은 CPU가 호출하는 데이터가 캐시에 저장되어 있는 확률로 결정된다. 따라서 CPU가 호출할 만한 데이터를 어느정도 예측하는 것이 필요함매핑: 캐시 메모리와 주기억장치 사이에서 정보를 옮기는 것직접매핑: 데이터의 원래 주소를 캐시 라인 개수로 나눈 나머지가 가리키는 주소에 저장. 충돌이 자주 발생해서 교체가 잦음. 구현이 쉬움.연관매핑: 캐시 라인에서 빈 곳 아무데나 혹은 빈 곳이 없다면 .. 2025. 3. 10.
[백준 1743] 음식물 피하기 (Swift) https://www.acmicpc.net/problem/1743 BFSN*M 격자 판에 K개의 음식물의 위치가 (r,c) 로 주어지고, 인접한 음식들의 묶음 중 가장 큰 묶음의 크기를 출력하는 문제(인접 : 상하좌우로 연결되어 있음) 접근방법우선 2차원 배열 map에 음식물의 위치를 표시하고, map의 모든칸을 확인하면서 방문여부와 음식물여부를 확인해서,방문한 적이 없고 음식물인 칸을 큐에 추가한다.그럼 이제 이 칸이 속한 음식물 묶음의 크기를 BFS를 통해서 구한다. (인접한 음식물을 큐에 넣기, 큐가 빌 때까지 반복, 큐에서 뺄 때 마다 음식물 묶음의 크기 +1)큐가 비어서 반복문이 종료되면 해당 음식물 묶음의 크기를 현재까지 최대 음식물 묶음의 크기를 저장하는 변수 result 와 비교해서큰 값을.. 2025. 3. 10.
728x90

티스토리툴바